CPSC 490 - Problem Solving in Computer Science

General Information

SectionTimeRoomCoordinator
201MWF 11am-12pmORCH 3062Jason Chiu
202MWF 3pm-4pmORCH 3068Raunak Kumar
Faculty Sponsors: Will Evans

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 Graph
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) Judge
Assignment 1 (Due Monday, January 23rd, 10:00pm) Judge
Assignment 2 (Due Monday, February 13th, 10:00pm) Judge
Assignment 3 (Due Monday, March 13th, 10:00pm) Judge
Assignment 4 (Due Monday, March 13th, 10:00pm) Judge
Assignment 5 (Due Monday, April 3rd, 10:00pm) Judge
Assignment 6 (Due Monday, April 17th, 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

Online Judges

SPOJ Online Judge