## Weekly outline

- General
- 27 and 28 September
### Introduction to algorithms and data structures (chap. 1-3, 10, 12, 17)

- Algorithms
- Asymptotic complexity in time and space
- Consequences in practice
- Elementary data structures (arrays, lists, heaps, queues, binary search trees)
- Dynamic arrays

- 4 and 5 October
### Divide and conquer (chap. 4, 30)

- Brute-force search
- Divide and conquer (binary search, matrix multiplication)
- Analysis of recursive algorithms
- Master theorem
- Fast multiplication of polynomials, discrete Fourier transform

- 11 and 12 October
### Dynamic programming and greedy algorithms (chap. 15, 16)

- Memorisation and dynamic programming (change making problems, sequence alignment)
- Greedy algorithms (knapsack)
- Knapsack and NP-hardness

- 25 and 26 October
### Sorting algorithms (chap. 6-8)

- Insertion sort
- Merge sort
- Quicksort
- Heaps and heapsort
- Lower bounds
- Bucket sort

- 8 and 9 November
### Data structures for sets and hashing (chap. 11, 13)

- Hashing
- Open addressing
- Red-black trees

- 15 and 16 November
### Disjoint-set data structures (chap. 21)

- Weighted union heuristic

- Union by rank

- Path compression

- 22 and 23 November
### Text algorithms (chap. 32)

- Pattern matching

- Dictionary look-up

- Binary search tree, hashing
- Trie (*)

- Multiple pattern matching

- Aho-Corasick (*)
- Suffix trees (*)

- Automata

- 29 and 30 November
### Minimum-weight spanning trees (chap. 23)

- Priority queue

- Kruskal’s algorithm

- Prim’s algorithm

- 6 and 7 December

### Depth-first search (chap. 22)

- Depth-first search

- Topological sort

- Strongly connected components

- 13 and 14 December
### Shortest paths (chap. 24)

- Priority queues

- Dijkstra’s algorithm

- Bellman-Ford algorithm

- 20 and 21 December
### Flow networks (chap. 26)

- Max-flow min-cut theorem

- Ford-Fulkerson algorithm

- 17 and 18 January
### Flow networks II (chap. 26)

- Edmonds-Karp algorithm (augmenting along the shortest path)

- Scaling algorithm (*)

- Bloom filter (*)

- 24 janvier