CPSC 490 - Problem Solving in Computer Science

General Information

Meeting Time: 3-4PM, MWF
Location: FSC 1613 (across the street from ICICS)
Coordinators: Paul Liu, Kent Williams-King, Nasa Rouf
Faculty Sponsors: David Kirkpatrick and Will Evans

Proposal and Syllabus

Piazza Discussion Board

You can sign up for the discussion board here. I also post hints to the assignments on the board.


More information on the lectures will be filled out as we approach the lecture date.

Date Topics Lecturer Notes
1 1/5 Overview, I/O Paul IO, Slides
2 1/7 Intro to graphs, BFS Paul Graph Notes, Slides
3 1/9 Dijkstra’s algorithm Paul Graph Notes, Slides
4 1/12 MST, DFS Paul DFS Notes, Slides
5 1/14 DFS, Bellman-Ford Paul Bellman-Ford, Slides
6 1/16 Bellman-Ford, Inequality Feasiblity Paul Slides
7 1/19 Come to class for HWK Help Paul None
8 1/21 Floyd-Warshall, Dynamic Programming (DP) Kent DP Intro Notes
9 1/23 Homework 1 Due, Intro to DP Kent DP Intro Notes
10 1/26 Longest Increasing Subsequence Kent LIS Notes
11 1/28 LCS and Edit Distance Paul Slides, LCS Notes
12 1/30 Presentation Choice Due, Bitmask DPs Paul Bitmasks Intro, Bitmask DP, Slides
13 2/2 DPs and graphs Paul Slides
14 2/4 Student Presentations Paul None
15 2/6 Student Presentations Paul None
16 2/11 Student Presentations Nasa None
17 2/13 Student Presentations Nasa None
18 2/23 Matrix Expo, SQRT Decomp Paul Slides
19 2/25 SQRT Decomp, Offline Queries Paul Slides
20 2/27 Offline Queries, SQRT Decomp on Graphs Paul Slides
21 3/2 SQRT Decomp on Graphs, Segment Trees Paul Slides
22 3/4 Implementation of Segment Trees Paul Slides
23 3/6 BITs and O(1) queries Paul Slides
24 3/9 Geometric Primitives Nasa Slides
25 3/11 Convex Hulls Nasa Slides
26 3/13 Intersections and Distances Nasa Slides
27 3/16 Rotating Calipers Nasa Slides
28 3/18 Line Sweep Nasa Slides
29 3/20 Line Sweep Nasa Slides
30 3/23 Divide and Conquer, Search Problems Nasa Slides
31 3/25 Search, Network Flow Nasa, Paul Slides, Slides
32 3/27 Max-flow Min-cut Paul Slides, Notes
33 3/30 Student Presentations Paul None
34 4/1 Student Presentations Paul None
37 4/8 Student Presentations Paul None
38 4/10 Student Presentations Paul None


We will have two sets of student presentations throughout the semester. More information can be found here.

Update: The schedule for the second set of presentations is out! See here


Practice Problems Judge
Assignment 0 (IO Practice, Ungraded) Judge
Assignment 1 (Due Friday, January 23rd. Graded out of 100 marks) Written, Judge
Assignment 2 (Due Friday, Feb 20th. Graded out of 100 marks) Written, Judge
Assignment 3 (Due Wednesday, March 11th. Graded out of 100 marks) Judge
Assignment 4 (Due Sunday, March 29th. Graded out of 100 marks) Judge
Assignment 5 (Due Monday, April 13th. Graded out of 100 marks) Written, Judge

Other resources

Past Offerings of this course

Past CPSC 490

Similar Courses

Stanford - CS 97SI
CMU - 15-295

Online Judges

SPOJ Online Judge
USACO Training Gate