|
Sections |
Topics |
|
1-5 |
Mathematical foundations |
|
1 |
Bubble sort, insertion sort, merge sort. Worst case complexity, recurrences. Recursive divide-and-conquer algorithms. |
|
7 |
Heaps, heap sort, priority queues |
|
8 |
Quick sort, randomized algorithms. Worst case complexity |
|
- |
Lexicographic order, representation of functional expressions, sorting of expressions. |
|
9 |
Lower bound for the (comparison) sorting problem. The decision tree model for comparison sorting. |
|
9 |
Can we sort quicker? Counting, Radix and Bucket sorts. |
|
13 |
Binary search trees, balanced trees, red-black trees (applet - after you add a node you have to press "next step" several times until yellow label disappear; there are many similar applets on the web, so if you don't like this particular one, search for other implementations). |
|
16 |
Dynamic programming |
|
17 |
Greedy algorithms |
|
23 |
Representations of graphs, breadth-first search and depth-first search, topological sort, strongly connected components. |
|
24 |
Minimum spanning trees |
|
25 |
Single-source shortest paths |
|
26 |
All-pairs shortest paths |
|
27 |
Flow networks, maximum flow. |
|
36 |
NP-completeness |