Course Schedule
Lectures

MWF 10:30am  11:50am, PH 100 ‐
Umut Acar,
Daniel Sleator
Monday and Wednesday Main Lectures, Friday Bonus Lecture
Recitations
A 
Tue 
9:30am  10:20am 
GHC 4215 
Namita,
Pranathi,
Connor

B 
Tue 
10:30am  11:20am 
PH A18B 
Alex,
Yiming,
Yiwei

C 
Tue 
12:30pm  1:20pm 
DH 2122 
Rameel,
Cayden

D 
Tue 
12:30pm  1:20pm 
SH 214 
Alisa,
David,
Coral

E 
Tue 
1:30pm  2:20pm 
WEH 5312 
Jacky,
Komal

F 
Tue 
3:30pm  4:20pm 
WEH 5421 
Mango,
Akshat,
Kalpa

G 
Tue 
4:30pm  5:20pm 
SH 219 
Aditya,
Josh,
Anubhav

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.

Week 1
 Jan 14
 Overview and Introduction
· Overview
· Introduction
· Specification and Implementation
· Genome Sequencing
 Jan 15
 recitation Recurrences
· Solving Recurrencess
 MCSSLab out
· MCSSLab
 Jan 16
 Cost Models
· Lambda Calculus
· SPARC
· Functional Algorithms
· Cost Models
 Jan 18
 No Lecture

Week 2
 Jan 21
 No Lecture (MLK Day)
 ParenLab out
 Jan 22
 recitation Parentheses Matching
· Parentheses Matching
 MCSSLab due
 Jan 23
 Asymptotics and Recurrences
· Asymptotics
· Recurrences
 Jan 25
 Sequences I
· Introduction
· ADT
· Examples

Week 3
 Jan 28
 Sequences II
· Implementation
· Cost
· Ephemeral and Single Threaded Sequences
 ParenLab due
 SkylineLab out
 Jan 29
 recitation Scan
· Scan
 Jan 30
 Algorithm Design Techniques
· Basic Techniques
· Divide and Conquer
· Contraction
 Feb 1
 No Lecture

Week 4
 Feb 4
 Maximum contiguous subsequence problem
· MCSS
 SkylineLab due
 BignumLab out
 Feb 5
 recitation Scan Reloaded
· Scan Reloaded
 Feb 6
 Probability Theory
· Probability Theory
· Random Variables
· Expectation
 Feb 8
 No Lecture

Week 5
 Feb 11
 Randomized Algorithms I
· Introduction
 BignumLab due
 RandomLab out
 Feb 12
 recitation Randomization
· Randomization
 Feb 13
 Randomized Algorithms II
· Order Statistics
· Quicksort
 Feb 15
 No Lecture

Week 6
 Feb 18
 Binary Search Trees
· BST ADT
· Parametric Implementation
 RandomLab due
 FingerLab out
 Feb 19
 recitation Exam Review
 Feb 20
 Exam Review Session (Optional)
 Feb 22
 Exam I
· Practice Exam
· Practice Exam Solutions
· Practice Exam (Spring 17)
· Practice Exam Solutions (Spring 17)

Week 7
 Feb 25
 Treaps and Augmented Trees
· Treaps
· Augmented Trees
 Feb 26
 recitation Treaps
· Treaps
 Feb 27
 Sets and Tables
· Sets
· Tables
· Ordering and Augmentation
· Examples
 Mar 1
 No Lecture

Week 8
 Mar 4
 Graphs, Graph Search
· Graphs and their Representation
· Graph Search
 FingerLab due
 RangeLab out
 Mar 5
 recitation Augmented and Ordered Tables
· Augmented Tables
 Mar 6
 BFS
 Mar 8
 No Lecture (MidSemester Break)

Week 9
 Mar 11
 No Lecture (Spring Break)
 Mar 12
 recitation No Recitation (Spring Break)
 Mar 13
 No Lecture (Spring Break)
 Mar 15
 No Lecture (Spring Break)

Week 10
 Mar 18
 DFS and Applications
· DFS
 RangeLab due
 CriticalLab out
 Mar 19
 recitation Graph Search
· Graph Search
 Mar 20
 Shortest Paths I
· Introduction
· Dijkstra
 Mar 22
 No Lecture

Week 11
 Mar 25
 Shortest Paths II
· Bellman Ford
· Johnson
 CriticalLab due
 ShortLab out
 Mar 26
 recitation Shortest Paths
· Shortest Paths
 Mar 27
 Graph Contraction I
 Mar 29
 No Lecture

Week 12
 Apr 1
 Graph Contraction II
 ShortLab due
 SandwichLab out
 Apr 2
 recitation Graph Contraction
· Graph contraction
 Apr 3
 Minimum Spanning Trees
 Apr 5
 No Lecture

Week 13
 Apr 8
 Exam II
· Practice Exam
· Practice Exam Solutions
· Practice Exam (Spring 17)
· Practice Exam Solutions (Spring 17)
 Apr 9
 recitation Minimum Spanning Trees
· Minimum Spanning Trees
 Apr 10
 Dynamic Programming I
· Introduction
· SS and MED
 Apr 12
 No Lecture

Week 14
 Apr 15
 Dynamic Programming II
· Implementing
· OBST
 Apr 16
 recitation SSSP with Dynamic Programming
· Dynamic Programming
 Apr 17
 Priority Queues and Leftist Heaps
· Priority Queues
 Apr 19
 No Lecture
 SandwichLab due
 DPLab out

Week 15
 Apr 22
 Hashing
· Foundations
 Apr 23
 recitation Priority Queues
· Priority Queues
 Apr 24
 Hash Function and Hash Tables
· Hash Tables
 ConcurLab out
 Apr 26
 Effects and Parallelism
· Implementing Array Sequences

Week 16
 Apr 29
 Threads and Concurrency
· Threads
· Mutual Exclusion
 Apr 30
 recitation Hashing and Concurrency
· Dedup
 May 1
 No lecture
 May 3
 No lecture
 ConcurLab due (No late days!)

Week 17
 May 10
 Final Exam (1:00PM4:00PM)
· Practice Exam
· Practice Exam Solutions