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.
Lectures
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 |
Presentations
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
Assignments
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
Similar Courses
Stanford - CS 97SI
CMU - 15-295