# Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Belépés
címtáras azonosítással

vissza a tantárgylistához   nyomtatható verzió

Advanced Datastructures and Techniques for Analysis of Algorithms

A tantárgy neve magyarul / Name of the subject in Hungarian: Haladó adatszerkezetek és algoritmuselemzési technikák

Last updated: 2020. augusztus 10.

 Budapest University of Technology and Economics Faculty of Electrical Engineering and Informatics PhD coursefree selective
 Course ID Semester Assessment Credit Tantárgyfélév VISZDV05 4/0/0/v 5
3. Course coordinator and department Dr. Katona Gyula,
4. Instructors

Dr. Judit Csima, associate professor, Department of Computer Science and Information Theory

Dr. Katalin Friedl, associate professor, Department of Computer Science and Information Theory

Dr. Gyula Katona, associate professor, Department of Computer Science and Information Theory

5. Required knowledge

Basic data structures and algorithms.

7. Objectives, learning outcomes and obtained knowledge In this course students are introduced to  modern, well-usable data structures. The algorithms focusing on the worst-case analysis does not give enough evidence for practical usability. The course aims to introduce a few methods for the analysis of estimates for the random case, and some other techniques  often used these days (eg. smoothed or parametric complexity analysis).
8. Synopsis
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.

14. Homework discussion.

9. Method of instruction 4 hours of lectures per week.
10. Assessment

Signature: Homework

Final: Oral exam

12. Consultations In office hours or by appointment.
13. References, textbooks and resources
Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (MIT Press 2009)
Motwani, Raghavan: Randomized Algorithms (Cambridge, 2000)
Hromkovic: Algorithmics for hard Problems (Springer, 2004)
Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh: Parameterized Algorithms (Springer 2015)
internernet recources
14. Required learning hours and assignment
 Kontakt óra 56 Félévközi készülés órákra 28 Felkészülés zárthelyire Házi feladat elkészítése 28 Kijelölt írásos tananyag elsajátítása 14 Vizsgafelkészülés 24 Összesen 150
15. Syllabus prepared by

Dr. Judit Csima, associate professor, Department of Computer Science and Information Theory

Dr. Katalin Friedl, associate professor, Department of Computer Science and Information Theory

Éva Hosszú, PhD student, Department of Telecommunications and Media Informatics

Dr. Gyula Katona, associate professor, Department of Computer Science and Information Theory

Dr. János Tapolcai, full professor, Department of Telecommunications and Media Informatics