CS 3000 – Course Schedule (Fall 2026)

Topics and Agenda

This schedule is a tentative outline and will be updated regularly as the course progresses. Check back frequently. Lecture notes and/or slides will usually be posted after each lecture. Lectures meet Mon/Wed/Thu, 1:35–2:40pm, in Shillman Hall 105. Classes run from Wed, Sep 9 through Thu, Dec 10.

Part 1: Divide and Conquer and Analysis

(): Course Introduction and Logistics
(): Sorting and Mergesort
(): Asymptotic Analysis (Big-O, Ω, Θ)
(): Asymptotic Analysis (cont'd)
(): Karatsuba's Algorithm

Quiz 1 – Code tracing and induction (in lecture, Thu Sep 17)

(): Master Theorem and Recurrences
(): Selection and Order Statistics
(): Selection: Median of Medians

Homework 1 due (Fri, Sep 25)

Part 2: Dynamic Programming

(): Dynamic Programming Intro and Weighted Interval Scheduling

Quiz 2 – Recurrences (in lecture, Mon Sep 28)

(): Weighted Interval Scheduling (cont'd)
(): Knapsack
(): Knapsack (cont'd)
(): Segmented Least Squares
(): Sequence Alignment and Edit Distance

Quiz 3 – Dynamic programming / LCS (in lecture, Thu Oct 8)

Homework 2 due (Fri, Oct 9)

No class – Indigenous Peoples Day (Mon, Oct 12)

(): Longest Increasing Subsequence
(): Midterm 1 – covers Divide & Conquer and Dynamic Programming

Part 3: Greedy Algorithms

(): Greedy Algorithms: Interval Scheduling
(): Exchange Arguments
(): Huffman Codes

Homework 3 due (Fri, Oct 23)

Part 4: Graph Algorithms

(): Graphs and Depth-First Search
(): Topological Ordering and DAGs
(): Connectivity and Strongly Connected Components

Quiz 4 – Depth-first search (in lecture, Thu Oct 29)

(): Breadth-First Search and Shortest Paths
(): Dijkstra's Algorithm

Homework 4 due (Fri, Nov 6)

(): Dijkstra's Algorithm (cont'd)
(): Priority Queues (Heaps)

No class – Veterans Day (Wed, Nov 11)

(): Bellman-Ford
(): Minimum Spanning Trees
(): Minimum Spanning Trees (cont'd)

Quiz 5 – Minimum spanning trees (in lecture, Wed Nov 18)

(): Midterm 2 – covers Greedy Algorithms and Graph Algorithms

Part 5: Network Flow

(): Network Flow: Max-Flow / Min-Cut

Homework 5 due (Tue, Nov 24)

No class – Fall Break (Wed–Fri, Nov 25–27)

(): Ford-Fulkerson and Augmenting Paths
(): Max-Flow Min-Cut Theorem and Running Time
(): Flow Applications: Bipartite Matching

Quiz 6 – Network flow (in lecture, Thu Dec 3)

(): Cut Applications and More Flow Applications

Part 6: Intractability and Review

(): Intractability and NP-Completeness
(): Course Review and Final Exam Review – last day of class; practice problems for the final handed out

Homework 6 due (Fri, Dec 11)

Final Exam (30%): date/time TBD – scheduled by the Registrar during the fall final exam period (Dec 14–20, 2026). The final is in person and cumulative.

Recitations

Recitations are held on Zoom, Wednesdays 6:00–7:00pm (tentative – the confirmed link and time will be on Canvas), led by our student instructors. Each session works through a problem to build problem-solving skills and gives you real-time feedback. You are expected to attend.

Sessions run 60 minutes, except the two midterm-review sessions (Oct 14 and Nov 18), which run 90 minutes. Every recitation is recorded and posted, so you can catch up if you cannot make it live. If you would rather ask your question in person, come to TA or instructor office hours – those are held in person.

Recitations are not graded and carry no quiz. Quizzes are given in lecture instead (see the ✎ markers above), so recitation is a place to practice and ask questions with nothing at stake. Each session does one of three things:

Worksheet – work a problem live with your recitation instructor and get real-time feedback. Solutions are posted afterwards.
Quiz debrief – go over the most recent quiz, so you find out quickly what you did and did not understand.
Midterm review – the session before each midterm.

Recitation 1 (Wed, Sep 16): Proofs, induction and divide & conquer — worksheet 1
Recitation 2 (Wed, Sep 23): Asymptotics and code tracing — worksheet 2; Quiz 1 debrief
Recitation 3 (Wed, Sep 30): Recurrences and divide & conquer — worksheet 3
Recitation 4 (Wed, Oct 7): Dynamic programming — worksheet 4; Quiz 2 debrief
Recitation 5 (Wed, Oct 14): Midterm 1 review — worksheet 5 (90 min)
Recitation 6 (Wed, Oct 21): Greedy algorithms and exchange arguments — worksheet 6; Quiz 3 debrief
Recitation 7 (Wed, Oct 28): Topological ordering — worksheet 7
Recitation 8 (Wed, Nov 4): Depth-first search and strongly connected components — worksheet 8; Quiz 4 debrief
No recitation – Veterans Day (Wed, Nov 11)
Recitation 9 (Wed, Nov 18): Midterm 2 review — worksheet 9 (90 min)
No recitation – Fall Break (Wed, Nov 25)
Recitation 10 (Wed, Dec 2): Heaps, minimum spanning trees and Bellman-Ford — worksheet 10; Quiz 5 debrief
Recitation 11 (Wed, Dec 9): Min cuts and flow applications — worksheet 11; Quiz 6 debrief

Acknowledgements

Special thanks to Prof. Rajmohan Rajaraman and Prof. Jonathan Ullman, whose lectures, slides, and problem sets from earlier offerings of CS 3000 this course draws on heavily. The course is much better for their work.

Course material is derived in part from standard algorithms texts and courses, including Kleinberg & Tardos, Algorithm Design, and CLRS, Introduction to Algorithms.