CPSC 490  Problem Solving in Computer Science
General Information
Section  Time  Room  Coordinator 

201  MWF 11am12pm  ORCH 3062  Jason Chiu 
202  MWF 3pm4pm  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  Graph 
4  1/11  Graph #2: BellmanFord, FloydWarshall, DFS  Slides  BellmanFord, 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/202/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 (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  15295