## Weekly outline

- General
- 27 and 28 SeptemberThis week
### 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
### 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
### 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
### 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
### 8 and 9 November

### Data structures for sets and hashing (chap. 11, 13)

- Hashing
- Open addressing
- Red-black trees

- 15 and 16 November
### 15 and 16 November

### Disjoint-set data structures (chap. 21)

- Weighted union heuristic
- Union by rank
- Path compression

- Weighted union heuristic
- 22 and 23 November
### 22 and 23 November

### Text algorithms (chap. 32)

- Pattern matching
- Naive
- KMP

- Dictionary look-up
- Binary search tree, hashing
- Bloom filter (*)
- Trie (*)

- Multiple pattern matching
- Aho-Corasick (*)
- Suffix trees (*)

- Automata

- Pattern matching
- 29 and 30 November
- 6 and 7 December
### 6 and 7 December

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

- Depth-first search
- Topological sort
- Strongly connected components

- Depth-first search
- 13 and 14 December
### 13 and 14 December

### Shortest paths (chap. 24)

- Priority queues
- Dijkstra’s algorithm
- Bellman-Ford algorithm

- Priority queues
- 20 and 21 December
- 10 and 11 January
### 10 and 11 January

### Flow networks II (chap. 26)

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

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