This course provides an introduction to mathematical modeling of computational problems. It covers the common algorithms, algorithmic paradigms, and data structures used to solve these problems. The course emphasizes the relationship between algorithms and programming, and introduces basic performance measures and analysis techniques for these problems. The course can be divided into several blocks of topics, as listed below
- Introduction, cost model, asymptotic complexity
- Algorithmic thinking, peak finding
- Models of computation, Python cost model, document distance
- Sorting and Trees
- Insertion sort and merge sort
- Heaps and heap sort
- Binary search tree and BST sort
- AVL tree and AVL sort
- Counting sort, radix sort and lower bounds for sorting and searching
- Hashing
- Hashing with training
- Table doubling, Karp-Rabin (rolling hash)
- Open addressing, cryptographic hashing
- Numerics
- Integer arithmetic, Karatsuba multiplication
- Square roots, Newton's method
- Graphs
- Breadth-first search (BFS)
- Depth-first search (DFS), topological sorting