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 Randomization
· Worksheet
· Notes
 Feb 10
 Binary Search Trees and Treaps I
· Chapter  Binary Search Trees and Treaps
 Feb 12
 Game Theory (Optional)
· Notes
 RandomLab due

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

Week 7
 Feb 22
 Sets and Tables
· Chapter  Sets and Tables
 Feb 23
 recitation Generalized BST Combinations (and Exam Debrief)
· Worksheet
· Notes
 Feb 24
 Sets and Tables and Graphs
· Chapter  Sets and Tables
· Chapter  Graphs and their Representation
 Feb 26
 Intro to Machine Learning (Optional)
 FingerLab due
 RangeLab out

Week 8
 Feb 29
 Graph Search and BFS
· Chapter  Graph Search
 Mar 1
 recitation Intervals with Augmented Tables
· Worksheet
· Notes
 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 Graph Search
· Worksheet
· Notes
 Mar 16
 Shortest Paths
· Chapter  Shortest Paths
 Mar 18
 No lecture today
 BridgeLab (written) due
 ShortLab out

Week 11
 Mar 20
 BridgeLab (programming) due
 Mar 21
 Graph Contraction I
· Chapter  Graph Contraction
 Mar 22
 recitation Shortest Paths
· Worksheet
· Notes
 Mar 23
 Graph Contraction II
· Chapter  Graph Contraction
 Mar 25
 Machine Learning II  Growth Function and VCdimension (Optional)
 ShortLab due
 SegmentLab out

Week 12
 Mar 28
 Minimum Spanning Trees
· Chapter  Minimum Spanning Trees
 Mar 29
 recitation Graph Contraction and MSTs
· Worksheet
· Notes
 Mar 30
 Dynamic Programming I
· Chapter  Dynamic Programming
 Apr 1
 No lecture today

Week 13
 Apr 4
 Dynamic Programming II
· Chapter  Dynamic Programming
 SegmentLab due
 Apr 5
 recitation SSSP with Dynamic Programming
· Worksheet
· Notes
 Apr 6
 Dynamic Programming III (short lecture)
· Chapter  Dynamic Programming
 Apr 8
 Exam II
· Practice Exam
· Practice Exam Solutions
 DPLab out

Week 14
 Apr 11
 Hash Tables
· Chapter  Hash Tables
 Apr 12
 recitation Hashing
· Worksheet
· Notes
 Apr 13
 Priority Queues and Leftist Heaps
· Chapter  Priority Queues
 Apr 15
 Carnival  No Lecture

Week 15
 Apr 18
 Parallel Algorithms in Practice, Chapters 1,2,3,4
· Lecture Notes
 DPLab due
 PASLLab out
 Apr 19
 recitation Priority Queues
· Worksheet
· Notes
 Apr 20
 Parallel Algorithms in Practice, Chapters 6,7
· Lecture Notes
 Apr 22
 Fun with Hashing (Optional)

Week 16
 Apr 25
 Parallel Algorithms in Practice, Chapters 8,9
· Lecture Notes
 Apr 26
 recitation Examples in PASL
· Worksheet
· rec15.hpp
· rec15bench.cpp
· Notes
· Code Solutions
 Apr 27
 Parallel Algorithms in Practice, Chapter 10
· Lecture Notes
 Apr 29
 No class today
 PASLLab due

Week 17
 May 4
 Review Session (7pm, Rashid Auditorium)
 May 6
 Final Exam (1PM4PM)
· Practice Exam
· Practice Exam Solutions