CPSC 490 - Problem Solving in Computer Science
General Information
Section | Time | Room | Coordinator |
---|---|---|---|
201 | MWF 11am-12pm | ORCH 3062 | Jason Chiu |
202 | MWF 3pm-4pm | ORCH 3068 | Raunak Kumar |
Proposal and Syllabus
Piazza Discussion Board
You can sign up for the discussion board here. We also post hints to the assignments on the board.
Lectures
Schedule is subject to small changes. Slides and notes will be uploaded before lecture.
# | Week | Date | Topics | Slides | Notes |
---|---|---|---|---|---|
1 | Week 1 | 1/4 | Overview, I/O, Floating Point | Slides | IO, Floating point |
2 | 1/6 | Implementation, Brute Force, Intro to Graphs, O(1) Memory Problems |
Slides | ||
3 | Week 2 | 1/9 | Graph #1: BFS, Dijkstra, MST | Slides | |
4 | 1/11 | Graph #2: Bellman-Ford, Floyd-Warshall, DFS | Slides | Bellman-Ford, DFS | |
5 | 1/13 | DP #1: Introduction, LIS, Knapsack | Slides | DP Intro, LIS/Knapsack | |
Week 3 | 1/16 | Come to class for HW Help | |||
6 | 1/18 | DP #2: LCS, Edit Distance | Slides | LCS | |
7 | 1/20 | DP #3: Bitmask DP, Matrix Exponentiation | Slides |
Bitmasks Intro,
Bitmask DP,
Matrix Exponentiation, DP Optimizations (optional) |
|
8 | Week 4 | 1/23 | DP #4: Tree DP, LCA Query, Graph DP | Slides | Tree DP |
9 | 1/25 | String #1: Trie, KMP; Assignment 1 Discussion | Slides | String notes (relevant sections) | |
10 | 1/27 | String #2: Aho Corasick | Slides | ||
11 | Week 5 | 1/30 | String #3: Suffix Array | Slides | Suffix Array |
12 | 2/1 | Query #1: SQRT Decomposition, Offline Queries | Slides | ||
13 | 2/3 | Query #2: Segment Tree | Slides | Segment Tree | |
14 | Week 6 | 2/6 | Query #3: Binary Indexed Tree, Tree Tricks | Slides | Euler Tour Tree |
2/8 | Presentations / Homework Help | ||||
2/10 | Presentations | ||||
Week 7 | 2/13 | Family Day (no class) | |||
2/15 | Presentations | ||||
2/17 | Presentations | ||||
Reading Week (2/20-2/24) | |||||
15 | Week 9 | 2/27 | Geom #1: Geometry Primitives | Slides | Computational Geometry (relevant sections) |
16 | 3/1 | Geom #2: Convex Hull | Slides | ||
17 | 3/3 | Geom #3: Rotating Calipers | Slides | ||
18 | Week 10 | 3/6 | Geom #4: Line Sweep I | Slides | |
19 | 3/8 | Geom #5: Line Sweep II | Slides | ||
20 | 3/10 | Divide and Conquer | Slides | ||
21 | Week 11 | 3/13 | Binary Search, Ternary Search | Slides | |
3/15 | Assignment 2 & 3 & 4 Discussion | ||||
22 | 3/17 | Flow #1: Maximum Flow | Slides | ||
23 | Week 12 | 3/20 | Flow #2: Maximum Bipartite Matching | Slides | |
24 | 3/22 | Flow #3: Konig's Theorem | Slides | ||
25 | 3/24 | Flow #4: More Flow, Flow with Demands | Slides | ||
26 | Week 13 | 3/27 | Flow #5: Minimum Cost Flow | Slides | |
3/29 | Presentations | ||||
3/31 | Presentations | ||||
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.
You must choose a topic for the second presentation by Monday, March 20th
Assignments
Assignment 0 (IO Practice, Ungraded) JudgeAssignment 1 (Released Wed. January 4th, 8:00pm, Due Mon. January 23rd, 10:00pm) Judge
Assignment 2 (Released Mon. January 16th, 8:00pm, Due Mon. February 13th, 10:00pm) Judge
Assignment 3 (Released Mon. January 30th, 8:00pm, Due Mon. March 13th, 10:00pm) Judge
Assignment 4 (Released Mon. February 13th, 8:00pm, Due Mon. March 13th, 10:00pm) Judge
Assignment 5 (Released Mon. March 13th, 8:00pm, Due Mon. April 3rd, 10:00pm) Judge
Assignment 6 (Released Mon. March 27th, 8:00pm, Due Mon. April 24th, 10:00pm) Judge
Other resources
Past Offerings of this course
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