CPSC 490 - Problem Solving in Computer Science
General Information
| Section | Time | Room | Coordinators |
|---|---|---|---|
| 201 | TTh 17:30-19:00 | ORCH 4016 | Henry Xia |
| 202 | TTh 15:30-17:00 | MCML 358 | Brandon Zhang |
Proposal and Syllabus
Piazza Discussion Board
You can sign up for the discussion board here.
Lectures
Schedule is subject to change. Slides and notes will be uploaded before lectures.
| # | Week | Date | Topics | Slides | Extra Notes |
|---|---|---|---|---|---|
| 1 | Week 1 | 1/3 | Intro: Overview, I/O, Floating Point, Implementation Tips, Binary Search |
Slides Solutions to problems 4, 5 |
I/O and containers, Floating point |
| 2 | Week 2 | 1/8 | Graph Traversals, Shortest Paths | Slides | Graph Basics, DFS, Bellman-Ford, SPFA |
| 3 | 1/10 | Bellman Ford and Inequalities, Topological Sort, Strongly Connected Components | Slides | ||
| 4 | Week 3 | 1/15 | 2-SAT, Trees, Minimum Spanning Tree | Slides | |
| 5 | 1/17 | Network Flow, Max Flow = Min Cut | Slides | History of flow algorithms | |
| 6 | Week 4 | 1/22 | Applications of Flow, Flow with demands | Slides | Flow with demands |
| 7 | 1/24 | Bipartite Graphs: Matching, Konig's Theorem | Slides | ||
| 8 | Week 5 | 1/29 | Dynamic Programming Intro, Top Down and Bottom Up Implementations | Slides | |
| 9 | 1/31 | Recovering Solutions, Bitmask DP, Matrix Exponentiation | Slides | Matrix Exponentiation, DP Optimizations (bonus) | |
| 10 | Week 6 | 2/5 | Tree DP: Examples, the Smaller to Larger Trick, DP on DAGs | Slides | Tree DP |
| 11 | 2/7 | More DP: Binary jumping, lowest common ancestor, Digit DP | Slides | ||
| Week 7 | 2/12 | Snow | |||
| 2/14 | Presentation #1 | ||||
| Reading Week (2/18-2/22) | |||||
| Week 9 | 2/26 | Presentation #1 | |||
| 12 | 2/28 | Segment Tree Intro | Slides | ||
| 13 | Week 10 | 3/5 | Segment Tree Lazy Propagation, and Tricks | Slides | |
| 14 | 3/7 | Subtree updates and queries, Line sweep | Slides | ||
| 15 | Week 11 | 3/12 | Geometry Primitives | Slides |
Computational Geometry (relevant sections) |
| 16 | 3/14 | Convex Hull, Binary Search, Ternary Search | Slides | ||
| 17 | Week 12 | 3/19 | Rotating Calipers | Slides | |
| 18 | 3/21 | Geometric Interpretations of Problems | Slides | ||
| 19 | Week 13 | 3/26 | Assignment discussion | ||
| 20 | 3/28 | Presentation #2 | |||
| Week 14 | 4/2 | Presentation #2 | |||
| 4/4 | Presentation #2 | ||||
Presentations
We will have two sets of student presentations.
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: Thursday Jan 3. Due: Tuesday Jan 15, 12:00 noon); Solutions
Assignment 2 (Released: Thursday Jan 10. Due: Tuesday Jan 22, 12:00 noon); Upsolver, Discussion
Assignment 3 (Released: Sunday Jan 20. Due: Friday Feb 1, 23:59); Upsolver, Discussion
Assignment 4 (Released: Thursday Jan 31. Due: Tuesday Mar 5, 23:59); Upsolver, Discussion
Assignment 5 (Released: Friday Mar 8. Due: Tuesday Mar 19, 23:59) Upsolver, Discussion
Assignment 6 (Released: Wednesday Mar 20. Due: Monday Apr 8, 21:00) Upsolver, Discussion
Assignment 7 (Released: Soon. Due: Thursday Apr 25, 21:00)
Other resources
Past Offerings of this course
CPSC 490 Spring 2017
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