Course Schedule

Lectures

  1. MWF 10:30am - 11:50am PH 100 — Umut Acar, Danny Sleator
  2. Wednesday and Friday Main Lectures, Monday Bonus Lecture

Recitations

A Tue 09:30am - 10:20am WEH 5312 Jennifer, Lizzi
B Tue 10:30am - 11:20am WEH 5310 Manik, Aashir
C Tue 12:30pm - 1:20pm DH 1209 Rahul, Matt
D Tue 12:30pm - 1:20pm SH 214 Alex, Mango, Rohan
E Tue 1:30pm - 2:20pm CFA 102 Nikhil, Allen
F Tue 1:30pm - 2:20pm BH 255A Vijay, Jon
G Tue 3:30pm - 4:20pm SH 222 Shreyan, Meheresh

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.

  1. 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
  2. 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
  3. 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
  4. Week 4

    Feb 5
    TBD
    Feb 6
    recitation Scan Reloaded · Worksheet · Notes
    Feb 7
    Contraction & Divide-and-Conquer · Chapter - Contraction · Chapter - Divide and Conquer
    Feb 9
    Maximum contiguous subsequence problem · Chapter - Maximum contiguous subsequence problem
    BignumLab due
    RandomLab out
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. Week 15

    Apr 23
    Parallel Algorithms in Practice, Chapters 1-10 · Lecture Notes · Lecture Code
    Apr 24
    recitation Hashing and Examples in PASL · Worksheet · Notes · rec14.hpp · rec14-bench.cpp · Code Solutions
    Apr 27
    Multithreading and Concurrency I · Lecture Notes
    PASLLab due
  16. Week 16

    May 2
    Review Session (6PM-8PM, GHC 4401)
  17. Week 17

    May 6
    Final Exam (5:30PM-8:30PM) · Practice Exam · Practice Exam Solutions