Algorithms and Data Structures

Algorithms and Data Structures

1. 0. Prologue

   • Enter Fibonacci
   • Big-O Notation

2. 1. Algorithms with numbers

   • Basic Arithmetic
   • Modular arithmetic
   • Primality testing
   • Cryptography

3. 2. Divide and conquer

   • Multiplication
   • Recurrence relations
   • Mergesort
   • Medians
   • Matrix multiplication

4. 3. Decomposition of graphs

   • Depth-first search in undirected graphs
   • Depth-first search in undirected graphs
   • Strongly connected components

5. 4. Paths in graphs

   • Breadth-fist search
   • Dikstra's algorithm

6. 5. Greedy algorithms

   • Huffman encoding
   • Horn formulas
   • Set cover

7. Dynamic programming

   • Longest increasing subsequences

8. 7. Linear programming and reductions

   • Postscript: circuit evaluation

9. 8. NP-complete problems