Course Schedule

Lectures

  1. MWF 10:30am - 11:50am, PH 100 ‐ Umut Acar, Daniel Sleator

  2. 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.

  1. 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

  2. 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

  3. 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

  4. 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

  5. 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

  6. 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)

  7. 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

  8. 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 (Mid-Semester Break)

  9. 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)

  10. 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

  11. 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

  12. 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

  13. 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

  14. 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

  15. 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

  16. 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!)

  17. Week 17

    May 10
    Final Exam (1:00PM-4:00PM) · Practice Exam · Practice Exam Solutions