CPSC 490 - Problem Solving in Computer Science
General Information
| Section | Time | Room | Coordinators |
|---|---|---|---|
| 202 | Tuesday & Thursday 16:00-17:30 | ORCH 3016 | Lucca Siaudzionis |
| 204 | Tuesday & Thursday 12:30-14:00 | ORCH 4058 | Jack Spalding-Jamieson |
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 | Jan. 7th | Intro: Overview, I/O, Floating Point, Implementation Tips, and Binary Search | L1 |
I/O and containers, Floating point |
| 2 | Jan. 9th | Graphs: Intro, DFS, and BFS | L2 | ||
| 3 | Week 2 | Jan. 14th | Graphs: Dijkstra, Floyd-Warshall, Union-Find, and Toposort | L3 | |
| 4 | Jan. 16th | Graphs: Trees, MST, Euler Tour, and Backtracking | L4 | ||
| 5 | Week 3 | Jan. 21th | Graphs: SCC, 2-SAT; DP: Intro | L5 | |
| 6 | Jan. 23rd | DP: Array Max-IS, LCS, Recovering Solutions, and Binary Exponentiation | L6 | ||
| 7 | Week 4 | Jan. 28th | DP: Knapsack, Bitmask DP, Tree DP | L7 | |
| 8 | Jan. 30th | DP: Optimizations | L8 | Guest lectured by David Zheng | |
| 9 | Week 5 | Feb. 4th | DP: Binary Jumping, LCA and Range Queries: Intro, Prefix Sums, and Fenwick Trees | L9 | |
| 10 | Feb. 6th | Range Queries: Segment Trees and Lazy Propagation | L10 | A quick C++ implementation, Efficient Segment Trees | |
| 11 | Week 6 | Feb. 11th | Range Queries: Line Sweep, Subtree Queries, and Extra Topic | L11 | |
| 12 | Feb. 13th | Range Queries: Binary Jumping (Quick Review), Offline Queries, SQRT Decomposition, and Mo's Algorithm | L12 | ||
| Reading Week (02/18-02/21) | |||||
| 13 | Week 8 | Feb. 25th | Geometry: Primitives | L13 | |
| 14 | Feb. 27th | Geometry: Line Sweep, Convex Hulls | L14 | ||
| 15 | Week 9 | Mar. 3rd | Geometry: Ternary Search, Angle Sweep, and Rotating Calipers | L15 | |
| 16 | Mar. 5th | Strings: Tries and KMP | L16 | ||
| 17 | Week 10 | Mar. 10th | Strings: Aho-Corasick | L17 | Aho-Corasick visualization |
| 18 | Mar. 12th | Number Theory | L18 | Guest lectured by Brandon Zhang | |
| 19 | Week 11 | Mar. 17th | Problem Solving | L19 | |
| 20 | Mar. 19th | Problem Solving | L20 (Part 1), (Part 2) | ||
| 21 | Week 12 | Mar. 24th | Project-Related Office Hours | L21 | |
| 22 | Mar. 26th | Problem Solving | L22 (Part 1) | ||
| Week 13 | Mar. 31st | Mini Network Flow Unit: Flow Intro | L23 | ||
| Apr. 2nd | Mini Network Flow Unit: Flow with Demands, Cool Reductions, Bipartite Matching, and Konig's Theorem | L24 | |||
| 23 | Week 14 | Apr. 7th | Finale: Heavy-Light Decomposition and Suffix Arrays | L25 | |
Assignments
Assignment 0 (IO Practice, Ungraded)Assignment 1 (Graphs, Due 2020/01/25 23:59 PST) (Upsolver)
Assignment 2 (Dynamic Programming, Due 2020/02/09 23:59 PST) (Upsolver)
Assignment 3 (Range Queries, Due 2020/03/01 23:59 PST) (Upsolver)
Assignment 4 (Geometry and Strings, Due 2020/03/22 23:59 PST) (Upsolver)
Assignment 5 (Course Medley, Due 2020/04/19 23:59 PDT) (Upsolver)
Written Report
Project requirements.Written report rubric.
Pre-approved topics.
Presentation
The presentations will happen on March 31st and April 2nd. Regardless of when you are presenting, you have to submit your slides by March 30th, 11:59PM. No changes will be allowed to the slides after. You presentation should last at most 8 minutes and briefly cover your report. Try to cover roughly the same topics your report covers. You can choose how to allocate your time for each section. Make sure to spend enough time introducing the topic so that we, the audience, can understand it before you go to the other sections. Due to the time limit, it is recommended that you use only your slides, with no use of the whiteboard. Please start early and work hard on your slides in advance! After the end of your presentation, a short Q&A section will follow. It should last approximately 4 minutes, but that is more flexible. Your set of presentation, slides, and Q&A will be worth 85% of your presentation grade (so 8.5% of the course total). Peer Feedback: The other 15% of your presentation grade comes from your peer feedback for others. For each of the other students presentation, you should write a short comment. This comment should address what you liked, disliked, issues, and suggestions. We will evaluate the peer feedback in a "binary" way, i.e. for each feedback that you write for another student, it will either be considered "good" (useful, constructive, interesting) or "not good" (e.g. already completely addressed in the presentation, not relevant to the topic at all, blank, numerical ratings, etc.). Your final peer feedback grade will be proportional to the number of "good" feedbacks you provide for other presentations. The feedback you write has no influence in other students' grades. Possibility of campus shutting down due to COVID-19 If this happens, you will be required to record your presentation and submit it to us. There will be no Q&A section. The recording will be due shortly after April 2nd (exact date TBD). Again, this will only be required if the in-person presentations have to be cancelled. We do recommend you do this recording regardless, since it will be a good practice for the presentation.Grading Scheme
Assignment #1: 15%Assignment #2: 15%
Assignment #3: 15%
Assignment #4: 15%
Assignment #5: 15%
Written Report: 15%
Presentation: 10%
Other resources
Code Archives
UBC Code Archive
Stanford Code Archive
Past Offerings of this course
Many assignment problems and slides were reused from previous offerings of this course. We'd like to especially thank the previous instructors Jason Chiu, Raunak Kumar, Daniel Du, David Zheng, Henry Xia, and Brandon Zhang for all their help.
CPSC 490 Spring 2018
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