CPSC490: Lecture notes

January 6

• C++ Input/Output
• io.cpp: Example program in C++
• Challenge Problem 1

January 11

• Solution to Challenge Problem 1
• Standard Template Library (STL) (Part 1)
• Challenge Problem 2

January 13

• Standard Template Library (STL) (Part 2)

January 18

• Solution to Challenge Problem 2
• Standard Template Library (STL) (Part 3)
• Challenge Problem 3

Plan:

1. Graph theory
2. Backtracking
3. Number Theory
4. Dynamic Programming

January 20

• Graph Theory: BFS/DFS Edited Jan-21-2005
• A short tutorial on Flood-Fill with code in Java.

January 25

• Graph Theory: Shortest Paths
  Edited Jan-29 - Small bug fix on page 3 in Dijkstra's algorithm. done[v] should be done[i]

January 27

• Solution to Challenge Problem 3
• Graph Theory: All-pairs shortest paths

February 1

• Graph Theory: Minimum Spanning Trees and Euler cycles Edited Feb-17
• Challenge problem 4

February 3

• Graph Theory: Maximum Flow and Bipartite Matching Edited Feb-8

February 22

• Backtracking: Introduction

February 24

• Backtracking: Branch and Bound

March 1

• Backtracking: Other Techniques

March 3

• Number Theory: GCD and the Extended Euclidean Algorithm Edited Mar-07

March 8

• Number Theory: Modular arithmetic and powers

March 10

• Number Theory: Primes, Factoring, and Euler's phi-function

March 15

• Number Theory: Cryptography

March 22

• Dynamic Programming: Memoization Edited Mar-24

March 24

• Dynamic Programming: Iterative DP, Partition, LIS

March 29

• Dynamic Programming: Partition