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) 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

Other resources

Past Offerings of this course

Past CPSC 490

Similar Courses

Stanford - CS 97SI
CMU - 15-295

Online Judges

SPOJ Online Judge