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.

Greedy

greedy algorithm: make a series of choices and immediately commit. Proof: induction by “greedy choices don’t limit future success.”

• activity selection
• Huffman Coding
• minimum spanning tree
  • Prim’s Algorithm
  • Kruskal’s Algorithm

Cuts and Flows

minimum cut and maximum flow and the Folk-Fulkerson Algorithm

Ethics

• Abstraction and Idealization, incommesurability
• tame problems and wicked problems

Methods

• algos: Divide and Conquer, dynamic programming, greedy algorithm
• tools: worst-case analysis, asymptotic analysis, recurrence relation, induction
• data structures: graph, trees, hash family