# CPSC 490 - Problem Solving in Computer Science

## General Information

Meeting Time: 3-4PM, MWF

Location: FSC 1613 (across the street from ICICS)

Coordinators: Paul Liu, Kent Williams-King, Nasa Rouf

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 | Lecturer | Notes | |
---|---|---|---|---|

1 | 1/5 | Overview, I/O | Paul | IO, Slides |

2 | 1/7 | Intro to graphs, BFS | Paul | Graph Notes, Slides |

3 | 1/9 | Dijkstra’s algorithm | Paul | Graph Notes, Slides |

4 | 1/12 | MST, DFS | Paul | DFS Notes, Slides |

5 | 1/14 | DFS, Bellman-Ford | Paul | Bellman-Ford, Slides |

6 | 1/16 | Bellman-Ford, Inequality Feasiblity | Paul | Slides |

7 | 1/19 | Come to class for HWK Help | Paul | None |

8 | 1/21 | Floyd-Warshall, Dynamic Programming (DP) | Kent | DP Intro Notes |

9 | 1/23 | Homework 1 Due, Intro to DP | Kent | DP Intro Notes |

10 | 1/26 | Longest Increasing Subsequence | Kent | LIS Notes |

11 | 1/28 | LCS and Edit Distance | Paul | Slides, LCS Notes |

12 | 1/30 | Presentation Choice Due, Bitmask DPs | Paul | Bitmasks Intro, Bitmask DP, Slides |

13 | 2/2 | DPs and graphs | Paul | Slides |

14 | 2/4 | Student Presentations | Paul | None |

15 | 2/6 | Student Presentations | Paul | None |

16 | 2/11 | Student Presentations | Nasa | None |

17 | 2/13 | Student Presentations | Nasa | None |

18 | 2/23 | Matrix Expo, SQRT Decomp | Paul | Slides |

19 | 2/25 | SQRT Decomp, Offline Queries | Paul | Slides |

20 | 2/27 | Offline Queries, SQRT Decomp on Graphs | Paul | Slides |

21 | 3/2 | SQRT Decomp on Graphs, Segment Trees | Paul | Slides |

22 | 3/4 | Implementation of Segment Trees | Paul | Slides |

23 | 3/6 | BITs and O(1) queries | Paul | Slides |

24 | 3/9 | Geometric Primitives | Nasa | Slides |

25 | 3/11 | Convex Hulls | Nasa | Slides |

26 | 3/13 | Intersections and Distances | Nasa | Slides |

27 | 3/16 | Rotating Calipers | Nasa | Slides |

28 | 3/18 | Line Sweep | Nasa | Slides |

29 | 3/20 | Line Sweep | Nasa | Slides |

30 | 3/23 | Divide and Conquer, Search Problems | Nasa | Slides |

31 | 3/25 | Search, Network Flow | Nasa, Paul | Slides, Slides |

32 | 3/27 | Max-flow Min-cut | Paul | Slides, Notes |

33 | 3/30 | Student Presentations | Paul | None |

34 | 4/1 | Student Presentations | Paul | None |

37 | 4/8 | Student Presentations | Paul | None |

38 | 4/10 | Student Presentations | Paul | None |

## Presentations

We will have two sets of student presentations throughout the semester. More information can be found here.

**Update:** The schedule for the second set of presentations is out! See here

## Assignments

Practice Problems Judge

Assignment 0 (IO Practice, Ungraded) Judge

Assignment 1 (Due Friday, January 23rd. Graded out of 100 marks) Written, Judge

Assignment 2 (Due Friday, Feb 20th. Graded out of 100 marks) Written, Judge

Assignment 3 (Due Wednesday, March 11th. Graded out of 100 marks) Judge

Assignment 4 (Due Sunday, March 29th. Graded out of 100 marks) Judge

Assignment 5 (Due Monday, April 13th. Graded out of 100 marks) Written, Judge

## Other resources

### Past Offerings of this course

### Similar Courses

Stanford - CS 97SI

CMU - 15-295