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.

- 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 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

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.

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

- 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.