Total number of hours 16 TREES Unit IV: – 1 1 Introduction, Terminology, Representation of Trees 2 2 Binary The Abstract Data Type, Properties of Binary Tress Binary Tree Representations, Binary Tree Traversal and Tree 3 2 Iterators Introduction, In order Traversal Preorder Traversal, Post order 4 1 Traversal Thread Binary Trees, Threads, In order Traversal of a Threaded Unit - 4 5 2 Binary Tree 6 2 Inserting a Node into a Threaded Binary Tree, Heaps Priority Queues, Definition of a Max Heap, Insertion into a Max 7 2 Heap, Deletion from a Max Heap 8 1 Binary Search Trees, Definition, Searching a Binary Search Tree Insertion into a Binary Search Tree, Deletion from a Binary 9 1 Search Tree, Height of Binary Search Tree. Total number of hours 14 Unit V: GRAPHS – The Graph Abstract Data Type, Introduction, Definition, Graph 1 1 Representation 2 1 Elementary Graph Operation, Depth First Search Breadth First Search, Connected Components, Spanning 3 2 Trees, Bi connected Components Unit - 5 4 1 Minimum Cost Spanning Trees, Kruskal S Algorithm 5 1 Prim s Algorithm Sollin’ s Algorithm Shortest Paths and Transitive Closure, Single Source/All 6 2 Destination: Nonnegative Edge Cost Single Source/All Destination: General Weights, All-Pairs 7 2 Shortest Path, Transitive Closure. Total number of hours 10 SORTING Unit VI: – 1 1 Insertion Sort, Quick Sort Unit 6 2 2 – Merge Sort Merging, Iterative Merge Sort 3 1 Recursive Merge Sort, Heap Sort Total number of hours 4 Overall Number of classes required: 66 Text Books: Data structures, Algorithms and Applications in C++, S.Sahni, University Press (India) Pvt.Ltd, 2nd edition, Universities Press Orient Longman Pvt. Ltd. 2 . Data structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education. Ltd., Second Edition. 3. Data structures and algorithms in C++, 3rd Edition, Adam Drozdek, Thomson References: 1 . Data structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education. Ltd., Second Edition._ 2 . Data structures using C and C++, Langsam, Augenstein and Tanenbaum, PHI._ 3. Problem solving with C++, The OOP, Fourth edition, W.Savitch, Pearson education Signature of Faculty
Total number of hours 16 Unit – IV: TREES Unit - 4 1 Introduction, Terminology, Representation of Trees 1 2 Binary The Abstract Data Type, Properties of Binary Tress 2 3 Binary Tree Representations, Binary Tree Traversal and Tree Iterators 2 4 Introduction, In order Traversal Preorder Traversal, Post order Traversal 1 5 Thread Binary Trees, Threads, In order Traversal of a Threaded Binary Tree 2 6 Inserting a Node into a Threaded Binary Tree, Heaps 2 7 Priority Queues, Definition of a Max Heap, Insertion into a Max Heap, Deletion from a Max Heap 2 8 Binary Search Trees, Definition, Searching a Binary Search Tree 1 9 Insertion into a Binary Search Tree, Deletion from a Binary Search Tree, Height of Binary Search Tree. 1 Total number of hours 14 Unit – V: GRAPHS Unit - 5 1 The Graph Abstract Data Type, Introduction, Definition, Graph Representation 1 2 Elementary Graph Operation, Depth First Search 1 3 Breadth First Search, Connected Components, Spanning Trees, Bi connected Components 2 4 Minimum Cost Spanning Trees, Kruskal S Algorithm 1 5 Prim s Algorithm Sollin’ s Algorithm 1 6 Shortest Paths and Transitive Closure, Single Source/All Destination: Nonnegative Edge Cost 2 7 Single Source/All Destination: General Weights, All-Pairs Shortest Path, Transitive Closure. 2 Total number of hours 10 Unit – VI: SORTING Unit – 6 1 Insertion Sort, Quick Sort 1 2 Merge Sort Merging, Iterative Merge Sort 2 3 Recursive Merge Sort, Heap Sort 1 Total number of hours 4 Overall Number of classes required: 66 Text Books: Data structures, Algorithms and Applications in C++, S.Sahni, University Press (India) Pvt.Ltd, 2nd edition, Universities Press Orient Longman Pvt. Ltd. 2 . Data structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education. Ltd., Second Edition. 3. Data structures and algorithms in C++, 3rd Edition, Adam Drozdek, Thomson References: 1 . Data structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education. Ltd., Second Edition._ 2 . Data structures using C and C++, Langsam, Augenstein and Tanenbaum, PHI._ 3. Problem solving with C++, The OOP, Fourth edition, W.Savitch, Pearson education Signature of Faculty
DS-MS-LecSche.docx