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:
- 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
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.
- Introduction to Parallel Algorithms, J. JaJa.
- Randomized Algorithms, by R. Motwani and P. Raghavan.
- Introduction to the Theory of Computation, M. Sipser, 2nd
- 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.