## Aperçu des semaines

### 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, queues, rooted trees)
• Dynamic arrays

### Divide and conquer (chap. 4, 30)

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

### Dynamic programming and greedy algorithms (chap. 15, 16)

• Memoisation and dynamic programming
• Greedy algorithms
• Knapsack and fractional knapsack
• Minimum Edit Distance

### Sorting algorithms (chap. 6-8)

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

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

• Sets and dictionaries
• Chained hash tables
• Designing hash functions
• Binary search trees
• Red-black trees
• ### 21-27/10/2019

##### Algorithms on strings (chap. 32)
• Pattern matching
• Naive
• KMP
• Dictionary look-up
• Trie (*)
• Multiple pattern matching
• Aho-Corasick (*)
• Suffix trees (*)

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

• Weighted union heuristic
• Union by rank
• Path compression

### Minimum-weight spanning trees (chap. 23)

• Priority queue
• Kruskal’s algorithm
• Prim’s algorithm

• ### 25-01/11/2019

##### ### Search in Graphs (chap. 22)
• Generic Search
• Depth-First search
• Topological sort
• Strongly connected components

### Shortest paths (chap. 24)

• Dijkstra’s algorithm
• Bellman-Ford algorithm
• Floyd-Warshall Algorithm

### Flow networks (chap. 26)

• Max-flow min-cut theorem
• Ford-Fulkerson algorithm

### Introduction to approximation algorithms

• Vertex Cover
• Traveling Salesman Problem
• Set cover
References: Chap 1 and 2 of the book "Approximation Algorithms" of Vijay V. Vazirani, Chap 35 of "Introduction To Algorithms" can also be looked at.

• ### 10 Janvier, 10:30 - 12:30

Séance de révision. Si il y a des points particuliers que vous voulez revoir faites le nous savoir.