Advanced Datastructures and Techniques for Analysis of
Algorithms
(Haladó adatszerkezetek és algoritmuselemzési technikák)
VISZDV05
PhD
course
Teachers: Katalin Friedl, Gyula Katona
Time and
location (2018/2019/1
semester): Wednesday and Thursday
12:15-13:45, IB134
Topics covered
so far:
Topics to review:
Planned topics:
1. Advanced Hashing: the concept of
universal hash, construction of universal hash
functions and k-independence, a perfect hash.
2. Surely the constant search time: Cuckoo hash. Searching
with small randomized error: Bloom filter.
3. Average case runing time analysis: linear hash probe,
randomized version of quicksort. Searching the
kth element, randomized and derandomized version,
Karger's algorithm for minimum cut.
4. Algorithms on random graphs, for example. 3 coloring in
O(1), Different random graph models: Erdős-Rényi and
Barabási model comparison.
5-6. Advanced data structures and their analysis: skip list,
treap, splay tree, suffix tree (applications in
bioinformatics: overlap search, longest common sub-word),
trie
7. Binomial heap, Fibonacci heap. Amortized analysis
(bankers method and potentials), application of Fibonacci
heap.
8. Data Structures for disjoint sets (union-find with path
compression and its analysis). Persistent data structures,
lazy evaluation.
9. Homogeneous and in-homogeneous linear recurrences, the
Akra-Bazzi formula, master theorem. Examples of recursive
algorithms for estimating the number of steps.
10. Ways to deal with difficult problems: fundamental
techniques of parametric complexity, pruning the search
tree, kernel technique, some basic examples.
11. Nontrivial exponential algorithms for difficult
problems, fast matrix multiplication, maximal independent
set of vertices, traveling salesman problem, chromatic
number, subsetsum problem, local search.
12. 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.
13. Compressed Sensing, sparse solutions of under defined
linear systems, L_1-minimization with linear programming.
Applications: towards the single-pixel camera.