Course Schedule

Lectures

  1. MWF 12:00pm - 1:20pm GHC 4401 — Guy Blelloch, Avrim Blum

  2. Monday and Wednesday Main Lectures, Friday Review Lecture

Recitations

A Tue 09:30am - 10:20am WEH 5312 Edward, Angie
B Tue 10:30am - 11:20am WEH 5320 Jake, Narain
C Tue 12:30pm - 01:20pm WEH 5421 Sonya, Anisha
D Tue 12:30pm - 01:20pm WEH 8427 Nick, Yongshan
E Tue 01:30pm - 02:20pm SH 219 William, Bryan
F Tue 01:30pm - 02:20pm BH 255A Sam S, Yutong
G Tue 03:30pm - 04:20pm SH 222 Howard, Yongshan

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

    Jan 11
    Mathematical Preliminaries · Chapter - Preliminaries
    SPARC - A Strict Functional Language for Parallel Computing · Chapter - SPARC
    Overview and Introduction · Chapter - Introduction
    SuperLab out
    Jan 12
    recitation Introduction with Burgers · Worksheet · Notes
    Jan 13
    Genome Sequencing · Chapter - Genome Sequencing
    Jan 15
    Algorithm Analysis · Chapter - Algorithm Analysis
    Superlab due
    ParenLab out

  2. Week 2

    Jan 18
    MLK Day - No Lecture
    Jan 19
    recitation Parenthesis Matching · Worksheet · Notes
    Jan 20
    Sequences I · Chapter - Sequences
    Jan 22
    Shortest Superstring Analysis (Optional)
    ParenLab due
    SkylineLab out

  3. Week 3

    Jan 25
    Sequences II · Chapter - Sequences
    Jan 26
    recitation Scan · Worksheet · Notes
    Jan 27
    Contraction & Divide-and-Conquer · Chapter - Contraction · Chapter - Divide and Conquer
    Jan 29
    Online Resource Allocation (Optional) · Notes
    SkylineLab due
    BignumLab out

  4. Week 4

    Feb 1
    Maximum contiguous subsequence problem · Chapter - Maximum contiguous subsequence problem
    Feb 2
    recitation Scan Reloaded · Worksheet · Notes
    Feb 3
    Randomized Algorithms · Chapter - Randomized Algorithms
    Feb 5
    Randomized algorithms for 3-SAT (optional) · Notes
    BignumLab due
    RandomLab out

  5. Week 5

    Feb 8
    Quicksort · Chapter - Randomized Algorithms
    Feb 9
    recitation Randomization · Worksheet · Notes
    Feb 10
    Binary Search Trees and Treaps I · Chapter - Binary Search Trees and Treaps
    Feb 12
    Game Theory (Optional) · Notes
    RandomLab due

  6. Week 6

    Feb 15
    Binary Search Trees and Treaps II · Chapter - Binary Search Trees and Treaps
    Feb 16
    recitation Treaps · Worksheet · Notes
    Feb 17
    Binary Search Trees and Treaps III · Chapter - Binary Search Trees and Treaps
    Feb 19
    Exam I · Practice Exam · Practice Exam Solutions
    FingerLab out

  7. Week 7

    Feb 22
    Sets and Tables · Chapter - Sets and Tables
    Feb 23
    recitation Generalized BST Combinations (and Exam Debrief) · Worksheet · Notes
    Feb 24
    Sets and Tables and Graphs · Chapter - Sets and Tables · Chapter - Graphs and their Representation
    Feb 26
    Intro to Machine Learning (Optional)
    FingerLab due
    RangeLab out

  8. Week 8

    Feb 29
    Graph Search and BFS · Chapter - Graph Search
    Mar 1
    recitation Intervals with Augmented Tables · Worksheet · Notes
    Mar 2
    DFS and Applications · Chapter - Graph Search
    Mar 4
    Mid-Semester Break - No Lecture
    RangeLab due
    BridgeLab out

  9. Week 9

    Mar 7
    Spring Break - No Lecture
    Mar 8
    Spring Break - No Recitation
    Mar 9
    Spring Break - No Lecture
    Mar 11
    Spring Break - No Review

  10. Week 10

    Mar 14
    Shortest Paths · Chapter - Shortest Paths
    Mar 15
    recitation Graph Search · Worksheet · Notes
    Mar 16
    Shortest Paths · Chapter - Shortest Paths
    Mar 18
    No lecture today
    BridgeLab (written) due
    ShortLab out

  11. Week 11

    Mar 20
    BridgeLab (programming) due
    Mar 21
    Graph Contraction I · Chapter - Graph Contraction
    Mar 22
    recitation Shortest Paths · Worksheet · Notes
    Mar 23
    Graph Contraction II · Chapter - Graph Contraction
    Mar 25
    Machine Learning II - Growth Function and VC-dimension (Optional)
    ShortLab due
    SegmentLab out

  12. Week 12

    Mar 28
    Minimum Spanning Trees · Chapter - Minimum Spanning Trees
    Mar 29
    recitation Graph Contraction and MSTs · Worksheet · Notes
    Mar 30
    Dynamic Programming I · Chapter - Dynamic Programming
    Apr 1
    No lecture today

  13. Week 13

    Apr 4
    Dynamic Programming II · Chapter - Dynamic Programming
    SegmentLab due
    Apr 5
    recitation SSSP with Dynamic Programming · Worksheet · Notes
    Apr 6
    Dynamic Programming III (short lecture) · Chapter - Dynamic Programming
    Apr 8
    Exam II · Practice Exam · Practice Exam Solutions
    DPLab out

  14. Week 14

    Apr 11
    Hash Tables · Chapter - Hash Tables
    Apr 12
    recitation Hashing · Worksheet · Notes
    Apr 13
    Priority Queues and Leftist Heaps · Chapter - Priority Queues
    Apr 15
    Carnival - No Lecture

  15. Week 15

    Apr 18
    Parallel Algorithms in Practice, Chapters 1,2,3,4 · Lecture Notes
    DPLab due
    PASLLab out
    Apr 19
    recitation Priority Queues · Worksheet · Notes
    Apr 20
    Parallel Algorithms in Practice, Chapters 6,7 · Lecture Notes
    Apr 22
    Fun with Hashing (Optional)

  16. Week 16

    Apr 25
    Parallel Algorithms in Practice, Chapters 8,9 · Lecture Notes
    Apr 26
    recitation Examples in PASL · Worksheet · rec15.hpp · rec15-bench.cpp · Notes · Code Solutions
    Apr 27
    Parallel Algorithms in Practice, Chapter 10 · Lecture Notes
    Apr 29
    No class today
    PASLLab due

  17. Week 17

    May 4
    Review Session (7pm, Rashid Auditorium)
    May 6
    Final Exam (1PM-4PM) · Practice Exam · Practice Exam Solutions