Algoritmika 2024/25 sügis

Lecture materials and links

Updated to reflect the 2024 fall status

Home Exam tasks have been revealed in the Exam page!

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)

2. Introduction PDF , PDF 6up

   - 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

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

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 23 - Nov 5)

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

red