Backstory, Partitioning Quick Sort Partition Sort, a.k.a. Quicksort Quicksort Runtime Theoretical analysis: Best case: Θ(N log N) Worst case: Θ(N2) Compare this to Mergesort. Best case: Θ(N log N) Worst case: Θ(N log N) Recall that Θ(N log N) vs. Θ(N2) is a really big deal. So how can Quicksort be the fastest sort empirically? Because on average it is Θ(N log N). Rigorous proof requires probability theory + calculus, but intuition + empirical analysis will hopefully convince you.

Shortest Paths in a DAG (Directed Acyclic Graphs) Dynamic Programming the DAG SPT algorithm The DAG SPT algorithm can be thought of as solving increasingly large subproblems: Distance from source to source is very easy, and is just zero. We then tackle distances to vertices that are a bit farther to the right. We repeat this until we get all the way to the end of the graph. Problems grow larger and larger.

pros and cons Graph Problem so far Punchline: DFS and BFS both traverse entire graphs, just in a different order (like preorder, inorder, postorder, and level order for trees). Solving graph problems is often a question of identifying the right traversal. Many traversals may work. Example: DFS for topological sort. BFS for shortest paths. Example: DFS or BFS about equally good for checking existence of path. Dijkstra’s Algorithm problem restatement: Find the shortest paths from source vertex s to some target vertex t.