Course Schedule

Lectures

1. Monday, Wednesday 11:00am - 12:20am, GHC 4401 (Rashid Auditorium) — Daniel Anderson, Danny Sleator

2. Main lectures are held on Monday and Wednesday, but we may also schedule activities (some compulsory) in the Friday slot. The three quizzes and the two midterm exams will be on Fridays during class time. Other Fridays may contain optional lectures, review sessions, etc.

Recitations

Recitation Attendance

You will register your attendance using a poll.

Topic/Assignment/Exam Schedule

1. Week 1

   Jan 12

   Mon

   Overview and Introduction [Notes] [Slides]

   Jan 13

   Tue

   recitation RefreshLab

    

    

   MCSSLab out

   Jan 14

   Wed

   Asymptotics and Recurrences [Notes] [Slides]

   Jan 15

   Thu

   RefreshLab due

   Jan 16

   Fri

   SML / C++ Review Session (Optional)

2. Week 2

   Jan 19

   Mon

   No Lecture (MLK Day)

   Jan 20

   Tue

   recitation Parenthesis Matching

    

    

   MCSSLab due

    

    

   ParenLab out

   Jan 21

   Wed

   Algorithm Design: Reductions, Greedy, Brute Force

3. Week 3

   Jan 26

   Mon

   Algorithm Design: Divide and Conquer and Contraction

    

    

   ParenLab due

   Jan 27

   Tue

   recitation Scan

    

    

   SkylineLab out

   Jan 28

   Wed

   Algorithm Design: Sequence-Based Algorithms

4. Week 4

   Feb 2

   Mon

   Algorithm Design: Dynamic Programming I

    

    

   SkylineLab due

   Feb 3

   Tue

   recitation Scan Reloaded

    

    

   WaffleLab out

   Feb 4

   Wed

   Algorithm Design: Dynamic Programming II

   Feb 6

   Fri

   Quiz 1

5. Week 5

   Feb 9

   Mon

   Probability for Randomized Algorithms

    

    

   WaffleLab due

   Feb 10

   Tue

   recitation Dynamic Programming

    

    

   DPLab out

   Feb 11

   Wed

   Randomized Algorithms I (Quickselect)

6. Week 6

   Feb 16

   Mon

   Randomized Algorithms II (Quicksort)

    

    

   DPLab due

   Feb 17

   Tue

   recitation Randomization I

   Feb 18

   Wed

   Midterm I Review

   Feb 20

   Fri

   Midterm I

7. Week 7

   Feb 23

   Mon

   Hashing and Hashtables

   Feb 24

   Tue

   recitation Randomization II & Hashing

    

    

   RandomLab out

   Feb 25

   Wed

   Binary Search Trees I

8. Spring Break

    

    

9. Week 8

   Mar 9

   Mon

   Binary Search Trees II (Treaps)

    

    

   RandomLab due

   Mar 10

   Tue

   recitation Treaps

   Mar 11

   Wed

   Augmented Binary Search Trees

   Mar 13

   Fri

   Quiz 2

10. Week 9

    Mar 16

    Mon

    Graph Search: DFS

     

     

    FingerLab due

    Mar 17

    Tue

    recitation Augmented Tables

     

     

    RangeLab out

    Mar 18

    Wed

    Graph Search: BFS

    Mar 20

    Fri

    Algorithm Design Review

11. Week 10

    Mar 23

    Mon

    Shortest Paths (Dijkstra's)

     

     

    RangeLab due

    Mar 24

    Tue

    recitation Graph Search

    Mar 25

    Wed

    Midterm II Review

    Mar 27

    Fri

    Midterm II

12. Week 11

    Mar 30

    Mon

    Shortest Paths (Bellman-Ford and Floyd-Warshall)

    Mar 31

    Tue

    recitation Shortest Paths

     

     

    CriticalLab out

    Apr 1

    Wed

    Graph Contraction I

13. Week 12

    Apr 6

    Mon

    Graph Contraction II

     

     

    CriticalLab due

    Apr 7

    Tue

    recitation Graph Contraction

14. Week 13

    Apr 13

    Mon

    MSTs (Boruvka's Algorithm)

     

     

    ShortLab due

    Apr 14

    Tue

    recitation MSTs

    Apr 15

    Wed

    Priority Queues

    Apr 17

    Fri

    Quiz 3

15. Week 14

    Apr 20

    Mon

    Parallel Scheduling

     

     

    SandwichLab due

    Apr 21

    Tue

    recitation Priority Queues

    Apr 22

    Wed

    Concurrency

    Apr 24

    Fri

    Final Review Session

16. Week 15

    TBD

     

    Final Exam