Algoritmika 2021/22 sügis

Lecture materials and links

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

Panopto: https://panopto.ut.ee/ -> Algorithmics 2021 folder on Panopto, with videos

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

Attach:Questionnaire2021.doc

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)

2. Introduction (Panopto available) PDF , PDF 6up

   - 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

4. Linear structures (Panopto available) PDF , PDF 6up

   - 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

5. Trees (Panopto partly available) PDF , PDF 6up

   - 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

6. Heaps PDF , PDF 6up

   - Binomial heaps
   - Amortised analysis
   - van Emde Boas tree/ PQ queue

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

8. Hashing PDF , PDF 6up

   - basic representations
   - hash functions
   - Universal hashing
   - Bloom filters

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

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

11. Dynamic Programming PDF I, PDF II

   - Edit distance
   - Generalised edit distance
   - Matrix chain multiplication 

12. Pattern Matching / Text search PDF, PDF 6up

   - Exact matching 
      - Knuth-Morris-Pratt
      - Boyer Moore family
      - Rabin-Karp
      - Aho-Corasick for multiple string matching

13. Automata and regular expressions PDF, PDF 6up

   - Deterministic and Non-deterministic automata
   - Regular expressions -> automaton
   - Non-deterministic into deterministic automaton 
   - Automaton minimisation
   ...

14. Approximate matching PDF, PDF 6up

15. Full-text indexing (suffix trees, arrays, etc) PDF, PDF 6up

   - Suffix trie, suffix tree
   - suffix array
   - Burrows-Wheeler transformation

16. (tbc) Hidden Markov Models

red