CPSC 490 - Problem Solving in Computer Science
General Information
Meeting Time: 1-2PM, MWF
Location: FSC 1402 (across the street from ICICS)
Coordinators: Kuba Karpierz, Bruno Vacherot
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 | Notes | |
---|---|---|---|
1 | 1/4 | Overview, I/O | IO, Slides |
2 | 1/6 | Line Sweep | Slides |
3 | 1/8 | Line Sweep cont. | Slides |
4 | 1/11 | Introduction to Dynamic Programming | Notes, Slides |
5 | 1/13 | Longest Common/Increasing Subsequence | Notes, Slides |
6 | 1/15 | Bitmasks, Dynamic Programming | Intro Notes, More Notes, Slides |
7 | 1/18 | Come to class for homework help | None | 8 | 1/20 | Matrix Exponentiation | Notes | 9 | 1/22 | Matrix Exponentiation++ | Notes | 10 | 1/25 | Assignment 1 Discussion | None | 11 | 1/27 | Offline Queries, SQRT Decomposition | Notes | 12 | 1/29 | SQRT Decomposition, Offline Queries | Notes | 13 | 2/1 | Segment Trees | Notes | 14 | 2/3 | Binary Index Trees | Notes | 15 | 2/5 | Range Query Conclusion | Notes | 16 | 2/8 | Presentations | Faster Matrix Multiplication, 2D Range Queries | 17 | 2/10 | Presentations | Optimal BST | 18 | 2/22 | Presentations | Four Russians, Knuth's Word Wrapping Algorithm | 19 | 2/24 | Presentations | Lowest Common Ancestor, Second Shortest Path | 20 | 2/26 | Intro to graphs, BFS | Graph Notes | 21 | 2/29 | Dijkstra’s algorithm | Graph Notes | 22 | 3/2 | MST, DFS | DFS Notes | 23 | 3/4 | DFS, Bellman-Ford | Bellman-Ford | 24 | 3/7 | Bellman-Ford, Heavy-Light Decomposition | Bellman-Ford | 25 | 3/9 | Floyd-Warshall, Geometric Primitives | 26 | 3/11 | Geometric Primitives | 27 | 3/14 | Convex Hulls | 28 | 3/16 | Rotating Calipers | 29 | 3/18 | Trenary Search | 30 | 3/21 | Geometric Search | 31 | 3/23 | Network Flow | 32 | 3/30 | Max-Flow, Mix Cut | 33 | 4/1 | Presentations | 34 | 4/4 | Presentations | 35 | 4/6 | Presentations | 36 | 4/8 | Presentations |
Presentations
We will have two sets of student presentations throughout the semester. More information can be found here.
And we have a schedule for presentations here.
Assignments
Assignment 0 (IO Practice, Ungraded) JudgeAssignment 1 (Due January 20th, 10:00pm) Judge
Assignment 2 (Due February 8th, 10:00pm) Judge
Assignment 3 (Due March 9th, 10:00pm) Judge
Assignment 4 (Due April 4th, 10:00pm) Judge
Assignment 5 (Due April 25th, 10:00pm) Judge
Other resources
Past Offerings of this course
Similar Courses
Stanford - CS 97SI
CMU - 15-295