Algoritmika 2020/21 sügis

Lecture materials and links

No physical lectures in auditorium any more.

No lecture Tue 24.11.

After each lecture, video recording will be made available here.

Piazza: https://piazza.com/class/ke78jd1mzo79r

Panopto: https://panopto.ut.ee/ -> Algorithmics folder on Panopto

Zoom link to Tuesday lectures: (log into courses to see link)

Note that 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 bullet-proof replacement for missing lectures. :)

Attach:Questionnaire.doc

1. Organisation of the course (Panopto available) PDF , PDF 6up

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

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

9. Graphs PDF , PDF 6up. (11.10.)

   - 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  (18.10.)
   - 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

No lecture session on 27.10.2020 due a conference

10. Heuristic Search PDF I, PDF II, PDF III, PDF 6up (24.10.)

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

   - Edit distance
   - Generalised edit distance
   - Matrix chain multiplication 

---

12. Pattern Matching / Text search PDF, PDF 6up (15.11 and 22.11)

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

13. Automata and regular expressions PDF, PDF 6up (22.11)

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

14. Approximate matching PDF, PDF 6up (29.11)

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

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

16. (tbc) Hidden Markov Models

red