Course Schedule

Lectures

  1. MWF 10:30am - 11:50am GHC 4401 — Guy Blelloch, Robert Harper

  2. Monday and Friday Main Lectures, Wednesday Bonus Lecture

Recitations

A Tue 09:30am - 10:20am DH 2122 Allen, Lizzi
B Tue 10:30am - 11:20am BH 255A Serena, Calvin
C Tue 11:30am - 12:20pm HH B131 Aashir, Irene
D Tue 12:30pm - 1:20pm HH B131 Aashir, Meheresh
E Tue 1:30pm - 2:20pm WEH 8427 Rohan, Rahul
F Tue 3:30pm - 4:20pm WEH 5421 Jonathan, Manik, Nikhil
G Tue 4:30pm - 5:20pm WEH 5310 Charles, Teddy, Ashwin

Recitation Attendance

Use the recitation attendance form to record your attendance with the weekly validation key.

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 complete book here. Comments and corrections are welcome; please enter them here.

  1. Week 1

    Aug 28
    Overview and Introduction · Chapter - Introduction · Slides - Introduction
    IntegralLab out
    Aug 29
    recitation Intro · Worksheet · Notes
    Aug 30
    No Lecture
    Sep 1
    Genome Sequencing · Chapter - Genome Sequencing
    SPARC - A Strict Functional Language for Parallel Computing · Chapter - SPARC
    IntegralLab due
    ParenLab out

  2. Week 2

    Sep 4
    Labor Day - No Class
    Sep 5
    recitation Parentheses Matching · Worksheet · Notes
    Sep 6
    Functional Algorithms and Cost Models · Chapter - Algorithm Design and Analysis · Notes - Cost Semantics
    Sep 8
    Algorithm Design and Analysis · Chapter - Algorithm Design and Analysis
    ParenLab due
    SkylineLab out

  3. Week 3

    Sep 11
    Sequences I · Chapter - Sequences
    Sep 12
    recitation Scan · Worksheet · Notes
    Sep 13
    TBD
    Sep 15
    Sequences II · Chapter - Sequences
    SkylineLab due
    BignumLab out

  4. Week 4

    Sep 18
    Contraction & Divide-and-Conquer · Chapter - Contraction · Chapter - Divide and Conquer
    Sep 19
    recitation Scan Reloaded · Worksheet · Notes
    Sep 20
    TBD
    Sep 22
    Maximum contiguous subsequence problem · Chapter - Maximum contiguous subsequence problem
    BignumLab due
    RandomLab out

  5. Week 5

    Sep 25
    Probability Theory · Chapter - Probability Theory
    Sep 26
    recitation Randomization · Worksheet · Notes
    Sep 27
    Analysis of Randomized Algorithms · Chapter - Analysis of Randomized Algorithms
    Sep 29
    No class

  6. Week 6

    Oct 2
    Analysis of Randomized Algorithms II · Chapter - Analysis of Randomized Algorithms
    RandomLab due
    Oct 3
    recitation Exam Review
    Oct 4
    Exam I · Practice Exam · Practice Exam Solutions · Practice Exam (Spring 17) · Practice Exam Solutions (Spring 17)
    Oct 6
    Binary Search Trees and Treaps I · Chapter - Binary Search Trees and Treaps
    FingerLab out

  7. Week 7

    Oct 9
    Binary Search Trees and Treaps II · Chapter - Binary Search Trees and Treaps
    Oct 10
    recitation Treaps and Generalized BST Combinations · Worksheet · Notes
    Oct 11
    Merging in linear work and log span (Optional) · Hand written notes
    Oct 13
    Sets and Tables · Chapter - Sets and Tables (Maps) · Notes on Maps
    FingerLab due
    RangeLab out

  8. Week 8

    Oct 16
    Graphs, Graph Search · Chapter - Graphs and their Representation · Chapter - Graph Search
    Oct 17
    recitation Intervals with Augmented Tables · Worksheet · Notes
    Oct 18
    BFS · Chapter - Graph Search
    Oct 20
    Mid Semester Break
    RangeLab due
    BridgeLab out

  9. Week 9

    Oct 23
    DFS and Applications · Chapter - Graph Search · Additional Notes on SCC
    Oct 24
    recitation Graph Search · Worksheet · Notes
    Oct 25
    No Lecture
    Oct 27
    Shortest Paths · Chapter - Shortest Paths
    BridgeLab (written) due
    ShortLab out

  10. Week 10

    Oct 29
    BridgeLab (programming) due
    Oct 30
    Shortest Paths · Chapter - Shortest Paths · Notes on Johnson's Algorithm
    Oct 31
    recitation Shortest Paths · Worksheet · Notes
    Nov 1
    No Lecture
    Nov 3
    Graph Contraction I · Chapter - Graph Contraction
    ShortLab due
    SegmentLab out

  11. Week 11

    Nov 6
    Graph Contraction II · Chapter - Graph Contraction
    Nov 7
    recitation Graph Contraction · Worksheet · Notes
    Nov 8
    Exam II · Practice Exam · Practice Exam Solutions · Practice Exam (Spring 17) · Practice Exam Solutions (Spring 17)
    Nov 10
    50th Aniversary Celebration, No Classes

  12. Week 12

    Nov 13
    Minimum Spanning Trees · Chapter - Minimum Spanning Trees
    Nov 14
    recitation Minimum Spanning Trees · Worksheet · Notes
    Nov 15
    No Lecture
    Nov 17
    Dynamic Programming I · Chapter - Dynamic Programming
    SegmentLab due
    DPLab out

  13. Week 13

    Nov 20
    Dynamic Programming II · Chapter - Dynamic Programming
    Nov 21
    recitation SSSP with Dynamic Programming · Worksheet · Notes
    Nov 22
    Thanksgiving Break
    Nov 24
    Thanksgiving Break

  14. Week 14

    Nov 27
    Priority Queues and Leftist Heaps · Chapter - Priority Queues
    Nov 28
    recitation Priority Queues · Worksheet · Notes
    Nov 29
    Parallel Dynamic Programming (optional)
    Dec 1
    Hash Tables · Chapter - Hash Tables
    DPLab due
    PASLLab out

  15. Week 15

    Dec 4
    Parallel Algorithms in Practice, Chapters 1-10 · Lecture Notes · Lecture Code
    Dec 5
    recitation Hashing and Examples in PASL · Worksheet · Notes · rec14.hpp · rec14-bench.cpp · Code Solutions
    Dec 8
    Multithreading and Concurrency I · Lecture Notes
    PASLLab due

  16. Week 16

    Dec 13
    Review Session (6PM-8PM, GHC 4401)

  17. Week 17

    Dec 17
    Final Exam (5:30PM-8:30PM) · Practice Exam · Practice Exam Solutions