Syllabus
DATA STRUCTURES AND ALGORITHMS(210244)
Teaching Scheme ExaminationScheme
Lectures : 4Hrs/week Theory : 100 Marks
Prerequisite: Fundamentals of Programming Languages (Subject Code: 110013).
To understand the different ways of data representation.
To define high level of abstraction of the needed linear data structure and algorithm.
To develop the ability to synthesize and analyze algorithms
To study the representation, implementation and applications of linear data structures
UNIT I: Review of 'C' [7 Hrs]
Arrays, Pointers: arrays & pointers.
Functions: Parameter passing call by value and call by reference, scope rules, functions and pointers, function returning pointer and pointer to function, String manipulations using arrays,pointer to pointer.
Structure and Union: Passing and returning structure as parameter for function ,structure and pointer.
Recursion: Definition, writing recursive functions & how recursion works.
File handling using C.
UNIT II: [TB 2] [7 Hrs]
Introduction to Algorithm, Data structures & Analysis of algorithms :
Introduction to Data Structures: Concept of data, Data object, Data structure, Abstract Data Types (ADT), realization of ADT in ‘C’.
Concept of Primitive and non primitive, linear and Non-linear, static and dynamic ,persistent and ephemeral data structures.
Analysis of algorithm: frequency count and its importance in analysis of an algorithm, Time complexity & Space complexity of an algorithm, Big ‘O’, ‘’ and ‘’ notations, Best, Worst and Average case analysis of an algorithm.
UNIT III:[TB 1] [8 Hrs]
Linear Data Structures using Sequential Organization:
Concept of sequential organization, Concept of Linear data structures, arrays as ADT, Storage representation of array – Row major and Column major & their address calculation, Multidimensional arrays, Concept of ordered list.
Applications : Polynomial representation using array, Concept of Sparse Matrix, it’s usage & representation using arrays, Algorithms for sparse matrix operations like addition, simple transpose, fast transpose & multiplication.
Analysis of the algorithms used.
Unit IV:[TB 1 & TB 2] [8 Hrs]
Sorting and searching techniques:
Need of sorting and searching, sorting order & stability in sorting.
Sorting Techniques: Algorithms for Bubble sort, Selection sort, Insertion sort, Shell sort, Radix sort, Quick sort and Merge sort.
Analysis of each sorting technique for best, worst and average case, Concept of Internal & External sorting.
Searching Techniques: Algorithms for Sequential search, Binary search, Fibonacci search & concept of Index Sequential search, analysis of each searching technique for best, worst and average case.
UNIT V:[TB 1] [9 Hrs]
Linear Data Structures using Linked Organization:
Limitations of static memory allocation. Dynamic memory allocation in C.
Concept of linked organization, Singly linked list, Doubly linked list, Circular linked list. Operations like insertion, deletion, traversal & other operations on these data structures.
Applications: Representation & manipulation of polynomials using circular linked lists, Application of doubly linked list in dynamic storage management, garbage collection and compaction. Representation of polynomial using generalized linked list (implementation not expected), Concept of skip list.
Analysis of the algorithms used.
UNIT VI:[TB 1 & TB 2] [9 Hrs]
Stacks and Queues:
Stacks: Concept of stack as ADT, Representation and implementation of stack using sequential & linked organization.
Applications: Examples using implicit stack, Simulating recursion using explicit stack, Arithmetic expression conversion & evaluation, reversing a string, parsing : well- formed parenthesis checking, concept of multi-stack & it’s representation. Analysis of the algorithms used.
Queues: Concept of queue as ADT, Representation and implementation of linear queue & circular queue using sequential & linked organization.
Applications: Josephus problem, Job scheduling, Queue simulation, Categorizing data, Double ended queue, Multi-queue and Priority queue. Analysis of the algorithms used.(Implementation not expected)
Text Books (TB):
R. Gilberg, B. Forouzan, “Data Structures: A pseudo code approach with C”, Cenage Learning, ISBN 9788131503140.
E. Horowitz , S.Sahani, S.Anderson-Freed ““Fundamentals of Data Structures in C”, Universities Press ,2008 ,ISBN 10:8173716056
Reference Books(RB):
1. A. Aho, J. Hopcroft, J. Ulman, “Data Structures and Algorithms”, Pearson Education, 1998, ISBN-0-201-43578-0
2. Y. Langsam, M. Augenstin and A. Tannenbaum, “Data Structures using C and C++”, 2nd Edition, Prentice Hall of India, 2002, ISBN-81-203-1177-9
3. J. Tremblay, P. Soresan, “An introduction to data structures with Applications”, 2nd edition, Tata McGraw-Hill International Editions, 1984, ISBN-0-07-462471-7.
PROGRAMMING LABORATORY(210246)
Teaching Scheme : Examination Scheme
Practical : 4 Hours /week Term Work : 25 marks
Practical : 50 Marks
Suggested List of Assignments Based on Data Structures and Algorithm
Write a program to perform Set operations - Union, Intersection, Difference, Symmetric Difference etc.
Write a program to perform various string operations such as Copy, Length, Reversing, Palindrome, Concatenation and to find occurrence substring etc with and without using library functions.
Write a program to perform operations on matrices like addition, multiplication, saddle point, magic square ,inverse & transpose etc using functions & pointers.[Minimum 4 operations]
Write a program to perform following operations on any database: Add, Delete, Modify, Display, Search & Sort etc.
Implement Sorting Methods using functions- Bubble Sort, Selection Sort, Insertion Sort, and Shell Sort.
Implement Sorting Methods using recursion- Quick Sort and Merge Sort.
Implement Searching Methods-Sequential Search, Binary Search, Fibonacci Search and Index Sequential Search.[Minimum 3 searching methods]
Represent polynomial using structures and write a menu driven program to perform Addition, Multiplication and Evaluation.
Represent Sparse Matrix using array and perform Matrix Addition, Simple and Fast Transpose.
Write a menu driven program to perform following operations on SLL/CDLL : Create, Insert – Start, end, between, Search & delete, Reverse ,Display etc.
Create two Singly Linked lists, sort one after creation and one while creation using Pointer manipulation. Merge these two lists into one list without creating a new node or swapping of the data.
Represent a polynomial using Circular Linked List and write a menu driven program to perform Addition, Multiplication and Evaluation.
Implement Stack as an ADT using Array. Use this ADT to perform expression conversion and evaluation (infix to postfix, infix to prefix, prefix to infix, prefix to postfix, postfix to infix and postfix to prefix).
Represent Circular Queue using Linked List and write a program to perform operations like Insert, Delete, Finding front and rear element.
Implement the Mini Project of Student Database using Linked list for following requirements:
Creation of Student Database in memory containing student ID, Name, Name Initials, Address, Contact No and Date of Birth .
Insertion, Deletion, Modification of student record for a given student ID.
Sorting on name initials and searching a particular student record on name initials
Note: All Assignments to be implemented using C and Time and Space Complexity is to be verified with theoretical findings.
Students will submit Term Work in the form Journal that will include minimum above 15 assignments. Each assignment will consist of Pseudo algorithm, program listing with proper documentation and printout of the output.
Practical examination will based on the Term Work and questions will be asked to judge the understanding of the assignments performed at the time of the examination.