Material: Textbook (Goodrich/Tamassia), Chapters 6, 7, 8, and handouts/slides on Mathematical Programming (see the relevant links in the lecture site).

The final exam will be comprehensive, with emphasis on the material covered after midterm 1, in particular Graphs, Flow Networks and mathematical programming (LP and ILP).

• Graphs
  
  • Basic graph properties; trees, cycles, spanning trees, subgraphs, complete subgraphs, cliques, connectivity, components, etc;
  • Directed graphs, transitive closure.
  • Graph traversal methods: BFS, DFS.
  • DAGs, topological sorting, examples, applications.
  • Weighted graphs.

• Fundamental Graph Algorithms
  Make sure you understand the constraints of each, applicability and complexity.
  • Weighted graphs; directed graphs; cycles (and their consequences).
  • Shortest Path algorithms: Dijkstra, Bellman-Ford, DAG based, etc.
  • Single source vs. all-pairs shortest paths. Matrix representation.
  • Minimum Spanning Tree algorithms: Kruskal, Prim's, Baruvka. You should understand WHY they work and for which graphs.

• Weighted and Directed Graphs
  
  • Graph traversal methods: BFS, DFS.
  • DAGs, topological sorting, examples, applications.
  • Shortest path algorithms - Dijkstra, edge relaxation.
  • Minimum spanning tree algorithms: Kruskal, Prims, etc.

• Network Flows and Matching
  
  • Basic concepts in network flows and cuts, and their relationship.
  • Max-Flow/Min-Cut theorem.
  • Augmenting path algorithms to find maximum flow.
  • Matching, and maximum bipartite matching; computation methods.
  • Min cost flow, multi-commodity flows, etc.

• Mathematical Optimization
  
  • Basic concepts in Mathematical Programming: types of objective function, constraints, convexity.
  • Linear Programming (LP) , problem formulation.
  • Integer Linear Programming (ILP), particularly 0,1 integer programming.
  • Total unimodularity, and relationship between LP and ILP.
  • LP Duality, transforming primal problem into dual, interpretation of dual variables and constraints (review the examples covered in class).
  • Relationship between Graph Algorithms and combinatorial, Mathematical Optimization problems.
  • Special class of problems with total unimodular constraint matrix: flow networks.
  • Simulated Annealing, bi-partitioning - general concepts.

• Problem Modeling
  
  • You should be able to model a simple problem both as a graph problem as well as a mathematical optimization problem; and apply the right graph algorithm or optimization method to solve it.
  • Examples include: task dependence, scheduling, imposing constraints, problem relaxation and simplification, shortest vs longest vs critical path; network flows (min/max, scheduling, assignment, matching, etc.

Good Luck! Have a nice, safe, and relaxing summer.