Course Schedule

Lectures

  1. MWF 10:30am - 11:50am GHC 4401 — Guy Blelloch, Avrim Blum
  2. Monday and Wednesday Main Lectures, Friday Review Lecture

Recitations

A Tue 09:30am - 10:20am WEH 5312 Andra Marinescu, Charles Yuan
B Tue 10:30am - 11:20am WEH 5421 Aashir Master, Anatol Liu
C Tue 12:30am - 01:20pm DH 1209 Oliver Daids
D Tue 12:30pm - 01:20pm WEH 8427 Rohan Yadav, Serena Wang
E Tue 01:30pm - 02:20pm CFA 102 John Bostanci, Christina Yuan
F Tue 01:30pm - 02:20pm BH 255A Vivek Shankar, Teddy Ding
G Tue 03:30pm - 04:20pm SH 222 Ashwin Sekar, Sunny Gakhar

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 16
    MLK Day - No Classes
    Jan 17
    recitation No Recitation
    Jan 18
    Overview and Introduction · Chapter - Introduction
    Mathematical Preliminaries · Chapter - Preliminaries
    Jan 20
    Genome Sequencing · Chapter - Genome Sequencing
    SPARC - A Strict Functional Language for Parallel Computing · Chapter - SPARC
    ParenLab out
  2. Week 2

    Jan 23
    Algorithm Design and Analysis I · Chapter - Algorithm Design and Analysis
    Jan 24
    recitation Parentheses Matching · Worksheet · Notes
    Jan 25
    Algorithm Design and Analysis II · Chapter - Algorithm Design and Analysis
    Jan 27
    Running Code in Parallel
    ParenLab due
    SkylineLab out
  3. Week 3

    Jan 30
    Sequences I · Chapter - Sequences
    Jan 31
    recitation Scan · Worksheet · Notes
    Feb 1
    Sequences II · Chapter - Sequences
    Feb 3
    Scheduling Parallel Computation (Optional) · Chapter - Algorithm Design and Analysis
    SkylineLab due
    BignumLab out
  4. Week 4

    Feb 6
    Contraction & Divide-and-Conquer · Chapter - Contraction · Chapter - Divide and Conquer
    Feb 7
    recitation Scan Reloaded · Worksheet · Notes
    Feb 8
    Maximum contiguous subsequence problem · Chapter - Maximum contiguous subsequence problem
    Feb 10
    Online Resource Allocation (optional) · Online Resource Allocation
    BignumLab due
    RandomLab out
  5. Week 5

    Feb 13
    Probability Theory · Chapter - Probability Theory
    Feb 14
    recitation Randomization · Worksheet · Notes
    Feb 15
    Analysis of Randomized Algorithms · Chapter - Analysis of Randomized Algorithms
    Feb 17
    Merging in linear work and log span (Optional)
  6. Week 6

    Feb 20
    Binary Search Trees and Treaps I · Chapter - Binary Search Trees and Treaps
    RandomLab due
    Feb 21
    recitation Treaps · Worksheet
    Feb 22
    Binary Search Trees and Treaps II · Chapter - Binary Search Trees and Treaps
    Feb 24
    Exam I · Practice Exam · Practice Exam Solutions
    FingerLab out
  7. Week 7

    Feb 27
    Sets and Tables I · Chapter - Sets and Tables
    Feb 28
    recitation Generalized BST Combinations (and Exam Debrief) · Worksheet
    Mar 1
    Sets and Tables II · Chapter - Sets and Tables
    Mar 3
    FingerLab due
    RangeLab out
  8. Week 8

    Mar 6
    Graphs, Graph Search, and BFS · Chapter - Graphs and their Representation · Chapter - Graph Search
    Mar 7
    recitation Intervals with Augmented Tables · Worksheet
    Mar 8
    DFS and Applications · Chapter - Graph Search
    Mar 10
    RangeLab due
    BridgeLab out
  9. Week 9

    Mar 13
    Spring Break - No Lecture
    Mar 15
    Spring Break - No Lecture
  10. Week 10

    Mar 20
    Shortest Paths · Chapter - Shortest Paths
    Mar 21
    recitation Graph Search · Worksheet
    Mar 22
    Shortest Paths · Chapter - Shortest Paths
    Mar 24
    BridgeLab (written) due
    ShortLab out
  11. Week 11

    Mar 26
    BridgeLab (programming) due
    Mar 27
    Graph Contraction I · Chapter - Graph Contraction
    Mar 28
    recitation Shortest Paths · Worksheet
    Mar 29
    Graph Contraction II · Chapter - Graph Contraction
    Mar 31
    ShortLab due
    SegmentLab out
  12. Week 12

    Apr 3
    Minimum Spanning Trees · Chapter - Minimum Spanning Trees
    Apr 4
    recitation Graph Contraction and MSTs · Worksheet
    Apr 5
    Dynamic Programming I · Chapter - Dynamic Programming
    Apr 7
    Exam II · Practice Exam · Practice Exam Solutions
  13. Week 13

    Apr 10
    Dynamic Programming II · Chapter - Dynamic Programming
    SegmentLab due
    DPLab out
    Apr 11
    recitation SSSP with Dynamic Programming · Worksheet
    Apr 12
    Priority Queues and Leftist Heaps · Chapter - Priority Queues
    Apr 14
    Carnival - No Class
  14. Week 14

    Apr 17
    Hash Tables · Chapter - Hash Tables
    Apr 18
    recitation No Recitation
    Apr 19
    ??
    Apr 21
    TBD
  15. Week 15

    Apr 24
    Parallel Algorithms in Practice, Chapters 1-7 · Lecture Notes
    Apr 25
    recitation Examples in PASL · Worksheet · rec14.hpp · rec14-bench.cpp · Code Solutions
    Apr 26
    DPLab due
    PASLLab out
    Parallel Algorithms in Practice, Chapters 8-10 · Lecture Notes
  16. Week 16

    May 1
    Multithreading and Concurrency I · Lecture Notes
    May 2
    recitation Priority Queues and Leftist Heaps · Worksheet
    May 3
    Multithreading and Concurrency II · Lecture Notes
    May 5
    PASLLab due