Week  Day  Topic  Lecture Notes  Homeworks

1  Jan 19  Performance and scalability of parallel algorithms  Section 1 (ps)

1  Jan 21  PRAM models  Section 2 (ps) (slides) (html)

2  Jan 26  Parallel complexity theory  NC algorithms  Section 3 (ps) (slides) (html)

2  Jan 28  Parallel complexity theory  Pcompleteness  Section 4 (ps) (slides) (html)  Homework 1 (ps) (html)

3  Feb 2  Interconnection networks  survey of topologies  Section 5 (ps) (slides) (html)

3  Feb 4  Interconnection networks  properties  Section 5 (ps) (slides) (html)  Homework 2 (ps) (html)

4  Feb 9  Embeddings and simulations among INs I.  Section 6 (ps) (slides) (html)

4  Feb 11  Embeddings and simulations among INs II.  Section 6 (ps) (slides) (html)  Homework 3 (ps) (html)

5  Feb 16  Routing and switching technologies  Section 7 (ps) (slides) (html)

5  Feb 18  Virtual channels and deadlocks  Section 8 (ps) (slides) (html)

6  Feb 23  Permutation routing in meshbased networks  Section 9 (ps) (slides) (html)

6  Feb 25  Permutation routing in hypercubic networks  Section 10 (ps) (slides) (html)  Homework 4 (ps)

7  Mar 2  Onetoall broadcast algorithms  Section 11 (ps) (slides) (html)

7  Mar 4  Multicast, IRC, and onetoall scatter algorithms  Section 12 (ps) (slides) (html)  Homework 5 (ps) (html)

8  Mar 16  Alltoall broadcast algorithms in SF networks  Section 13 (ps) (slides) (html)

8  Mar 18  Alltoall scatter algorithms  Section 14 (ps) (slides) (html)  Homework 6 (ps) (html)

9  Mar 23  Introduction to parallel sorting on meshes  Section 15 (ps) (slides) (html)

9  Mar 25  Asymptotically optimal mesh sorting algorithm  Section 16 (ps) (slides) (html)  Homework 7 (ps) (html)

10  Mar 30  Parallel sorting on hypercubic machines  Section 17 (ps) (slides) (html)

10  Apr 1  Optimal EREW PRAM sorting  Section 18 (ps) (slides) (html)

11  Apr 6  Parallel matrix operations  Section 19 (ps) (slides) 
11  Apr 8  Solving systems of equations in parallel I  Section 20 (ps) (slides)  Homework 8 (ps)

12  Apr 13  Solving systems of equations in parallel II  Section 20 (ps) (slides)

12  Apr 15  Parallel scan  introduction  Section 21 (ps) (slides)  Homework 9 (ps)

13  Apr 20  Advanced applications of parallel scan  Section 22 (ps) (slides)

13  Apr 22  Parallel scan on linked lists  Section 23 (ps) (slides)

14  Apr 27  Deterministic coin tossing  Section 24 (ps) (slides)

14  Apr 29  Euler tour technique and its applications  Section 25 (ps) (slides)  Homework 10 (ps)

15  May 4  Parallel tree contraction  Section 26 (ps) (slides)

15  May 6  Parallel connected component algorithms  Section 27 (ps) (slides)

Finals  May 11  Final Exam (Tuesday, 8:00)
