Advances Datastructures and Techniques for Analysis of Algorithms
(Haladó adatszerkezetek és algoritmuselemzési technikák)
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.

Previous semesters: 2016/2017/1