Objectives: The course is intended to provide the foundations of the practical implementation and usage of Algorithms and Data Structures. One objective is to ensure that the student evolves into a competent programmer capable of designing and analyzing implementations of algorithms and data structures for different kinds of problems. The second objective is to expose the student to the algorithm analysis techniques, to the theory of reductions, and to the classification of problems into complexity classes like NP.
Outcomes:
By the end of the course, the students will be able to :
- design and analyze programming problem statements.
- choose appropriate data structures and algorithms, understand the ADT/libraries, and use it to design algorithms for a specific problem.
- understand the necessary mathematical abstraction to solve problems.
- come up with analysis of efficiency and proofs of correctness
- comprehend and select algorithm design approaches in a problem specific manner.
Course Contents:
Review of Basic Concepts, Asymptotic Analysis of Recurrences.
Randomized Algorithms. Randomized Quicksort, Analysis of Hashing algorithms.
Algorithm Analysis Techniques - Amortized Analysis. Application to Splay Trees.
External Memory ADT - B-Trees. Priority Queues and Their Extensions: Binomial heaps, Fibonacci heaps, applications to Shortest Path Algorithms. Partition ADT: Weighted union, path compression, Applications to MST. Algorithm Analysis and Design Techniques. Dynamic Programming-Bellman-Ford, Greedy Algorithms.
Network Flows-Max flow, min-cut theorem, Ford-Fulkerson, Edmonds-Karp algorithm, Bipartite Matching. NP-Completeness and Reductions.
Text Books:
- Introduction to Algorithms, by T. H. Cormen, C. E. Lieserson, R. L. Rivest, and C. Stein, Third Edition, MIT Press.
Reference Books:
- Algorithms, by S. Dasgupta, C. Papadimitrou, U Vazirani, Mc Graw Hill.
- Algorithm Design, by J. Klienberg and E. Tardos, Pearson Education Limited.
