CS6013 - Advanced Data Structures and Algorithms

Brief Syllabus:


Divide and Conquer: Max-subarray problem, Strassen's matrix multiplication, Multiplying two polynomials (FFT). Greedy Algorithms: Interval scheduling problem, minimum spanning tree algorithms with correctness proof. Union-find data structure. Dynamic Programming: Rod cutting problem, matrix chain multiplication problem, longest common subsequence problem. Number Theoretic Algorithms: Elementary number theoretic notions, Euclid's algorithm for GCD computation, Miller-Rabin primality test. NP: Complexity class NP, NP completeness, reductions. Introduction to approximation algorithms: Combinatorial approximation algorithms for Min vertex cover, max-cut, and steiner tree problem. Introduction to randomized algorithms: Randomized quicksort, randomized algorithm for finding mincut (, also the Miller-Rabin test mentioned above).
Topics for self-study (will hold quizzes on these topics): big O notation and solving recurrence relations, sorting algorithms, binary search tree, red black tree.

Course books:

  • Introduction to algorithms, by Cormen, Leiserson, Rivest and Stein

  • Online lecture notes, by Jeff Erickson

  • Algorithm Design, by Kleinberg and Tardos

  • Data structures and algorithm analysis in C++ (Java), by Mark Weiss

  • Lecture notes, by T. Kavitha