Introduction to Abstract Data Types, Data structures and Algorithms; Analysis of Algorithms – Time and Space Complexity, Complexity Notation, Solving Recurrence Relations.; Divide-and-Conquer as a Design Technique; Recursion – Design of Recursive Functions / Procedures, Tail Recursion, Conversion of Recursive Functions to Iterative Form. Linear data structures – Lists, Access Restricted Lists (Stacks and Queues) – Implementation using Arrays and Linked Lists; Searching and Order Queries. Sorting – Sorting Algorithms (Online vs. Offline, In-memory vs. External, In-space vs. Out-of-space, QuickSort and Randomization). Unordered Collections: Hashtables (Separate Chaining vs. Open Addressing, Probing, Rehashing). Binary Trees – Tree Traversals. Partially Ordered Collections: Search Trees and Height Balanced Search Trees, Heaps and Priority Queues. Algorithm Design: Greedy Algorithms and Dynamic Programming. Graphs and Graph Algorithms: Representation schemes, Problems on Directed Graphs (Reachability and Strong Connectivity, Traversals, Transitive Closure. Directed Acyclic Graphs - Topological Sorting), Problems on Weighted Graphs (Shortest Paths. Spanning Trees). Introduction to Complexity Classes (P and NP) and NP-completeness. NP-Hard problems. Designing Algorithms for Hard Problems – Backtracking, Branch-and-Bound, and Approximation Algorithms.
Scope and Objective
To enable the student to develop different algorithms for a given situation, to test their validity, measure their complexity and analyze the performance (if necessary by simulation). To introduce techniques for designing data structures and algorithms.
Prescribed Text Book
Sahni, Sartaj, Data Structures, Algorithms and Application in C++, McGraw Hill International Edition.