CPSC 490 - Problem Solving in Computer Science

General Information

SectionTimeRoomCoordinators
202TTh 11am-12:30pmORCH 3062David Zheng, Daniel Du
Faculty Sponsors: Will Evans

Proposal and Syllabus

Piazza Discussion Board

You can sign up for the discussion board here. We will post hints to the assignments on the board.

Lectures

Schedule is subject to change. Slides and notes will be uploaded before lectures.

# Week Date Topics Slides Notes
1 Week 1 1/4 Intro: Overview, I/O, Floating Point Slides IO, Floating point
2 Week 2 1/9 Graph #1: Intro, BFS, DFS, Floyd-Warshall, Dijkstra, Bellman-Ford Slides Graph Basics, DFS, Bellman-Ford
3 1/11 Graph #2: Trees, MST, Union find, Euler tour Slides
4 Week 3 1/16 Graph #3: BCC, SCC, 2-SAT Slides
5 1/18 DP #1: Intro, LCS, Knapsack Slides DP Intro, LCS LIS/Knapsack
6 Week 4 1/23 DP #2: LIS, Bitmask DP, Matrix Exponentiation Slides Bitmasks Intro, Bitmask DP,
Matrix Exponentiation,
DP Optimizations (optional)
7 1/25 DP #3: Binary jumping, Tree DP, LCA Query, Graph DP Slides Tree DP
8 Week 5 1/30 Strings: KMP, tries, hashing Slides String notes (relevant sections)
9 2/1 Query #1: SQRT Decomposition, Offline Queries, Binary Search, Divide and Conquer Slides
10 Week 6 2/6 Query #2: Binary index tree, Segment Tree Slides Segment Tree
11 2/8 Query #3: More Trees Slides Euler Tour Tree
Week 7 2/13 Presentations
2/15 Presentations
Reading Week (2/19-2/23)

Presentations

We will have two sets of student presentations throughout the semester.

Assignments

Assignment 0 (IO Practice, Ungraded) Judge
Assignment 1 (Released Tues. January 9th, 8:00pm, Due Fri. January 26th, 10:00pm) Judge

Other resources

Past Offerings of this course

CPSC 490 Spring 2016
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
Codeforces