MSC17203: Data Structures UNIT - I: Linear Data Structures: Abstract Data Types - Asymptotic Notations: Big-Oh, mega and Theta Best, Worst and Average case Analysis: Definition and an example Arraysand its – – representations Stacks and Queues Linked lists Linked list based implementation of Stacks – – – and Queues Evaluation of Expressions Linked list based polynomial addition. – – UNIT II: – Non-Linear Data Structures: Trees Binary Trees Binary tree representation and traversals – – – Threaded binary trees Binary tree representation of trees Application of trees: Set – – representation and Union-Find operations Graph and its representations Graph Traversals – – – Connected components. UNIT III: – Search Structures And Priority Queues: AVL Trees Red-Black Trees Splay Trees – – – Binary Heap UNIT IV: – Searching: Linear Search Binary Search – Sorting: Insertion Sort Merge Sort Quick Sort Heap Sort Sorting With Disks K-Way – – – – – Merging Sorting With Tapes Polyphase Merge. – – Text Books: 1. Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures, Galgotia Book Sorce, Gurgaon, 1976. 2. Gregory L. Heilman, Data Structures, Algorithms and Object Oriented Programming, Tata Mcgraw-Hill, New Delhi, 2002. Reference Books: 1. Jean-Paul Tremblay and Paul G. Sorenson, An Introduction to Data Structures with Applications, Second Edition, Tata McGraw-Hill, New Delhi, 1991. 2. Alfred V. Aho, John E. Hopcroft and Jeffry D. Ullman, Data Structures and Algorithms, Pearson Education, New Delhi, 2006.
MSC17203: Data Structures UNIT - I: Linear Data Structures: Abstract Data Types - Asymptotic Notations: Big-Oh, mega and Theta – Best, Worst and Average case Analysis: Definition and an example – Arraysand its representations – Stacks and Queues – Linked lists – Linked list based implementation of Stacks and Queues – Evaluation of Expressions – Linked list based polynomial addition. UNIT – II: Non-Linear Data Structures: Trees – Binary Trees – Binary tree representation and traversals – Threaded binary trees – Binary tree representation of trees – Application of trees: Set representation and Union-Find operations – Graph and its representations – Graph Traversals – Connected components. UNIT – III: Search Structures And Priority Queues: AVL Trees – Red-Black Trees – Splay Trees – Binary Heap UNIT – IV: Searching: Linear Search – Binary Search Sorting: Insertion Sort – Merge Sort – Quick Sort – Heap Sort – Sorting With Disks – K-Way Merging – Sorting With Tapes – Polyphase Merge. Text Books: 1. Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures, Galgotia Book Sorce, Gurgaon, 1976. 2. Gregory L. Heilman, Data Structures, Algorithms and Object Oriented Programming, Tata Mcgraw-Hill, New Delhi, 2002. Reference Books: 1. Jean-Paul Tremblay and Paul G. Sorenson, An Introduction to Data Structures with Applications, Second Edition, Tata McGraw-Hill, New Delhi, 1991. 2. Alfred V. Aho, John E. Hopcroft and Jeffry D. Ullman, Data Structures and Algorithms, Pearson Education, New Delhi, 2006.
MSC%20I%20year%20Syllabus.docx