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 · Notes
    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 · Notes
    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 · Notes
    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 · Notes
    Mar 22
    Shortest Paths · Chapter - Shortest Paths
    Mar 24
    Randomized Algorithms for 3-SAT · Randomized 3-SAT
    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 · Notes
    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 · Notes
    Apr 5
    MSTs and Graph Algorithms Review · Chapter - Minimum Spanning Trees
    Apr 7
    Exam II · Practice Exam · Practice Exam Solutions

  13. Week 13

    Apr 10
    Dynamic Programming I · Chapter - Dynamic Programming
    Apr 11
    recitation SSSP with Dynamic Programming · Worksheet · Notes
    Apr 12
    Dynamic Programming II · Chapter - Dynamic Programming
    Apr 14
    Parallel Dynamic Programming (optional)
    SegmentLab due
    DPLab out

  14. Week 14

    Apr 17
    Priority Queues and Leftist Heaps · Chapter - Priority Queues
    Apr 18
    recitation Priority Queues and Leftist Heaps · Worksheet · Notes
    Apr 19
    Hash Tables · Chapter - Hash Tables
    Apr 21
    Carnival - No Class

  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 · Notes · Code Solutions
    DPLab due
    PASLLab out
    Apr 26
    Parallel Algorithms in Practice, Chapters 8-10 · Lecture Notes

  16. Week 16

    May 1
    Multithreading and Concurrency I · Lecture Notes
    May 2
    recitation TBD
    May 3
    Topic Review
    May 5
    PASLLab due

  17. Week 17

    May 10
    Review Session (4PM-6PM, GHC 4401)
    May 12
    Final Exam (1:00PM-4:00PM) · Practice Exam · Practice Exam Solutions