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 Design and Analysis · Chapter - Algorithm Design and Analysis
    Sep 2
    Algorithm Design and Analysis · Chapter - Genome Sequencing

  2. Week 2

    Sep 5
    Labor Day - No Lecture
    Sep 6
    recitation Solving Recurrences · Worksheet · Notes
    Sep 7
    Genome Sequencing · Chapter - Genome Sequencing
    Sep 9
    Practice of Parallelism · Parentheses Matching
    ParenLab due
    SkylineLab out

  3. Week 3

    Sep 12
    Sequences I · Chapter - Sequences
    Sep 13
    recitation Scan · Worksheet · Notes
    Sep 14
    Sequences II · Chapter - Sequences
    Sep 16
    Contraction & Divide-and-Conquer · Chapter - Contraction · Chapter - Divide and Conquer
    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
    Probability Theory · Chapter - Probability Theory
    Sep 23
    BignumLab due
    RandomLab out

  5. Week 5

    Sep 26
    Probability Theory · Chapter - Probability Theory
    Analysis of Randomized Algorithms · Chapter - Analysis of Randomized Algorithms
    Sep 27
    recitation Randomization · Worksheet · Notes
    Sep 28
    Analysis of Randomized Algorithms · Chapter - Analysis of Randomized Algorithms
    Sep 30
    Quicksort Analysis Review · Chapter - Analysis of Randomized Algorithms
    RandomLab due
    FingerLab out

  6. Week 6

    Oct 3
    Binary Search Trees and Treaps I · Chapter - Binary Search Trees and Treaps
    Oct 4
    recitation Treaps · Worksheet · Notes
    Oct 5
    Binary Search Trees and Treaps II · Chapter - Binary Search Trees and Treaps
    Oct 7
    Exam I · Practice Exam · Practice Exam Solutions

  7. Week 7

    Oct 10
    Sets and Tables I · Chapter - Sets and Tables
    Oct 11
    recitation Generalized BST Combinations (and Exam Debrief) · Worksheet · Notes
    Oct 12
    Sets and Tables II · Chapter - Sets and Tables
    Oct 14
    FingerLab due
    RangeLab out

  8. Week 8

    Oct 17
    Graphs, Graph Search, and BFS · Chapter - Graphs and their Representation · 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
    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
    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
    DPLab out
    Nov 15
    recitation SSSP with Dynamic Programming · Worksheet · Notes
    Nov 16
    Priority Queues and Leftist Heaps · Chapter - Priority Queues

  13. Week 13

    Nov 21
    Hash Tables · Chapter - Hash Tables
    Nov 22
    recitation No Recitation
    Nov 23
    Thanksgiving Break
    Nov 25
    Thanksgiving Break

  14. Week 14

    Nov 28
    Parallel Algorithms in Practice, Chapters 1-7 · Lecture Notes
    Nov 29
    recitation Examples in PASL · Worksheet · rec14.hpp · rec14-bench.cpp · Notes · Code Solutions
    Nov 30
    DPLab due
    PASLLab out
    Parallel Algorithms in Practice, Chapters 8,9,10 · Lecture Notes

  15. Week 15

    Dec 5
    Multithreading and Concurrency I · Lecture Notes
    Dec 6
    recitation Priority Queues and Leftist Heaps · Worksheet · Notes
    Dec 7
    Multithreading and Concurrency II · Lecture Notes
    Dec 9
    PASLLab due

  16. Week 16

    Dec 11
    Review Session (4PM-6PM, GHC 4401)
    Dec 13
    Final Exam (5:30PM-8:30PM) · Practice Exam · Practice Exam Solutions