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

### Similar Courses

Stanford - CS 97SI

CMU - 15-295