# |
Topic |
Consists of |
1 |
Introduction |
What is in this course. Motivation. Grading details not relevant to people who do not take this course with Adam. |
2 |
Running Times |
Worst case analysis, asymptotic running time including O()-notation, binary search. |
3 |
Sorting |
Selection sort, Merge sort, the Divide and Conquer approach and recurrence relations, a stock market problem, a lower bound for sorting algorithms. |
4 |
BFS |
Introduction to graphs and basic graph notation, the shortest paths problem, the BFS algorithm, shortest paths graphs, an algorithm for checking bipartiteness. |
5 |
Spanning Trees |
Spanning tree, minimum spanning trees, Prim's algorithm, Kruskal's algorithm. |
6 |
Shortest paths |
The weighted shortest paths problem, Dijkstra's algorithm, the Bellman-Ford algorithm, finding an arbitrage, checking if systems of linear inequalities have solutions. |
7 |
Matchings |
Bipartite graphs, matchings, finding a bipartite maximum matching using augmenting paths, stable marriage theorem. |
8 |
Network Flow |
Flow networks, the Ford-Fulkerson algorithm, the min-cut max-flow theorem, finding disjoint paths and Menger's theorem, finding a bipartite maximum matching using network flow. |
9 |
Dynamic Programming |
Cutting steel rods, longest increasing subsequence, similarities in DNA sequences, max weighted independent set in a tree, travelling salesperson problem. |
10 |
Greedy Algorithms |
Transporting materials, the knapsack problem, lecture scheduling, Data compression (Huffman codes). |
11 |
Error Correcting Codes |
Error detection and error correction, linear codes, check matrices, Hamming codes. |
12 |
Cryptography |
Asymmetric cryptography, Diffie-Hellman key exchange, RSA, modular arithmetic. |