Time and
location (2020/2021/1
semester): Wednesday and Thursday
12:15-13: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.1-3, 3.1-2, 6.1-9.3, 10.1-13.4, 15.1-5, 22.1-25.2,
26.1-3, 34.1-5.
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 VISZAB03.) 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:
Topics to review:
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/cuckoo-undergrad.pdf
- Tabulation hashing:
Wikipedia
- Bloom filter:
https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture10.pdf
https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf
- Treap and skip lists:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-treaps.pdf
- k-th element search
Thomas
H. Cormen, Charles E. Leiserson and Ronald L. Rivest:
Introduction to Algorithms, Chapter 9 and 14.1
- Self-adjusting data structures:
http://www.dcc.fc.up.pt/~pribeiro/aulas/taa1516/selfadjusting.pdf
- Detailed analysis of Move-to-Front:
http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/mtf.pdf
- Detailed analysis of splay trees:
https://lcbb.epfl.ch/algs11/splay-analysis.pdf
- Algorithms on
random graphs, for example. 3 coloring in O(1),
Different random graph models: Erdős-Rényi and Barabási
model comparison.
- Data
Structures for disjoint sets (union-find with path
compression and its analysis). Persistent data
structures, lazy evaluation.
Homogeneous and
in-homogeneous linear recurrences, the Akra-Bazzi
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.
- Hybrid
solutions between worst-case and average-case analysis.
Smoothed Analysis, smoothed local search. Proof of
smoothed polynomial running time of 2-OPT local search
algorithm.