Course Description and Learning Objectives

This is a second course on algorithms and teaches you more advanced techniques in the design and analysis of algorithms. Broadly, after this course, a student will:

learn how randomization helps in the algorithmic design and paradigms (such as hashing/sampling)
learn basics of linear programming (LP), algorithms for LP, and the applications of LP in algorithms
learn basic + advanced combinatorial algorithms for flows and cuts, and their applications
learn basic NP-hardness and approximation algorithms

The course is theoretical and we will focus on the reason behind the algorithms. After this course, students will grow in the indefinable but essential quality of mathematical maturity. In particular, they will be ready to read SOTA research papers in algorithms.

Prerequisites

A first course in algorithms. For Dartmouth undergraduate students, CS31 suffices.
Students should know basic algorithmic design paradigms (sorting/searching/recursion/DP/DFS/BFS/shortest paths) and algorithm analysis concepts (Big-Oh notation/recurrence inequalities).
Mathematical Maturity. This is essential as the course will go at a faster pace. In particular,
- you should be able to read a "statement in Math" and understand what it means. You should be able to write down a logical argument in your mind as "statements in Math".
- you should have some basics covered, or you should have the ability to quickly pick it up. eg, "handshake lemma" in graphs, "linearity of expectation" or "modular arithmetic" or "basic linear algebra".
Check this "sample diagnostic test" to see if you are ready.

Logistics

Lectures: 3A+3AX hour. Mondays (3:30p - 6:20p) & Wednesdays (3:30p - 5:20p)
Problem Solving Sessions. Fridays (4:30p - 5:30p), ECSC 042
Class Venue: Maclean 132
Attendance: Mandatory
Work: exercises (some solutions), problems (some solutions, homework solutions) // these files will be constantly updated
Online Discussions: via Ed Discussion
Work Submissions: Gradesceope
Text/Lecture Notes: There is no single text book for this course, but we'll try to post lecture notes/relevant material.
Deliverables & Grades: class participation, problems sets, timed in-class tests. (click for more details)
Office Hours
- (deepc): Thursdays, 4:30p - 5:30p, ECSC 110
- (whit) Mondays, 1p - 2p, ECSC CTR 035 (will not occur on 10/5, there will be a make-up office hour on TBD)
Read this: Principle & Policies, CS 32/232, Fall 2026, AI Guidelines and Course AI Policy

(the schedule below is subject to changes)

**Tentative Weekly Schedule**
Date	Lecture Material	Relevant Problems	Related Notes
	Randomization
9/14	Introduction Monte-Carlo Algorithms, Equality Testing Las-Vegas Algorithms, Quick-Sort	E: 1-9 P: 1-6	Jupyter notebook to see the distribution of Quick Sort runtime
9/16	Estimation Algorithms Markov, Chebyshev	Weekly Summary 1 E: 10-16 P: 7-9
9/21	Hashing An Application in Geometry*	E: 17-24 P: 10-13	Jupyter notebook to play with Carter-Wegman
9/23	Chernoff Bounds "Median Trick" for Boosting Error	E: 25 - 30 P: 14 - 17 Weekly Summary 2	Jupyter notebook to play around with Chernoff bounds
9/28	A couple of classic randomized algos from the 90's Karger's Minimum Cut Algorithm Schoning's 3SAT Algorithm.	E: 31 - 38 P: 18 - 20
9/30	A 21st century example: Sublinear algorithms to estimate average degree of a graph	E: 39 - 41 Weekly Summary 3
	Optimization
10/5	Linear Program Basics: Algebra + Geometry (A quick refresher on linear algebra)	E: 42 - 50 P: 21 - 23
10/7	Generic Simplex algorithm	E: 51 - 53 Weekly Summary 4
10/12	Linear Programming Duality	E: 54 - 60 P: 24 - 30
10/14	"catch up": covered stuff from LP-duality, and odds-and-ends from the "basics of LP" notes of previous week	Weekly Summary 5
10/15	in-class test 1 time: 6:30p - 9:30p venue: cummings 200 (not usual classroom)
10/19	LP Duality, Zero Sum Games, Minimax Principle	E: 61-67 P: 31-32
10/21	NP-hardness Intro to Approximation Algorithms	E: 68 - 75 Weekly Summary 6
	Approximation
10/26	LP & Approximation: primal rounding + primal-dual algorithms
10/28	LP & Approximation: randomized rounding
11/2	Online Algorithms: Ski-Rental + Experts
11/4	Multiplicative Weight Update (MWU) method
11/9	in-class test time & venue: 3A hour in usual classroom
11/11	Streaming Algorithms
11/16

*hurriedly written notes -- possibly contains many errors

Consent to Record

We will try to record lectures. By enrolling in this course,

I affirm my understanding that the instructor may record meetings of this course in our classroom.
I further affirm that the instructor owns the copyright to their instructional materials, of which these recordings constitute a part, and my distribution of any of these recordings in whole or in part to any person or entity other than other members of the class without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including separation from Dartmouth.
Right to Privacy Policy

Accessibility Needs

Students requesting disability-related accommodations and services for this course are required to register with Student Accessibility Services (SAS; Apply for Services webpage; student.accessibility.services@dartmouth.edu; 1-603-646-9900) and to request that an accommodation email be sent to me in advance of the need for an accommodation. Then, students should schedule a follow-up meeting with me to determine relevant details such as what role SAS or its Testing Center may play in accommodation implementation. This process works best for everyone when completed as early in the quarter as possible. If students have questions about whether they are eligible for accommodations or have concerns about the implementation of their accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.