Course Schedule
Lectures

MWF 12:00pm  1:20pm GHC 4401 —
Guy Blelloch,
Avrim Blum
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
 Jan 11
 Mathematical Preliminaries
· Chapter  Preliminaries
 SPARC  A Strict Functional Language for Parallel Computing
· Chapter  SPARC
 Overview and Introduction
· Chapter  Introduction
 SuperLab out
 Jan 12
 recitation Introduction with Burgers
· Worksheet
· Notes
 Jan 13
 Genome Sequencing
· Chapter  Genome Sequencing
 Jan 15
 Algorithm Analysis
· Chapter  Algorithm Analysis
 Superlab due
 ParenLab out

Week 2
 Jan 18
 MLK Day  No Lecture
 Jan 19
 recitation Parenthesis Matching
· Worksheet
· Notes
 Jan 20
 Sequences I
· Chapter  Sequences
 Jan 22
 Shortest Superstring Analysis (Optional)
 ParenLab due
 SkylineLab out

Week 3
 Jan 25
 Sequences II
· Chapter  Sequences
 Jan 26
 recitation Scan
· Worksheet
· Notes
 Jan 27
 Contraction & DivideandConquer
· Chapter  Contraction
· Chapter  Divide and Conquer
 Jan 29
 Online Resource Allocation (Optional)
· Notes
 SkylineLab due
 BignumLab out

Week 4
 Feb 1
 Maximum contiguous subsequence problem
· Chapter  Maximum contiguous subsequence problem
 Feb 2
 recitation Scan Reloaded
· Worksheet
· Notes
 Feb 3
 Randomized Algorithms
· Chapter  Randomized Algorithms
 Feb 5
 Randomized algorithms for 3SAT (optional)
· Notes
 BignumLab due
 RandomLab out

Week 5
 Feb 8
 Quicksort
· Chapter  Randomized Algorithms
 Feb 9
 recitation TBA
 Feb 10
 Binary Search Trees and Treaps I
· Chapter  Binary Search Trees and Treaps
 Feb 12
 TBA
 RandomLab due

Week 6
 Feb 15
 Binary Search Trees and Treaps II
· Chapter  Binary Search Trees and Treaps
 Feb 16
 recitation TBA
 Feb 17
 Binary Search Trees and Treaps III
· Chapter  Binary Search Trees and Treaps
 Feb 19
 Exam I
 FingerLab out

Week 7
 Feb 22
 Sets and Tables
· Chapter  Sets and Tables
 Feb 23
 recitation TBA
 Feb 24
 Sets and Tables and Graphs
· Chapter  Sets and Tables
· Chapter  Graphs and their Representation
 Feb 26
 TBA
 FingerLab due
 RangeLab out

Week 8
 Feb 29
 Graph Search and BFS
· Chapter  Graph Search
 Mar 1
 recitation TBA
 Mar 2
 DFS and Applications
· Chapter  Graph Search
 Mar 4
 MidSemester Break  No Lecture
 RangeLab due
 BridgeLab out

Week 9
 Mar 7
 Spring Break  No Lecture
 Mar 8
 Spring Break  No Recitation
 Mar 9
 Spring Break  No Lecture
 Mar 11
 Spring Break  No Review

Week 10
 Mar 14
 Shortest Paths
· Chapter  Shortest Paths
 Mar 15
 recitation TBA
 Mar 16
 Shortest Paths
· Chapter  Shortest Paths
 Mar 18
 TBA
 BridgeLab due
 ShortLab out

Week 11
 Mar 21
 Graph Contraction I
· Chapter  Graph Contraction
 Mar 22
 recitation TBA
 Mar 23
 Graph Contraction II
· Chapter  Graph Contraction
 Mar 25
 TBA
 ShortLab due
 SegmentLab out

Week 12
 Mar 28
 Minimum Spanning Trees
· Chapter  Minimum Spanning Trees
 Mar 29
 recitation TBA
 Mar 30
 Dynamic Programming I
· Chapter  Dynamic Programming
 Apr 1
 TBA
 SegmentLab due

Week 13
 Apr 4
 Dynamic Programming II
· Chapter  Dynamic Programming
 Apr 5
 recitation TBA
 Apr 6
 Hash Tables
· Chapter  Hash Tables
 Apr 8
 Exam II
 DPLab out

Week 14
 Apr 11
 Priority Queues and Leftist Heaps
· Chapter  Priority Queues
 Apr 12
 recitation TBA
 Apr 13
 Parallel Algorithms in Practice
· Lecture Notes
 Apr 15
 Carnival  No Lecture
 DPLab due
 PASLLab out

Week 15
 Apr 18
 Parallel Algorithms in Practice
· Lecture Notes
 Apr 19
 recitation TBA
 Apr 20
 Parallel Algorithms in Practice
· Lecture Notes
 Apr 22
 Parallel Algorithms in Practice
· Lecture Notes

Week 16
 Apr 25
 Parallel Algorithms in Practice
· Lecture Notes
 Apr 26
 recitation TBA
 Apr 27
 Final Review
· Lecture Notes
 Apr 29
 Final Review
 PASLLab due