CPSC 490 - Problem Solving in Computer Science
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.
More information on the lectures will be filled out as we approach the lecture date.
|1||1/4||Overview, I/O||IO, 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|
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.
AssignmentsAssignment 0 (IO Practice, Ungraded) Judge
Assignment 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
Past Offerings of this course
Past CPSC 490
Stanford - CS 97SI
CMU - 15-295
SPOJ Online Judge