# Schedule Outline

• The detailed schedule is maintained on Canvas. Everything past the current week is subject to change.
• Exams are given on Canvas. Campus students must take them in CSB 110 on the friday of the week mentioned below. Online students will use the Respondus Lockdown browser.
• Recordings of the lectures are available on Canvas.
 Week Reading, Slides, Materials Worksheets, Programs, Quizzes, Exams 108/21 Welcome! Example Name Tag Info Algorithm Design, Kleinberg/Tardos, Chapter 1 Course Introduction, Representative Problems (Monday slides, Wednesday slides1 and slides2) Review CS 220 and prepare for review exam next week. Here's an open discrete math textbook. It has much of, but not all, the information from that class. How much do you remember? Take the Canvas quizzes on CS 220 prerequisites to help you prepare. Take the CS 220 final exam (Fri Aug 25, in CSB 110). 208/28 Introduction to Algorithms, Chapters 1.1-3.2 and Kleinberg/Tardos, Chapter 2 Orders of magnitude (slides) Line of Sight Algorithm (slides) Survey of common running times (slides) Study Python Tutorial, especially dictionaries. How much do you remember? Take the Canvas quizzes on CS 220 prerequisites to help you prepare. (Re) take the CS 220 final exam (Fri Sep 01, in CSB 110). Meet the team worksheet W0: StableMatching + counting review 309/04 Introduction to Algorithms, Chapter 6 Heaps and Heapsort 409/11 Introduction to Algorithms, Chapter 22 Graphs backup slides from 2022 509/18 Introduction to Algorithms, Chapter 16.1-16.3 Greedy Algorithms W5 Graphs Q4+WA1: Complexity, Orders of Magnitude 609/25 Introuction to Algorithms, Chapters 4.1, 4.3, 4.5 Divide & Conquer, Master Theorem Review W6 Greedy Midterm Exam 1 (Friday Sept. 29) 710/2 Midterm review Master Theorem/Solving Recurrences Programming Assignment 2: Heaps W7 Recurrences 810/9 Introduction to Algorithms, Chapters 23, 24 Minimum Spanning Trees, Shortest Paths Minimum Spanning Trees, Shortest Paths paper worksheet (not in Canvas) 910/16 Introduction to Algorithms, Chapter 33.4 Counting Inversions/TBD Closest Point Pair Polynomial Multiplication (Karatsuba) William's Lecture Notes (tar)) Q8: Divide and Conquer: Setting Up and Solving Recurrences 1010/23 Introduction to Algorithms, Chapter 15 Dynamic Programming: Recursive substructure, memoization, Weighted Interval Scheduling Knapsack & Memory-efficient Knapsack KPDP-full.xlsx KPDP-ME.xlsx W9 Weighted Interval Scheduling W9 Knapsack 1110/31 Memory-efficient Knapsack (concl) Review Q10: KnapSack W10 Belman Ford Midterm Exam 2 (Friday Nov. 3) 1211/6 Introduction to Algorithms, Chapter 24.1 Shortest Paths revisited: Bellman Ford (Introduction to Algorithms, Chapter 15.2) Introduction to Algorithms, Chapter 27 Dynamic Multi-Threading (aka Parallel Algorithms) W12 Dynamic Multi-Threading 1311/13 Parallel Scans (Prefix Sums), Reductions, and Fibonacci Prefix sum Programming Assignment 3: Counting Inversions W13 More DMT Fall Recess, Nov 18-26 1411/27 Introduction to Algorithms, Chapter 34.1-3 Polynomial time Reductions P, NP, and NP Completeness W14 Reductions Q14 DMT 1512/04 More P, NP, and NP Completeness Wrap up and recap W15 P & NP 1612/11 Final Exam Monday Dec 11 (CSB 110)