Course Schedule
Lectures

MWF 10:30am  11:50am GHC 4401 —
Umut Acar,
Robert Harper
Monday and Wednesday Main Lectures, Friday Review Lecture
Recitations
Schedule and Course Book
The following schedule is under development and subject to
change. You can find
the complete book
here. Comments and corrections are welcome; please enter them
here.

Week 1
 Aug 29
 Mathematical Preliminaries
· Chapter  Preliminaries
 SPARC  A Strict Functional Language for Parallel Computing
· Chapter  SPARC
 Overview and Introduction
· Chapter  Introduction
 ParenLab out
 Aug 30
 recitation Parentheses Matching
· Worksheet
· Notes
 Aug 31
 Algorithm Design and Analysis
· Chapter  Algorithm Design and Analysis
 Sep 2
 Algorithm Design and Analysis
· Chapter  Genome Sequencing

Week 2
 Sep 5
 Labor Day  No Lecture
 Sep 6
 recitation Solving Recurrences
· Worksheet
· Notes
 Sep 7
 Genome Sequencing
· Chapter  Genome Sequencing
 Sep 9
 Practice of Parallelism
· Parentheses Matching
 ParenLab due
 SkylineLab out

Week 3
 Sep 12
 Sequences I
· Chapter  Sequences
 Sep 13
 recitation Scan
· Worksheet
· Notes
 Sep 14
 Sequences II
· Chapter  Sequences
 Sep 16
 Contraction & DivideandConquer
· Chapter  Contraction
· Chapter  Divide and Conquer
 SkylineLab due
 BignumLab out

Week 4
 Sep 19
 Maximum contiguous subsequence problem
· Chapter  Maximum contiguous subsequence problem
 Sep 20
 recitation Scan Reloaded
· Worksheet
· Notes
 Sep 21
 Probability Theory
· Chapter  Probability Theory
 Sep 23
 BignumLab due
 RandomLab out

Week 5
 Sep 26
 Probability Theory
· Chapter  Probability Theory
 Analysis of Randomized Algorithms
· Chapter  Analysis of Randomized Algorithms
 Sep 27
 recitation Randomization
· Worksheet
· Notes
 Sep 28
 Analysis of Randomized Algorithms
· Chapter  Analysis of Randomized Algorithms
 Sep 30
 Quicksort Analysis Review
· Chapter  Analysis of Randomized Algorithms
 RandomLab due
 FingerLab out

Week 6
 Oct 3
 Binary Search Trees and Treaps I
· Chapter  Binary Search Trees and Treaps
 Oct 4
 recitation Treaps
· Worksheet
· Notes
 Oct 5
 Binary Search Trees and Treaps II
· Chapter  Binary Search Trees and Treaps
 Oct 7
 Exam I
· Practice Exam
· Practice Exam Solutions

Week 7
 Oct 10
 Sets and Tables
· Chapter  Sets and Tables
 Oct 11
 recitation Generalized BST Combinations (and Exam Debrief)
· Worksheet
· Notes
 Oct 12
 Sets and Tables and Graphs
· Chapter  Sets and Tables
· Chapter  Graphs and their Representation
 Oct 14
 FingerLab due
 RangeLab out

Week 8
 Oct 17
 Graph Search and BFS
· Chapter  Graph Search
 Oct 18
 recitation Intervals with Augmented Tables
· Worksheet
· Notes
 Oct 19
 DFS and Applications
· Chapter  Graph Search
 Oct 21
 MidSemester Break  No Lecture
 RangeLab due
 BridgeLab out

Week 9
 Oct 24
 Shortest Paths
· Chapter  Shortest Paths
 Oct 25
 recitation Graph Search
· Worksheet
· Notes
 Oct 26
 Shortest Paths
· Chapter  Shortest Paths
 Oct 28
 BridgeLab (written) due
 ShortLab out

Week 10
 Oct 30
 BridgeLab (programming) due
 Oct 31
 Graph Contraction I
· Chapter  Graph Contraction
 Nov 1
 recitation Shortest Paths
· Worksheet
· Notes
 Nov 2
 Graph Contraction II
· Chapter  Graph Contraction
 Nov 4
 ShortLab due
 SegmentLab out

Week 11
 Nov 7
 Minimum Spanning Trees
· Chapter  Minimum Spanning Trees
 Nov 8
 recitation Graph Contraction and MSTs
· Worksheet
· Notes
 Nov 9
 Dynamic Programming I
· Chapter  Dynamic Programming
 Nov 11
 Exam II
· Practice Exam
· Practice Exam Solutions

Week 12
 Nov 14
 Dynamic Programming II
· Chapter  Dynamic Programming
 SegmentLab due
 Nov 15
 recitation SSSP with Dynamic Programming
· Worksheet
· Notes
 Nov 16
 Dynamic Programming III (short lecture)
· Chapter  Dynamic Programming
 Nov 18
 DPLab out

Week 13
 Nov 21
 Hash Tables
· Chapter  Hash Tables
 Nov 22
 recitation Hashing
· Worksheet
· Notes
 Nov 23
 Priority Queues and Leftist Heaps
· Chapter  Priority Queues

Week 14
 Nov 28
 Parallel Algorithms in Practice, Chapters 1,2,3,4
· Lecture Notes
 DPLab due
 PASLLab out
 Nov 29
 recitation Priority Queues
· Worksheet
· Notes
 Nov 30
 Parallel Algorithms in Practice, Chapters 6,7
· Lecture Notes
 Dec 2
 Fun with Hashing (Optional)

Week 15
 Dec 5
 Parallel Algorithms in Practice, Chapters 8,9
· Lecture Notes
 Dec 6
 recitation Examples in PASL
· Worksheet
· rec15.hpp
· rec15bench.cpp
· Notes
· Code Solutions
 Dec 7
 Parallel Algorithms in Practice, Chapter 10
· Lecture Notes
 Dec 9
 No class today
 PASLLab due

Week 16
 Dec 14
 Review Session (7pm, Rashid Auditorium)
 Dec 16
 Final Exam (1PM4PM)
· Practice Exam
· Practice Exam Solutions