Complexity and Advanced Algorithms

Objective:

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:

Computing theory : Space Complexity, Space/time hierarchy, Interactive Proof systems, PCP and inapproximability
Parallel Algorithms : Models of computation and Flynn’s taxonomy including SIMD and MIMD, Design paradigms including divide and conquer, binary tree based computations, accelerated cascading, and the like.
Parallel algorithms for lists and trees : list ranking, tree traversal and evaluation
Parallel graph algorithms: connected components, matrix based computations
Randomized Algorithms : Tail inequalities including Chernoff bounds Examples for parallel/distributed symmetry breaking, Luby’s algorithm, graph coloring, Online algorithms for paging

Lecture Notes

Lecture notes on Space Compelxity
Lecture notes on Space and Time Hierarchy
Lecture notes on Introdcution to Randomized Algorithms
Lecture notes on Randomized Algorithms and Complexity Classes
Lecture notes on Perfect Hashing
Slides for Lecture 1 (Parallel Algorithms) on Parallel Algorithms : Introduction
Slides for Lecture 2 (Parallel Algorithms) on Parallel Algorithms : Analysis, Variants of PRAM, Merging
Slides for Lecture 3 (Parallel Algorithms) on Parallel Algorithms : CRCW Minima, Accelerated Cascading, Parallel Search
Slides for Lecture 4 to 6 (Parallel Algorithms) on Parallel Algorithms : List Ranking and Trees
Slides for Lecture on MIS Algorithm MIS : Luby's Algorithm
Lecture notes for the lower bounds in parallel computing
Lecture notes for the Short Overview of Approximation and Online Algorithms

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.

Textbooks

Introduction to Parallel Algorithms, J. JaJa.
Randomized Algorithms, by R. Motwani and P. Raghavan.
Introduction to the Theory of Computation, M. Sipser, 2nd edition.

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

Homework 1 (PDF). Due on 9/August in class. This short homework is to warm up on background material.
Homework 2 (PDF). Due on 19/August in class. This short homework will review the lectures on space complexity.
Homework 3 (PDF). Due on 06/September in class. This homework reviews probability, tail inequalities, and the lectures on hierarchy theorems. For Problem 4 on conditional probabilty, you may want to read the Appendix from the lecture notes on probabilty.
Homework 4 : Redo the mid term exam.
Homework 5 (PDF). Due on 04/October in class. This short homework will review the lectures on parallel algorithms.
Homework 6 (PDF). Due on 04/November in class. This short homework will review the lectures on parallel list and tree algorithms.
Homework 7 (PDF). Due on 25/November in class. This short homework will review the lectures on distributed MIS and lower bounds in parallel computing.