Lecture materials and links
Keep monitoring this page, as material may be updated here.
Zoom link to Tuesday lectures: (log into courses to see link)
Slack: (log into courses to see link)
Note that during any online only or hybrid sessions the videos may fail to get recorded or processed for various reasons. They are for an additional help but not a 100% guarantee. Please do not consider them for missing lectures. :)
1. Organisation of the course: Online Meeting / Zoom on August 31st at 10:15.
2021 Intro slides PDF
(Panopto recording available from 2020; Zoom recording of 2021 will be added to Panopto folder)
- why algorithmic rigour? - bits and higher level thinking - challenges - Books etc
- Counting the nr of operations, memory slots, etc. - Increase of work when input grows - Big Oh (growth in long run - asymptotic analysis; computational complexity classes) - gnuplot, etc. - Divide and conquer
- Arrays, Lists, Linked lists, XOR list - Abstract Data Types - Queue, circular queue, dequeue, Stack - Amortised analysis example - Binary Search - Sorting: lower bound, Merge Sort, Quicksort - Recursion tree - Average performance of randomise algorithm (Quicksort) - Master method for solving recurrences - Sorting in linear time (Counting sort, Radix sort, Bit-mask based sort) - Bucket sort - Order statistic - Speeding up linked lists - Skip lists
- Tree data model, hierarchical abstraction - Trie - Binary trees - notations, storage, traversal (pre- , post-, in-order), parenthesisation (serialisation), expression trees - General tree traversal: pre- and postorder, depth first, breadth first - Binary Search tree - BST balancing - AVL and Red-Black trees - B-tree - k-d tree (2D, 3D, ..), random projections tree, - Quad-tree, Oct-tree, R-tree variants - Binary heap, array storage, Heapify in O(n) - Augmented data structures: - Dynamic order statistics - Interval tree example - Treap - Union-find
- Binomial heaps - Amortised analysis - van Emde Boas tree/ PQ queue
- Definition of succinct - Heap-like succinct tree - Rank/Select from bitvector - general trees - level-order and depth-first representation - parenthesis representation - unified
- basic representations - hash functions - Universal hashing - Bloom filters
- general relationships representation - Basic characteristics: degrees, connectivity, etc.. - types of graphs: directed/undirected, cyclic/acyclic, ... - Representations: Edge lists, Array representations, ... - Breadth-first, Depth first, Random order, Guided heuristic search - Topological sorting - Finding cycles - Strongly connected components Graphs II PDF, PDF 6up - Weighted graphs - Minimum spanning tree (Prim and Kruskal) - Shortest paths - Dijkstra algorithm - A* algorithm - Paths by matrix multiplications - Page rank - Monte Carlo Clustering (MCL) - Estimation of distances - Community analysis (clustering) - Maximum Flow
- Search space - Objective function - Greedy search - Set cover - A* - TSP - Stochastic search - Simulated Annealing - TABU search - SAT solving - Genetic algorithms - Evolution - Examples, art, etc - Ant Colony Optimisation - Differential Evolution - Robust regression - Particle Swarm Optimisation
- Edit distance - Generalised edit distance - Matrix chain multiplication
- Exact matching - Knuth-Morris-Pratt - Boyer Moore family - Rabin-Karp - Aho-Corasick for multiple string matching
- Deterministic and Non-deterministic automata - Regular expressions -> automaton - Non-deterministic into deterministic automaton - Automaton minimisation ...
- Suffix trie, suffix tree - suffix array - Burrows-Wheeler transformation
16. (tbc) Hidden Markov Models