CPSC 490 - Problem Solving in Computer Science
General Information
| Section | Time | Room | Coordinators |
|---|---|---|---|
| 202 | TTh 11am-12:30pm | ORCH 3062 | David Zheng, Daniel Du |
Proposal and Syllabus
Piazza Discussion Board
You can sign up for the discussion board here. We will post hints to the assignments on the board.
Lectures
Schedule is subject to change. Slides and notes will be uploaded before lectures.
| # | Week | Date | Topics | Slides | Notes |
|---|---|---|---|---|---|
| 1 | Week 1 | 1/4 | Intro: Overview, I/O, Floating Point | Slides | IO, Floating point |
| 2 | Week 2 | 1/9 | Graph #1: Intro, BFS, DFS, Floyd-Warshall, Dijkstra, Bellman-Ford | Slides | Graph Basics, DFS, Bellman-Ford |
| 3 | 1/11 | Graph #2: Trees, MST, Union find, Euler tour | Slides | ||
| 4 | Week 3 | 1/16 | Graph #3: BCC, SCC, 2-SAT | Slides | |
| 5 | 1/18 | DP #1: Intro, LIS, Knapsack | Slides | DP Intro, LCS LIS/Knapsack | |
| 6 | Week 4 | 1/23 | DP #2: Backtracking, Bitmask DP, Matrix Exponentiation | Slides |
Bitmasks Intro,
Bitmask DP,
Matrix Exponentiation, DP Optimizations (optional) |
| 7 | 1/25 | DP #3: LCS, KMP, tries | Slides | String notes (relevant sections) | |
| 8 | Week 5 | 1/30 | DP #4: Binary jumping, Tree DP, LCA Query, Graph DP | Slides | Tree DP |
| 9 | 2/1 | Query #1: LCA (cont.) SQRT Decomposition, Offline Queries | Slides | Sqrt Decomposition of Queries (Mo's) | |
| 10 | Week 6 | 2/6 | Query #2: Euler Tour Trees, Homework help | Slides | Euler Tour Tree |
| 11 | 2/8 | Query #3: Binary index tree, Segment Tree | Slides | Segment Tree | |
| Week 7 | 2/13 | Presentation #1 | |||
| 2/15 | Presentation #1 | ||||
| Reading Week (2/19-2/23) | |||||
| Week 9 | 2/27 | Homework Help | |||
| 12 | 3/1 | Geometry #1: Geometric Primitives | Slides |
Computational Geometry (relevant sections) |
|
| 13 | Week 10 | 3/6 | Geometry #2: Binary search, Ternary Search, Convex Hull | Slides | |
| 14 | 3/8 | Geometry #3: Rotating Calipers | Slides | ||
| 15 | Week 11 | 3/13 | Geometry #4: Line Sweep | Slides | |
| 16 | 3/15 | Number Theory: Primes, Intro to number theory, Extended Euclidian Algorithm | Slides | ||
| 17 | Week 12 | 3/20 | Flow #1: Maximum Flow | Slides | |
| 18 | 3/22 | Flow #2: Maximum Bipartite Matching, Minimum Vertex Cover, Maximum Independent Set | Slides | ||
| 19 | Week 13 | 3/27 | Flow #3: Minimum Cost Flow | Slides | |
| 20 | 3/29 | Flow #4: More Flow | Slides | ||
| Week 14 | 4/3 | Presentations | |||
| 4/5 | Presentations | ||||
Presentations
We will have two sets of student presentations throughout the semester.
Topics and information for the first presentation is here. Schedule is here.
Topics and information for the second presentation is here. Schedule is here.
Assignments
Assignment 0 (IO Practice, Ungraded)Assignment 1 (Released Tues. January 9th, 8:00pm, Due Fri. January 26th, 10:00pm)
Assignment 2 (Releases Thurs. January 25th, 8:00pm, Due Fri. February 9th, 10:00pm)
Assignment 3 (Released Fri. February 9th, 8:00am, Due Thurs. March 8th, 10:00pm)
Assignment 4 (Released Fri. February 16th, 11:00pm, Due Wed. March 14th, 10:00pm)
Assignment 5 (Released Thurs. March 15th, 8:00pm, Due Tues. March 27th, 10:00pm)
Assignment 6 (Released Wed. March 28th, 10:00pm, Due Wed. April 11th, 10:00pm)
Upsolvers (Optional) Due Wed. April 25th, 11:59pm
Assignment 1 UpsolverAssignment 2 Upsolver
Assignment 3 Upsolver
Assignment 4 Upsolver
Assignment 5 Upsolver
Assignment 6 Upsolver
Solve previously unsolved problems and earn 10% of the marks. (Marks should show up correctly on the last columns of the scoreboards)
Other resources
Past Offerings of this course
CPSC 490 Spring 2016
CPSC 490 Spring 2015
CPSC 490 Spring 2014
CPSC 490 Spring 2009
CPSC 490 Spring 2007
CPSC 490 Spring 2006
CPSC 490 Spring 2005
Similar Courses
Stanford - CS 97SI
CMU - 15-295