Algorithms & Complexity (CS 601)
Schedule: Monday, 2-3:30 PM. Thursday, 2-3:30 PM.
Venue: LC002
Pre-requisites: Comfort with abstraction. Basic Run-time analysis, O-notation, Recursion. Basic probability and combinatorics. Basic data structures: array, list, stack, queue. Basic graph algorithms: cycles, trees, depth-first search, breadth-first search, shortest path.
Course Content:
Algorithms: Basic principles like induction/recursion. Divide and Conquer, Dynamic Programming, Greedy Algorithms, Bipartite Matching, Network Flow, Reductions.
Complexity: Undecidability, Polynomial-time, and the Complexity classes NP, co-NP. NP-hardness and NP-completeness.
Coping with Hardness.
Approximation: Traveling Salesman Problem, Geometric Set Cover.
Parameterization: Vertex Cover, Dominating Set, k-Cycle.
Randomization: Random variables, Linearity of expectation, and Applications like approximate max-cut, quicksort, min-cut.
Learning Objectives:
This is a moderate level course on Algorithms & Complexity. We will discuss techniques needed in designing and analysing efficient algorithms and data structures for computational problems. Also, we will discuss the limits of computation. After successful completion of this course, students will be able to -
explain fundamental concepts, structures, and problem definitions in basic Algorithms & Complexity.
explain, analyze, and evaluate the discussed algorithms.
select and adapt appropriate algorithms and data structures to related problems.
model and analyze unknown applied or theoretical problems and develop and possibly implement efficient solutions independently.
Selected Readings:
Books
Algorithm Design, J. Kleinberg and E. Tardos, Addison Wesley, 2005.
Introduction to Algorithms by T. H. Corman, C. E. Leiserson, R. L. Rivest, C. Stein.
Algorithms, Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani.
Useful notes from Prof. Sundar's course.
Grading:
Grades will be based on a mid-sem (25%), a final (40%), two in-class quizzes (30%), and class participation (5%).