Complexity and Advanced Algorithms


The course is aimed at undergraduates and graduates who have done a first course in algorithms and a first course in formal languages. This course is intended to build up further on the above two themes. About a third of the course will cover topics in formal languages/computing theory such as reductions, NP, NP-Completeness, the language hierarchy, classical undecidability results, and the like. The remaining two-thirds of the course shall focus on two notions of recent advances in algorithms: parallel algorithms, and randomized algorithms.

In the case of parallel algorithms, focus will be on algorithm design and problem solving using the PRAM model. Classical PRAM algorithm design techniques such as binary tree based computations, accelerated cascading, divide and conquer will be covered. Also included in the coverage are PRAM algorithms for lists, trees, and graphs. Basic concepts in randomized algorithms will be covered with applications to parallel algorithms. Topics covered include tail inequalities, independence, application to symmetry breaking and the like.

List of Topics:

Lecture Notes

Grading policy

There will be weekly homeworks which constitute 15% of the grade. Two mid term exams constitute 55% of the grade. Rest of the grade (30%) is from the end term exam.

Learning Outcomes: At the end of the course, a student shall be able to understand the implications of parallelism in problem solving, design parallel algorithms, and also reason about the efficiency of the same.


Most times, these books are in limited supply, especially the first one. It is also not necessary to own a copy. Lecture material will be provided, and lectures will be self-contained.

Homework Assignments