Time and
location (2022/2023/1
semester): Monday and Thursday
12:1513:45, IB134
Required knowledge:
This is really an advanced class :) You are expected to be
familiar with the basics of Theory of Algorithms. To be more
precise, we will build on your knowledge of the following
topics:
Cormen,
Leiserson, Rivest and Stein: Introduction to Algorithms,
sections 2.13, 3.12, 6.19.3, 10.113.4, 15.15, 22.125.2,
26.13, 34.15.
If you are not familiar with many of these, then it will be
difficult to follow this class. (
In this case we suggest to
take Theory
of Algorithms VISZAA08.) If you are familiar
with most of it then you should be able to learn the rest
yourself during the semester.
To help you to test your knowledge we
prepared test. If you can solve (and explain the
solution) at least 16 questions, then you will be fine in this
class. If you can solve at least 12, then you will need to learn
a few topics yourself. If your result is less than 12, then you
should probably take a more basic class in algorithms before you
take this class. (
We can give suggestions if you need some.)
Topics covered so far and
other information about the class:
Planned topics:
We will select the topics after discussion with the students.
Some possibilities are

 Average case running time of quicksort
Thomas
H. Cormen, Charles E. Leiserson and Ronald L. Rivest:
Introduction to Algorithms, Chapter 7
 Hash tables
Thomas
H. Cormen, Charles E. Leiserson and Ronald L. Rivest:
Introduction to Algorithms, Chapter 11
 Network flows
Lecture
Slides for Algorithm Design by Jon Kleinberg and Éva
Tardos: Nework Flow I, II, III.
 Linear Programing
Lecture
Slides for Algorithm Design by Jon Kleinberg and Éva
Tardos: Linear Programing I.
 Approximation algorithms
Lecture
Slides for Algorithm Design by Jon Kleinberg and Éva
Tardos: Approximation algorithms.
 Robin Hood hashing:
https://web.stanford.edu/class/cs166/lectures/13/Small13.pdf
(this also contains stuff about other hashing methods)
 Cuckoo hashing:
http://www.itu.dk/people/pagh/papers/cuckooundergrad.pdf
 Tabulation hashing:
Wikipedia
 Bloom filter:
https://people.eecs.berkeley.edu/~daw/teaching/cs170s03/Notes/lecture10.pdf
https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf
 Treap and skip lists:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10treaps.pdf
 kth element search
Thomas
H. Cormen, Charles E. Leiserson and Ronald L. Rivest:
Introduction to Algorithms, Chapter 9 and 14.1
 Selfadjusting data structures:
http://www.dcc.fc.up.pt/~pribeiro/aulas/taa1516/selfadjusting.pdf
 Detailed analysis of MovetoFront:
http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/mtf.pdf
 Detailed analysis of splay trees:
https://lcbb.epfl.ch/algs11/splayanalysis.pdf
 Algorithms on
random graphs, for example. 3 coloring in O(1),
Different random graph models: ErdősRényi and Barabási
model comparison.
 Fast
arithmetics, multiplication, Katsuba algorithm,
SchönhageStrassen multiplication, discrete Fourier
transform
 Data
Structures for disjoint sets (unionfind with path
compression and its analysis). Persistent data
structures, lazy evaluation.
 Homogeneous
and inhomogeneous linear recurrences, the AkraBazzi
formula, master theorem. Examples of recursive
algorithms for estimating the number of steps.
 Ways to deal
with difficult problems: fundamental techniques of
parametric complexity, pruning the search tree, kernel
technique, some basic examples.
 Nontrivial
exponential algorithms for difficult problems, fast
matrix multiplication, maximal independent set of
vertices, traveling salesman problem, chromatic number,
subsetsum problem, local search.
 Matching in
general graphs, EdmondsGallai decomposition