Course Description and Learning Objectives

This is a course which teaches the basics of design and analysis of algorithms. Simply put, an algorithm is a step-by-step procedure to solve a problem, and forms the bedrock of computer science. The learning objectives of this course are:

describe an algorithm precisely and succinctly
analyze the correctness and efficiency (running times) of algorithms
learn some basic algorithmic techniques and some classic algorithms for fundamental problems
use the above knowledge to adapt them for solving different problems
design new algorithms

From a computer science perspective, the above objectives will make a student better problem solvers and programmers. Although the course is primarily theoretical, there are avenues for programming where students can hone their coding skills.

Logistics

Prerequisites: COSC 30 or equivalent. See this.
Lectures: 9L hour (M-W-F, 8:50 - 9:55, X-hour on Th, 9:05-9:55)
Class Venue: Cummings 100 (Spanos Auditorium)
Discussions: via Ed Discussion
Work Submissions: (mostly) Gradescope
Textbook: Lecture notes and plenty of practice problems (with solutions) will be posted. No particular textbook needed, but these are good:
- Erickson: Algorithms (this is freely available here: https://jeffe.cs.illinois.edu/teaching/algorithms/ )
- Dasgupta, Papadimitriou, Vazirani: Algorithms
- Roughgarden: Algorithms Illuminated
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
- Kleinberg, Tardos: Algorithm Design
Read these:

Evaluation

(tl;dr) weekly problem sets (45%) and three "in-class" exams (55%), with lots of extra credit options. Details: see Deliverables and Evaluation

Tentative Weekly Schedule
Date	Lecture Material	Exercises/Problems	Other Info
6 Jan (Mon)	Introduction; Writing Algos		W1 problems and (some) solutions released
8 Jan (Wed)	Big Oh Notation	W1: P1- P10
10 Jan (Fri)	More Big-Oh Notation Analysis of For/While Loops	W1: P11-P17	Over zoom (Meeting ID: 949 3742 4109, Passkey: algorithms)
13 Jan (Mon)	Binary Search, Runtime Analysis, Recurrence Inequalities	W2: P1-P9	W2 problems and (some) solutions released
15 Jan (Wed)	DC1: Merge-Sort + Master Theorem	W2: P10-19	Supplement: Proof of Master Theorem, Ceilings & Floors, and the Grandmaster Theorem Even better: See Theorem 3.4 of this (quite recent) paper.
16 Jan (X-hour)	(catch up) Master Theorem: applying it, and a little bit on "why"
17 Jan (Fri)	DC2: Counting Inversions	W3: P1-13	W3 problems and (some) solutions released
20 Jan (Mon)	MLK Day, class moved to X-hours
22 Jan (Wed)	DC3: Polynomial Multiplication	W3: P14 - 16	Extra materials: (1) Even faster polynomial multiplication: FFT (video) (2) Faster Matrix Multiplication (video)
23 Jan (X)	DC4: Finding Median in Linear Time
24 Jan (Fri)	DC5: Closest Points on a Plane	W3: P17
27 Jan (Mon)	DP1: Basics, Smart Recursion	W4+5: 1-2	W4+5 problems and (some) solutions released
29 Jan (Wed)	DP2: Subset Sum
30 Jan (Thu)	Midterm 1 (Time): 6:40p - 9:40p (Venue): Cummings 100 (usual classroom)		Syllabus: (Big-Oh, Analyzing runtimes, Master Theorem, Sorting/Searching, Divide & Conquer) Relevant problems: all problems in W1, W2 and W3 problems 1-13
31 Jan (Fri)	DP2: Subset Sum
3 Feb (Mon)	DP3: Knapsack	W4+5:3-10
5 Feb (Wed)	DP4: Edit Distance	W4+5:11-20
7 Feb (Fri)	DP5: Longest Increasing Subsequence		A video about the faster implementation

10 Feb (Mon)	Graph Algorithms: Intro	W6:1-7	W6 problems and (some) solutions released
12 Feb (Wed)	DFS1: Algorithm
13 Feb (X)	DFS2: Properties	W6:8-12	Over zoom (Meeting ID: 949 3742 4109, Passkey: algorithms)
14 Feb (Fri)	DFS3: Cycles & Strong Connectivity in Linear Time
17 Feb (Mon)	DFS4: Top Sort & DP on DAGs	W6:13-18
19 Feb (Wed)	DFS5: Longest path in a DAG
20 Feb (Thu)	Midterm 2 (Time): 6:40p - 9:40p (Venue): Cummings 100 (usual classroom)		Syllabus: (Dynamic Programming, Graphs: DFS) Relevant problems: all problems in W4+5 and W6 problems 1-12
21 Feb (Fri)	SSSP1: Distance Labels & Generic Algo	W7: 1-2	W7 problems and (some) solutions released
24 Feb (Mon)	SSSP2: BFS	W7: 3-8
26 Feb (Wed)	SSSP3: BFS proofs + Dijkstra	W7: 9-15
27 Feb (X)	SSSP4: Dijkstra runtime + Priority Queues
28 Feb (Fri)	SSSP5: Bellman-Ford	W7: 16-20
3 Mar (Mon)	MST1: Intro, Cut-Crossing Prop; Prim's Algorithm		W9 problems and (some) solutions released
5 Mar (Wed)	MST2: Boruvka's Algo
6 Mar (X)	MST3: Kruskal's Algo + Union-Find
7 Mar (Fri)	Review + Looking Ahead + AMA		TLDR.pdf
11 Mar (Tue)	Finals (Time): 3p - 6p (Venue): Cummings 100 (usual classroom)		Cumulative

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.

Religious Observances

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me before the end of the second week of the term to discuss appropriate accommodations.