Course Schedule

Lectures

  1. MWF 10:30am - 11:50am GHC 4401 — Umut Acar, Robert Harper
  2. Monday and Wednesday Main Lectures, Friday Review Lecture

Recitations

A Tue 09:30am - 10:20am DH 2122 Andra, Charlie
B Tue 10:30am - 11:20am BH 255A Andres, Emma
C Tue 11:30am - 12:20pm WEH 5310 Anatol, John
D Tue 12:30pm - 01:20pm SH 208 Aashir, Ashwin
E Tue 01:30pm - 02:20pm WEH 8427 Nathaniel, Sonya
F Tue 03:30pm - 04:20pm WEH 5310 Teddy, Vivek
G Tue 04:30pm - 05:20pm WEH 5310 Alex, Patrick

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 29
    Mathematical Preliminaries · Chapter - Preliminaries
    SPARC - A Strict Functional Language for Parallel Computing · Chapter - SPARC
    Overview and Introduction · Chapter - Introduction
    ParenLab out
    Aug 30
    recitation Parentheses Matching · Worksheet · Notes
    Aug 31
    Algorithm Analysis · Chapter - Algorithm Design and Analysis
    Sep 2
    Genome Sequencing · Chapter - Genome Sequencing
  2. Week 2

    Sep 5
    Labor Day - No Lecture
    Sep 6
    recitation TBA
    Sep 7
    Sequences I · Chapter - Sequences
    Sep 9
    Practice of Parallelism
    ParenLab due
    SkylineLab out
  3. Week 3

    Sep 12
    Sequences II · Chapter - Sequences
    Sep 13
    recitation Scan · Worksheet · Notes
    Sep 14
    Contraction & Divide-and-Conquer · Chapter - Contraction · Chapter - Divide and Conquer
    Sep 16
    Online Resource Allocation (Optional) · Notes
    SkylineLab due
    BignumLab out
  4. Week 4

    Sep 19
    Maximum contiguous subsequence problem · Chapter - Maximum contiguous subsequence problem
    Sep 20
    recitation Scan Reloaded · Worksheet · Notes
    Sep 21
    Randomized Algorithms · Chapter - Randomized Algorithms
    Sep 23
    Randomized algorithms for 3-SAT (optional) · Notes
    BignumLab due
    RandomLab out
  5. Week 5

    Sep 26
    Quicksort · Chapter - Randomized Algorithms
    Sep 27
    recitation Randomization · Worksheet · Notes
    Sep 28
    Binary Search Trees and Treaps I · Chapter - Binary Search Trees and Treaps
    Sep 30
    Exam I · Practice Exam · Practice Exam Solutions
    FingerLab out
  6. Week 6

    Oct 3
    Binary Search Trees and Treaps II · Chapter - Binary Search Trees and Treaps
    Oct 4
    recitation Treaps · Worksheet · Notes
    Oct 5
    Binary Search Trees and Treaps III · Chapter - Binary Search Trees and Treaps
  7. Week 7

    Oct 10
    Sets and Tables · Chapter - Sets and Tables
    Oct 11
    recitation Generalized BST Combinations (and Exam Debrief) · Worksheet · Notes
    Oct 12
    Sets and Tables and Graphs · Chapter - Sets and Tables · Chapter - Graphs and their Representation
    Oct 14
    Intro to Machine Learning (Optional)
    FingerLab due
    RangeLab out
  8. Week 8

    Oct 17
    Graph Search and BFS · Chapter - Graph Search
    Oct 18
    recitation Intervals with Augmented Tables · Worksheet · Notes
    Oct 19
    DFS and Applications · Chapter - Graph Search
    Oct 21
    Mid-Semester Break - No Lecture
    RangeLab due
    BridgeLab out
  9. Week 9

    Oct 24
    Shortest Paths · Chapter - Shortest Paths
    Oct 25
    recitation Graph Search · Worksheet · Notes
    Oct 26
    Shortest Paths · Chapter - Shortest Paths
    Oct 28
    No lecture today
    BridgeLab (written) due
    ShortLab out
  10. Week 10

    Oct 30
    BridgeLab (programming) due
    Oct 31
    Graph Contraction I · Chapter - Graph Contraction
    Nov 1
    recitation Shortest Paths · Worksheet · Notes
    Nov 2
    Graph Contraction II · Chapter - Graph Contraction
    Nov 4
    Machine Learning II - Growth Function and VC-dimension (Optional)
    ShortLab due
    SegmentLab out
  11. Week 11

    Nov 7
    Minimum Spanning Trees · Chapter - Minimum Spanning Trees
    Nov 8
    recitation Graph Contraction and MSTs · Worksheet · Notes
    Nov 9
    Dynamic Programming I · Chapter - Dynamic Programming
    Nov 11
    Exam II · Practice Exam · Practice Exam Solutions
  12. Week 12

    Nov 14
    Dynamic Programming II · Chapter - Dynamic Programming
    SegmentLab due
    Nov 15
    recitation SSSP with Dynamic Programming · Worksheet · Notes
    Nov 16
    Dynamic Programming III (short lecture) · Chapter - Dynamic Programming
    Nov 18
    DPLab out
  13. Week 13

    Nov 21
    Hash Tables · Chapter - Hash Tables
    Nov 22
    recitation Hashing · Worksheet · Notes
    Nov 23
    Priority Queues and Leftist Heaps · Chapter - Priority Queues
    Nov 25
    Carnival - No Lecture
  14. Week 14

    Nov 28
    Parallel Algorithms in Practice, Chapters 1,2,3,4 · Lecture Notes
    DPLab due
    PASLLab out
    Nov 29
    recitation Priority Queues · Worksheet · Notes
    Nov 30
    Parallel Algorithms in Practice, Chapters 6,7 · Lecture Notes
    Dec 2
    Fun with Hashing (Optional)
  15. Week 15

    Dec 5
    Parallel Algorithms in Practice, Chapters 8,9 · Lecture Notes
    Dec 6
    recitation Examples in PASL · Worksheet · rec15.hpp · rec15-bench.cpp · Notes · Code Solutions
    Dec 7
    Parallel Algorithms in Practice, Chapter 10 · Lecture Notes
    Dec 9
    No class today
    PASLLab due
  16. Week 16

    Dec 14
    Review Session (7pm, Rashid Auditorium)
    Dec 16
    Final Exam (1PM-4PM) · Practice Exam · Practice Exam Solutions