[ news | information | syllabus | links ]

CS140 - Spring 2020

TR 9:35am-10:50am (section 1) and 11:00am-12:15pm (section 2) in Edmunds 101
Prof. Chen and Prof. Kauchak
TAs: Marcel Alfonso Garcia, Gabriel Alzate, Grete Helena Kutt, Thuan Nguyen, Levente Papp


We will be using Piazza for distributing problem sets, posting lecture notes, making announcements, etc. Please make sure that you're signed up for this course! If you aren't, let one of the professors know. The piazza page is here.


CS140 is an introduction to algorithm design and analysis techniques. The course covers basic techniques used to analyze algorithms, basic techniques used in designing algorithms, and important classical algorithms. The goal is to learn how to apply all of the above to designing solutions for real-world problems (a skill that you will practice throughout the semester). Grades will be based primarily on problem sets and exams, with participation factoring in a small amount.

The prerequisites for the class are cs54 and cs62. Talk to one of the professors if you have questions about these requirements.

The textbook is Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, and Stein. Copies are available at Huntley bookstore.


Any topic/readings/assignments that are listed for a date in the future should be taken as (potentially very) tentative. Readings/assignments will be updated by the preceding class; lecture topics will be updated by the following class.

Week Date In class topic(s) Readings (CLRS) Assignment due
1 (Tue) 1/21 intro
review (asymptotics, proofs - direct, contradiction, style)
(Thu) 1/23 review (proofs - induction)
insertion sort
2, 3 ps1
2 (Tue) 1/28 mergesort
average case analysis
4.3-4.5 ps2
(Thu) 1/30 master method
average case analysis
4.2, 7 ps3 - part 1
3 (Tue) 2/4 order statistics 9 ps3 - part 2 - coding
(Thu) 2/6 bounding problems
lower bounds on sorting
linear time sorts
4 (Tue) 2/11 review (basic data structures)
6, 10 ps4
(Thu) 2/13 amortized analysis 17 ps5
5 (Tue) 2/18 (balanced) binary search trees 12, 13 ps6
(Thu) 2/20 other data structures
6 (Tue) 2/25 checkpoint 1
(Thu) 2/27 optimal substructure, greedy choice property
greedy algorithms: change, activity scheduling
16 ps8
7 (Tue) 3/3 dynamic programming: fibonacci,
longest common subsequence, matrix multiplication
15 ps9
(Thu) 3/5 dynamic programming: rod splitting, 0-1 knapsack
15 ps10
8 (Tue) 3/10 dynamic programming continued 15 ps11 - part 1
(Thu) 3/12 linear programming 29 ps11 - part 2 (coding)
(Tue) 3/17 spring break
(Thu) 3/19
(Tue) 3/24 spring break #2
(Thu) 3/26
10 (Tue) 3/31 review: graphs, trees, traversals
topological sort
strongly connected components
B.4-B.5, 22  
(Thu) 4/2 single source shortest paths:
Bellman-Ford, Dijkstra's
11 (Tue) 4/7 all pairs shortest paths:
Johnson's, Floyd-Warshall
25 ps12
(Thu) 4/9 minimum spanning trees: Kruskal's, Prims 23  
12 (Tue) 4/14 network flow 26 ps13
(Thu) 4/16 checkpoint 2
13 (Tue) 4/21 maximum bipartite matching
26, 34 ps14
(Thu) 4/23 NP-completeness reductions 34  
14 (Tue) 4/28 more NP-completeness reductions 34 ps15
(Thu) 4/30 more NP-completeness reductions 35  
15 (Tue) 5/5 approximation algorithms ps16

The final exam time is Thursday, May 14th from 2-5pm7


  • web site for the textbook. Note the list of errata.
  • complexity:
  • complexity zoo
  • NP compendium

  • "Computers do not solve problems, they execute solutions"
    --Laurent Gasser