Course Schedule

Lectures

  1. MWF 9:30am - 10:50am, GHC 4401 (Rashid Auditorium) — Charlie Garrod, Guy Blelloch

  2. Lectures are typically just on Monday and Wednesday, but there will be a couple on Friday. The two midterm exams will be on Fridays during class.

Recitations

A Tue 9:00am - 9:50am WEH 6403 Avantika, Ivy
B Tue 10:00am - 11:50am WEH 4708 Saaketh, Lukas
C Tue 10:00am - 10:50am WEH 6403 Edward, Tony
D Tue 11:00am - 11:50am PH 225B Aditya, Karthik
E Tue 2:00pm - 2:50pm PH 226B James, Audi
F Tue 1:00pm - 1:50pm PH 225B Jocelyn, Amruta
G Tue 2:00pm - 2:50pm WEH 8427 Juliet, Jason
H Tue 3:00pm - 3:50pm WEH 8427 Ananya, Crystal
I Tue 4:00pm - 4:50pm DH 1117 Ronnie, Jonathan
J Tue 5:00pm - 5:50pm WEH 4708 Tom, Vishant
K Tue 10:00am - 10:50am PH A18A Jessica, Matthew
L Tue 4:00pm - 4:50pm PH A18B Cole, Alex

Recitation Attendance

You will register your attendance using a poll.

Topic/Assignment/Exam Schedule

  1. Week 1

    Aug 25
    Overview and Introduction
    Book Readings · Introduction · Parallelism · Genome Sequencing
    Aug 26
    recitation Refresh Lab out · Refresh Lab
    MCSSLab out · MCSSLab
    Quiz 0 out · Quiz 0
    Aug 27
    Asymptotics and Recurrences
    Book Readings · Introduction · Asymptotics · Recurrences
    Aug 28
    Refresh Lab due
    Quiz 0 due
    Quiz 1 out · Quiz 1
    Aug 29
    SML Review (Optional)

  2. Week 2

    Sep 1
    No Lecture (Labor Day)
    Sep 2
    recitation Parentheses Matching
    MCSSLab due
    ParenLab out · ParenLab
    Sep 3
    Cost Models
    Book Readings · Cost Models
    Sep 4
    Quiz 1 due
    Quiz 2 out
    Sep 5
    Sequences I
    Book Readings · Sequence Introduction · The Sequence ADT · Array Sequences · Sequence Costs

  3. Week 3

    Sep 8
    Sequences II
    Book Readings · The Sequence ADT · Array Sequences · Sequence Costs · Single Threaded Sequences
    ParenLab due
    SkylineLab out · SkylineLab
    Sep 9
    recitation Scan
    Sep 10
    Algorithm Design Techniques I · Algorithm Design
    Sep 11
    Quiz 2 due
    Quiz 3 out
    Sep 12
    No Lecture

  4. Week 4

    Sep 15
    Algorithm Design Techniques II · Algorithm Design
    SkylineLab due
    WaffleLab out · WaffleLab
    Sep 16
    recitation Scan Reloaded
    Sep 17
    Probability Theory · Probability
    Sep 18
    Quiz 3 due
    Sep 19
    No Lecture

  5. Week 5

    Sep 22
    Randomized Algorithms I · Introduction · Quick Select
    WaffleLab due
    RandomLab out · RandomLab
    Sep 23
    recitation Randomization I
    Sep 24
    Midterm I Review Session · Review and Practice Exams
    Sep 26
    Midterm I
    Quiz 4 out

  6. Week 6

    Sep 29
    Randomized Algorithms II · Quicksort
    Sep 30
    recitation Randomization II
    Oct 1
    Binary Search Trees I · Introduction · Generic Interface
    Oct 2
    Quiz 4 due
    Quiz 5 out
    Oct 3
    Exam Solution Session (Optional)

  7. Week 7

    Oct 6
    Binary Search Trees II · Treaps
    RandomLab due
    FingerLab out · FingerLab
    Oct 7
    recitation Treaps
    Oct 8
    Augmented Trees + Sets/Tables · Augmented Trees · Sets · Tables
    Oct 9
    Quiz 5 due
    Quiz 6 out
    Oct 10
    No Lecture

  8. Week 8

    Oct 13
    No Lecture (Fall Break)

  9. Week 9

    Oct 20
    Graphs and Graph Search · Graphs and their Representation
    RangeLab out · RangeLab
    Oct 21
    recitation Augmented Tables
    FingerLab due
    Oct 22
    Graph Search and BFS · Graph Search · Breadth First Search
    Oct 23
    Quiz 6 due
    Quiz 7 out
    Oct 24
    No Lecture

  10. Week 10

    Oct 27
    DFS · Depth First Search
    RangeLab due
    CriticalLab out · CriticalLab
    Oct 28
    recitation Graph Search
    Oct 29
    Shortest Paths I · Introduction to Shortest Paths · Dijkstra's Algorithm
    Oct 30
    Quiz 7 due
    Oct 31
    Shortest Paths II · Bellman Ford's Algorithm · Johnson's Algorithm

  11. Week 11

    Nov 3
    Graph Contraction I · Introduction Graph Contraction · Edge Conctraction
    CriticalLab due
    ShortLab out · ShortLab
    Nov 4
    recitation Shortest Paths
    Nov 5
    Midterm II Review · Review and Practice Exams
    Nov 7
    Midterm II
    Quiz 8 out

  12. Week 12

    Nov 10
    Graph Contraction II · Star Conctraction · Graph Connectivity
    Nov 11
    recitation Graph Contraction
    Nov 12
    Minimum Spanning Trees (MST) · Introduction to MSTs · Sequential MST Algorithms · Parallel MST Algorithm - Boruvka
    Nov 13
    Quiz 8 due
    Quiz 9 out
    Nov 14
    Exam Solutions Session (Optional)

  13. Week 13

    Nov 17
    Dynamic Programming I · Introduction to Dynamic Programming · Subset Sum and Min Edit Distance
    ShortLab due
    SandwichLab out · SandwichLab
    Nov 18
    recitation MSTs
    Nov 19
    Dynamic Programming II · Implementing Dynamic Programming
    Nov 20
    Quiz 9 due
    Quiz 10 out
    Nov 21
    No Lecture

  14. Week 14

    Nov 24
    Priority Queues · Priority Queues (Leftist Heaps)
    SandwichLab due
    DPLab out · DPLab
    Nov 25
    recitation Dynamic Programming
    Nov 26
    No Lecture (Thanksgiving)

  15. Week 15

    Dec 1
    DP with Concurrency
    Dec 2
    recitation Priority Queues
    Dec 3
    Some sequential algorithms are almost always parallel
    DPLab due
    Dec 4
    Quiz 10 due
    Dec 5
    Final Review Session (Optional)