Setup: graphs are directed, and edges have “capacities”. We have source vertex \(s\) and sink vertex \(t\).

definitions

s-t cut

A cut is a s-t cuts is for a directed graph it goes from s’s side to t’s side; an edge cross an s-t cuts is the edges that goes from \(s\)’s side to \(t’s\) side

cut cost

the cut cost of an s-t cuts is the sum of the weights of the edges that cross the S-T cut.

Key Sequence

Notation

New Concepts

• minimum cut and maximum flow

Important Results / Claims

Questions

Interesting Factoids

see greedy algorithm

Key Sequence

Notation

New Concepts

• minimum spanning tree

Important Results / Claims

Questions

Interesting Factoids

Key Questions

• Does it work?
• Is it fast?
• Can I do better?

General Structure

• worst-case analysis: what’s the performance on the worst input
• Big-oh notation

Syllabus

Divide and Conquer

• merge sort
• Karatsuba Integer Multiplication
• k-select

We typically proof these’s correctness via induction, and we proof runtime by substitution method or master theorem.

Randomized Algorithm

quicksort: worst-case input, we use randomness after input is chosen

sorting with a model of computation

• radix sort, in an ordered model
• limitations of comparison based sorting

data structures

• red-black tree and its balacne rules
• hash table and Universal Hash Family and example of universal hash family

DFS/BFS

• depth first search
  • strongly connected components
  • topological sort
• breadth first search
  • shortest paths

Shortest Paths

• Dijikstra’s Algorithm (DFS)
• Bellman-Ford Algorithm (DP)
• Floyd-Warshall Algorithm (DP)

DP

dynamic programming has a recipe: identify optimal substructure, write down the recursive formulation, fill in table to figure out full answer.