Classification of Data Structures:
Primitive and Non- Primitive, Linear and Nonlinear; Data structure Operations, Stack: Definition, Representation, Operations and Applications: Polish and reverse polish expressions, Infix to postfix conversion, evaluation of postfix expression, infix to prefix, postfix to infix conversion.
Recursion -
Factorial, GCD, Fibonacci Sequence, Tower of Hanoi. Queue: Definition, Representation, Queue Variants: Circular Queue, Priority Queue, Double Ended Queue; Applications of Queues. Programming Examples.
Linked List:
Limitations of array implementation, Memory Management: Static (Stack) and Dynamic (Heap) Memory Allocation, Memory management functions. Definition, Representation, Operations: getnode() and Freenode() operations, Types: Singly Linked List. Linked list as a data Structure, Inserting and removing nodes from a list, Linked implementations of stacks, Header nodes, Array implementation of lists.
Introduction, Fundamentals of the Analysis of Algorithm Efficiency Notion of Algorithm, Fundamentals of Algorithmic Problem Solving, Important Problem Types, Analysis Framework, Asymptotic Notations and Basic efficiency classes, Mathematical analysis of Recursive and Nonrecursive algorithms.
Brute Force:
Selection Sort and Bubble Sort, Sequential Search, Exhaustive search and String Matching. Divide-and-Conquer Mergesort, Quicksort, Binary Search, Binary tree Traversals and related properties. Decrease-and-Conquer Insertion Sort, Depth First and Breadth First Search, Topological sorting. Greedy Technique Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm.
Question Paper Pattern:
• The Question paper will have TEN questions
• Each full question will be for 20 marks
• There will be 02 full questions (with maximum of four sub questions) from each module.
• Each full question will have sub questions covering all the topics under a module.
• The students will have to answer FIVE full questions, selecting one full question from each module.
Textbooks
1. Introduction to the Design and Analysis of Algorithms. AnanyLevitin, Pearson Education, 2nd Edition.
2. Programming in ANSI C, Balaguruswamy, McGraw Hill Education .
3. Data Structures Using C and C++ by YedidyahLangsam and Moshe J. Augenstein and Aaron M Tenanbanum, 2nd Edition, Pearson Education Asia, 2002.
4. Introduction to Data Structure and Algorithms with C++ by Glenn W. Rowe.
Course Outcomes:
At the end of the course students will be able to
1. CO1: Demonstrate different data structures, its operations using C programming.
2. CO2: Analyse the performance of Stack, Queue, Lists, Trees, Hashing, Searching and Sorting techniques.
3. CO3: Implement some applications of data structures in a high-level language such as C/C++
4. CO4: Design and apply appropriate data structures for solving computing problems.
5. CO5: Compute the efficiency of algorithms in terms of asymptotic notations for the given problem.