Algoritmika 2025/26 sügis

Lecture materials and links

To be updated for 2025

Keep monitoring this page, as material may be updated here.

Lecture/consultation: Wednesday 10.15 - 12.00 Delta - 1019 (Jaak Vilo)

Schedule for learning from videos, textbooks, etc.

(Log into courses to see the link to all video pre-recordinds)

Week 1 Lectures (Sep 1-7)

1. Organisation of the course

• Intro slides PDF (presented in lecture)

2. Introduction PDF

   - why algorithmic rigour? 
   - bits and higher level thinking
   - challenges 
   - Books etc

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

Weeks 2 and 3 Lectures (Sep 08-21)

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 22 - Oct 5)

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

6. Heaps PDF , PDF 6up

   - 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 6-12)

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 13-26)

8. Hashing PDF , PDF 6up

   - 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 27 - Nov 2)

9. Graphs PDF , PDF 6up.

   - 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 3 - 16)

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 17-23)

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 24-Nov 30)

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 1-07)

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 8-21)

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)

red