Spring 2024 CS231

This is a course about algorithms; their design and analysis

About CS231


The language of computer science is to a great extent the language of algorithms. Although there are many thousands of algorithms, there are relative few basic design techniques. These include: divide-and-conquer, greedy, dynamic programming, and network flow. We will illustrate these techniques by studying a few fundamental algorithms of each type. In addition to helping us understand classic solution techniques, these algorithms have proven very useful in practice. Their names and the names of the problems they solve have become a standard part of the language of computer science.

Unfortunately, there is rarely a best algorithm to solve a given problem. Each approach involves a series of tradeoffs. Therefore, we will also study methods for evaluating the usefulness of an algorithm in a given situation. Among the various competing measures, we will focus primarily on the anal- ysis of time and space complexity. However, a number of other issues will also be discussed.

Meet your instructors & tutors

Click here for CS231 support calendar


Instructors

Christine Bassem
Office hours:
Wednesday and Thursday 1pm-2:30pm


Tutors

Wednesday TA: Sally Kim
Drop-in tutors:
Karen Xiao
Emily Suh
Kaitlyn Tsien
Yiduo Wang

CS231 Syllabus


All course info and logistics can be found in the course syllabus

CS231 Schedule


Please note that this page will be updated frequently, and it will contain all course content and resources
Monday Tuesday Wednesday Thursday Friday
Jan
22
Introduction and Review
(slides)
Reading: Course syllabus
23
24
(I) Basics:
Complexity analysis
(stubs)
25
Priority queues and heaps
(slides)
Optional Reading: Section 2.5
Assignment 0 due at 11:59pm (pdf file - tex file)
26
29
Analysis and asymptotics
(slides)
Reading: Sections 2.1 and 2.2
30
31
Analysis and asymptotics
(activity)
Reading: Sections 2.1 and 2.2
Feb
1
Stable matching (1)
(slides)
2
5
Stable matching (2)
(slides - stubs)
6
7
Stable matching (3)
8
(II) Graphs: Definitions and representation
(slides)
Assignment 1 due at 11:59pm (pdf file - tex file)
9
12
BFS
(slides)
13
14
BFS
(activity)
15
DFS
(slides)
16
19
No classes
20
DAGs and Topological ordering
(slides)
21
(III) Greedy algorithms:
Interval Scheduling
(slides - lookahead proof)
22
Review graphs
(activity)
Assignment 2 due at 11:59pm (pdf file - tex file - starter code)
23
26
Scheduling (2) and exchange argument
(slides)
27
28
Exam 1 in-class
Focuses on material till end of DFS
29
Exchange argument 2
(proof)
Mar
1
4
Shortest path routing
(slides)
5
6
Review proofs
7
Minimum spanning trees
(slides)
8
11
(IV) Divide and Conquer:
Merge sort
(sort slides - recurrence slides)
12
13
Solving Recurrences
14
Counting Inversions
(slides)
No class - watch videos shared on Piazza
Assignment 3 due at 11:59pm (pdf file - tex file)
15
18
Spring break
19
Spring break
20
Spring break
21
Spring break
22
Spring break
25
(V) Dynamic programming:
Weighted interval scheduling
(slides - activity)
26
27
Jillian Amaral talk
Final paper description
28
Exam 2 in-class
Focuses on material till end of greedy
29
Apr
1
Knapsack
(slides)
2
3
Knapsack practice
(activity)
4
Shortest path revisited
( slides / activity)
5
8
(VI) Max Flow:
Max Flow problem (1)
(slides)
9
10
Max Flow problem (2)
11
Rhulman - No classes
Assignment 4 due at 11:59pm (pdf file - tex file)
12
15
No classes
16
17
Review dynamic programming
18
Applications of Max Flow
(slides)
19
22
Tractability of algorithms
(slides)
23
24
TBD
25
Guest lecture by Brian Brubach
Assignment 5 due at 11:59pm (pdf file - tex file)
26
29
Exam 3 in-class
Covers remaining material
30
May
1
In-class presentations
2
Reading period starts