Lecture materials and links
To be updated to reflect the 2024 fall status
Keep monitoring this page, as material may be updated here.
Lecture/consultation: Tuesday 10.15 - 12.00 Delta - 1021 (Jaak Vilo, Kallol Roy)
Panopto: https://ut.cloud.panopto.eu/ -> (log into courses to see link)
No Zoom / hybrid during lectures or practice groups in classroom
(Log into courses to see the link to all video pre-recordinds)
Schedule for learning from videos, textbooks, etc.
Week 1 Lectures (Sep 2-8)
1. Organisation of the course
- Intro slides PDF (presented in lecture)
- (Log into courses to see the questionnaire)
(Panopto recording available from Panopto, new files are added to new folder)
- why algorithmic rigour? - bits and higher level thinking - challenges - Books etc - (Log into courses to see the questionnaire)
3. Growth functions (Panopto available) PDF, PDF 6up
- 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 - (Log into courses)
Weeks 2 and 3 Lectures (Sep 09-22)
4. Linear structures (Panopto available) PDF, PDF 6up
Topics:
- 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 randomised 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
- Please see the following :
- 04 - Arrays and linked lists
- 05. Sorting - Merge and Quicksort analyses
- 06 - Recurrence - master method
- 07. Linear time sort and sortingbenchmark
- 08 - Order statistics and Skip Lists
Week 4-5 Lectures (Sep 25- Oct 8)
5. Trees (Panopto partly available) PDF , PDF 6up
- Tree data model, hierarchical abstraction
- Tries
- 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
Please see the following videos:
- 09 - Tree data model and basic traversals
- 10 - Binary search tree basics
- 11 - Balanced binary search trees AVL and Red-Black trees
- 12. B-Trees
- 13. k-d trees
- 14. Random Projection Trees
- 15. Geometric trees: Quad-, Oct-, and R-trees
- 16. Binary heap and heap sort
- 17. Augmenting data structures - Ranks, Intervals, Treaps
- 18. Union Find
- Binomial heaps - Amortised analysis - van Emde Boas tree/ PQ queue
Please see the following videos:
- 19. Heaps - Binomial, Fibonacci, Va Emde Boas
Week 6 Lectures (Oct 9-15)
7. Succinct data structures (bit-arrays, trees) PDF , PDF 6up (6.10.2020)
- Definition of succinct
- Heap-like succinct tree
- Rank/Select from bitvector
- general trees
- level-order and depth-first representation
- parenthesis representation
- unified
- SDSL - Succinct Data Structures Library C++ library cheat sheet
- https://av.tib.eu/media/44930 Python library
Please see the following videos:
- 20. Succinct tree representations
- MIT Open courseware - Eric Demain
Week 7 Lectures (Oct 16-22)
- basic representations - hash functions - Universal hashing - Bloom filters
Please see the following videos:
- 21. Hash functions I
- 21. Hashing and Bloom filters II
- Extracurricular info -- guest lecture videos by prof. Amr El Abbadi. E.g. watch Big Data Summarisation
Week 8-9 Lectures (Oct 23 - Nov 5)
- 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
Please see the following videos:
- 22. Graphs I - Intro
- 23. Graphs I - treminology
- 24. Graphs I - graph traversals
- 25. Graphs I - topological sort and SCC
- 26 Minimum spanning trees
- 27. Shortest path algorithms
- 28. Graph - Matrix - Page Rank - MCL
- 29. Landmark based shortest path estimation
- 30. Social Network Analysis (brief)
- 31. Maximum flow networks
Week 10-11 Lectures (Nov 6 - 19)
10. Heuristic Search PDF I, PDF II, PDF III, PDF 6up.
- 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
Please see the following videos:
- 32. Heuristic Search intro
- 33. Greedy Set Cover
- 34. A* algorithm
- 35. local search and TSP
- 36. Local search Simulated Annealing and SAT
- 37. Genetic algorithms and evolutionary strategies
- 38. Videos and graphic design by evolution
- 39. PSO ACO Differential Evolution Summary
Week 12 Lectures (Nov 20-26)
11. Dynamic Programming PDF I, PDF II
- Edit distance - Generalised edit distance - Matrix chain multiplication
Please see the following videos:
- 40. Dynamic programming - principle
- 41. Demo - generalised edit distance usecase examples
- 41. String edit distance
- 42. Dynamic Time Warping
- 43. Matrix chain multiplication
Week 13 Lectures (Nov 27-Dec 3)
12. Pattern Matching / Text search PDF, PDF 6up
- Exact matching
- Knuth-Morris-Pratt
- Boyer Moore family
- Rabin-Karp
- Aho-Corasick for multiple string matching
Please see the following videos:
- 44. Exact Matching I (Naive KMP RK, Shift-Or)
- 45 - Boyer Moore and Factor searches
- 46. Multiple string matching - Aho Corasick, COmmentz Walter, Wu Manber and Bit-parallel
Week 14 Lectures (Dec 4-10)
13. Automata and regular expressions PDF, PDF 6up
- Deterministic and Non-deterministic automata - Regular expressions -> automaton - Non-deterministic into deterministic automaton - Automaton minimisation ...
Please see the following videos:
- 47. Regular expressions languages and automata matching and minimization
Week 15-16 Lectures (Dec 11-22)
14. Approximate matching PDF, PDF 6up
Please see the following videos:
- 48. Approximate matching - part I and II
15. Full-text indexing (suffix trees, arrays, etc) PDF, PDF 6up
- Suffix trie, suffix tree - suffix array - Burrows-Wheeler transformation
Please see the following videos:
- 49. Suffix trees part I
- 49. Suffix trees part II after crash
- 50. Suffix arrays
- 51. Burrows Wheeler transformation BWT part I before crash
- 51. Burrows Wheeler transformation Part II after crash
- Recommended: Travis Gagie -- Pangenomics FM indexes (many genomes, mapping)