Course Schedule
Lectures

MWF 10:30am  11:50am PH 100 —
Umut Acar,
Danny Sleator
Wednesday and Friday Main Lectures, Monday Bonus Lecture
Recitations
Recitation Attendance
You will use Diderot to sign in to your recitation.
Office Hours Queue
We are using an online office hours queue
this semester. Log in with your Andrew credentials and you will be able
to check the status of the queue and ask questions.
Schedule and Course Book
The following schedule is under development and subject to
change. You can find
the book on Diderot. Older pdf's are linked below but these will
not be updated.

Week 1
 Jan 15
 No Lecture
 Jan 16
 recitation Recurrences
· Worksheet
· Notes
 Jan 17
 Overview and Introduction
· Chapter  Introduction
· Slides  Introduction
 IntegralLab out
 Jan 19
 Genome Sequencing
· Chapter  Genome Sequencing
 SPARC  A Strict Functional Language for Parallel Computing
· Chapter  SPARC
 IntegralLab due
 ParenLab out

Week 2
 Jan 22
 No Lecture
 Jan 23
 recitation Parentheses Matching
· Worksheet
· Notes
 Jan 24
 Functional Algorithms and Cost Models
· Chapter  Algorithm Design and Analysis
· Notes  Cost Semantics
 Jan 26
 Algorithm Design and Analysis
· Chapter  Algorithm Design and Analysis
 ParenLab due
 SkylineLab out

Week 3
 Jan 29
 No Lecture
 Jan 30
 recitation Scan
· Worksheet
· Notes
 Jan 31
 Sequences I
· Chapter  Sequences
 Feb 2
 Sequences II
· Chapter  Sequences
 SkylineLab due
 BignumLab out

Week 4
 Feb 5
 TBD
 Feb 6
 recitation Scan Reloaded
· Worksheet
· Notes
 Feb 7
 Contraction & DivideandConquer
· Chapter  Contraction
· Chapter  Divide and Conquer
 Feb 9
 Maximum contiguous subsequence problem
· Chapter  Maximum contiguous subsequence problem
 BignumLab due
 RandomLab out

Week 5
 Feb 12
 No class
 Feb 13
 recitation Randomization
· Worksheet
· Notes
 Feb 14
 Probability Theory
· Chapter  Probability Theory
 Feb 16
 Analysis of Randomized Algorithms
· Chapter  Analysis of Randomized Algorithms

Week 6
 Feb 19
 Analysis of Randomized Algorithms II
· Chapter  Analysis of Randomized Algorithms
 RandomLab due
 Feb 20
 recitation Exam Review
 Feb 21
 Exam I
· Practice Exam
· Practice Exam Solutions
· Practice Exam (Spring 17)
· Practice Exam Solutions (Spring 17)
 Feb 23
 Binary Search Trees and Treaps I
· Chapter  Binary Search Trees and Treaps
 FingerLab out

Week 7
 Feb 26
 Binary Search Trees and Treaps II
· Chapter  Binary Search Trees and Treaps
 Feb 27
 recitation Treaps and Generalized BST Combinations
· Worksheet
· Notes
 Feb 28
 Merging in linear work and log span (Optional)
· Hand written notes
 Mar 2
 Sets and Tables
· Chapter  Sets and Tables (Maps)
· Notes on Maps
 FingerLab due
 RangeLab out

Week 8
 Mar 5
 Graphs, Graph Search
· Chapter  Graphs and their Representation
· Chapter  Graph Search
 Mar 6
 recitation TBA
 Mar 7
 BFS
· Chapter  Graph Search
 Mar 9
 recitation Intervals with Augmented Tables
· Worksheet
· Notes
 RangeLab due
 BridgeLab out

Week 9
 Mar 12
 DFS and Applications
· Chapter  Graph Search
· Additional Notes on SCC
 Mar 13
 recitation Graph Search
· Worksheet
· Notes
 Mar 14
 No Lecture
 Mar 16
 Shortest Paths
· Chapter  Shortest Paths
 BridgeLab (written) due
 ShortLab out

Week 10
 Mar 18
 BridgeLab (programming) due
 Mar 19
 Shortest Paths
· Chapter  Shortest Paths
· Notes on Johnson's Algorithm
 Mar 20
 recitation Shortest Paths
· Worksheet
· Notes
 Mar 21
 No Lecture
 Mar 23
 Graph Contraction I
· Chapter  Graph Contraction
 ShortLab due
 SegmentLab out

Week 11
 Mar 26
 Graph Contraction II
· Chapter  Graph Contraction
 Mar 27
 recitation Graph Contraction
· Worksheet
· Notes
 Mar 28
 Exam II
· Practice Exam
· Practice Exam Solutions
· Practice Exam (Spring 17)
· Practice Exam Solutions (Spring 17)
 Mar 30
 50th Aniversary Celebration, No Classes

Week 12
 Apr 2
 Minimum Spanning Trees
· Chapter  Minimum Spanning Trees
 Apr 3
 recitation Minimum Spanning Trees
· Worksheet
· Notes
 Apr 4
 No Lecture
 Apr 6
 Dynamic Programming I
· Chapter  Dynamic Programming
 SegmentLab due
 DPLab out

Week 13
 Apr 9
 Dynamic Programming II
· Chapter  Dynamic Programming
 Apr 10
 recitation SSSP with Dynamic Programming
· Worksheet
· Notes
 Apr 11
 Thanksgiving Break
 Apr 13
 Thanksgiving Break

Week 14
 Apr 16
 Priority Queues and Leftist Heaps
· Chapter  Priority Queues
 Apr 17
 recitation Priority Queues
· Worksheet
· Notes
 Apr 18
 Parallel Dynamic Programming (optional)
 Apr 20
 Hash Tables
· Chapter  Hash Tables
 DPLab due
 PASLLab out

Week 15
 Apr 23
 Parallel Algorithms in Practice, Chapters 110
· Lecture Notes
· Lecture Code
 Apr 24
 recitation Hashing and Examples in PASL
· Worksheet
· Notes
· rec14.hpp
· rec14bench.cpp
· Code Solutions
 Apr 27
 Multithreading and Concurrency I
· Lecture Notes
 PASLLab due

Week 16
 May 2
 Review Session (6PM8PM, GHC 4401)

Week 17
 May 6
 Final Exam (5:30PM8:30PM)
· Practice Exam
· Practice Exam Solutions