Course Schedule
Lectures

MWF 12:00pm  1:20pm GHC 4401 —
Umut Acar,
Daniel Sleator
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 31
 Mathematical Preliminaries
· Chapter  Preliminaries
 SPARC  A Strict Functional Language for Parallel Computing
· Chapter  SPARC
 Overview and Introduction
· Chapter  Introduction
 SuperLab out
 Sep 1
 recitation Introduction with Brute Force Sorting
· Worksheet
· Notes
 Sep 2
 Genome Sequencing
· Chapter  Genome Sequencing
 Sep 3
 Superlab due
 ParenLab out
 Sep 4
 Algorithm Analysis
· Chapter  Algorithm Analysis

Week 2
 Sep 7
 Labor Day (No Lecture)
 Sep 8
 recitation Parenthesis Matching
· Worksheet
· Notes
 Sep 9
 Sequences I
· Chapter  Sequences
 Sep 10
 ParenLab due
 SkylineLab out
 Sep 11
 Social Algorithms Session

Week 3
 Sep 14
 Sequences II
· Chapter  Sequences
 Sep 15
 recitation Scan
· Worksheet
· Notes
 Sep 16
 Contraction & DivideandConquer
· Chapter  Contraction
· Chapter  Divide and Conquer
 Sep 17
 SkylineLab due
 BignumLab out
 Sep 18
 Social Algorithms Session

Week 4
 Sep 21
 Maximum contiguous subsequence problem
· Chapter  Maximum contiguous subsequence problem
 Sep 22
 recitation Scan Reloaded
· Worksheet
· Notes
 Sep 23
 Randomized Algorithms
· Chapter  Randomized Algorithms
 Sep 24
 BignumLab due
 RandomLab out
 Sep 25
 Social Algorithms Session

Week 5
 Sep 28
 Quicksort
· Chapter  Randomized Algorithms
 Sep 29
 recitation Randomization
· Worksheet
· Notes
 Sep 30
 Binary Search Trees and Treaps I
· Chapter  Binary Search Trees and Treaps
 Oct 1
 RandomLab due
 FingerLab out
 Oct 2
 Social Algorithms Session

Week 6
 Oct 5
 Binary Search Trees and Treaps II
· Chapter  Binary Search Trees and Treaps
 Oct 6
 recitation Treaps
· Worksheet
· Notes
 Oct 7
 Binary Search Trees and Treaps III
· Chapter  Binary Search Trees and Treaps
 Oct 8
 FingerLab due
 Oct 9
 Exam I
· Practice Exam
· Practice Exam Solutions

Week 7
 Oct 12
 Sets and Tables
· Chapter  Sets and Tables
 Oct 13
 recitation Augmented and Ordered Tables
· Worksheet
· Notes
 Oct 14
 Sets and Tables and Graphs
· Chapter  Sets and Tables
· Chapter  Graphs and their Representation
 Oct 15
 RangeLab out
 Oct 16
 Social Algorithms Session

Week 8
 Oct 19
 Graph Search and BFS
· Chapter  Graph Search
 Oct 20
 recitation Graphs and BFS
· Worksheet
· Notes
 Oct 21
 DFS and Applications
· Chapter  Graph Search
 Oct 22
 RangeLab due
 BridgeLab out
 Oct 23
 MidSemester Break  No Review

Week 9
 Oct 26
 Shortest Paths
· Chapter  Shortest Paths
 Oct 27
 recitation DFS
· Worksheet
· Notes
 Oct 28
 Shortest Paths
· Chapter  Shortest Paths
 Oct 29
 BridgeLab due
 ShortLab out
 Oct 30
 Social Algorithms Session

Week 10
 Nov 2
 Graph Contraction I
· Chapter  Graph Contraction
 Nov 3
 recitation Shortest Paths
· Worksheet
· Notes
 Nov 4
 Graph Contraction II
· Chapter  Graph Contraction
 Nov 5
 ShortLab due
 SegmentLab out
 Nov 6
 Social Algorithms Session

Week 11
 Nov 9
 Minimum Spanning Trees
· Chapter  Minimum Spanning Trees
 Nov 10
 recitation Graph Contraction and MSTs
· Worksheet
· Notes
 Nov 11
 Dynamic Programming I
· Chapter  Dynamic Programming
 Nov 13
 Social Algorithms Session

Week 12
 Nov 16
 Dynamic Programming II
· Chapter  Dynamic Programming
 SegmentLab due
 DPLab out
 Nov 17
 recitation Dynamic Programming
· Worksheet
· Notes
 Nov 18
 Hash Tables
· Chapter  Hash Tables
 Nov 20
 Exam II
· Practice Exam
· Practice Exam Solutions

Week 13
 Nov 23
 Priority Queues and Leftist Heaps
· Chapter  Priority Queues
 Nov 24
 recitation TBA
 Nov 25
 Thanksgiving Break (No Lecture)
 Nov 27
 Thanksgiving Break (No Lecture)

Week 14
 Nov 30
 Parallel Algorithms in Practice (Chapters 1,2,3)
· Lecture Notes
 DPLab due
 PASLLab out
 Dec 1
 recitation TBA
 Dec 2
 Parallel Algorithms in Practice (Chapters 1,2,3)
· Lecture Notes
 Dec 4
 Parallel Algorithms in Practice (Chapters 4, 8)
· Lecture Notes

Week 15
 Dec 7
 Parallel Algorithms in Practice (Chapters 5,6,7)
· Lecture Notes
 Dec 8
 recitation TBA
 Dec 9
 Parallel Algorithms in Practice (Chapters 4, 8)
· Lecture Notes
 Dec 10
 PASLLab due
 Dec 11
 Parallel Algorithms in Practice (Chapters 10, 11)
· Lecture Notes