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 course

    free selective 
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZDV05   4/0/0/v 5  
    3. Course coordinator and department Dr. Katona Gyula,
    Web page of the course http://cs.bme.hu/haladoadat/
    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.

    Please check http://cs.bme.hu/haladoadat/ for more details.

    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 óra56
    Félévközi készülés órákra28
    Felkészülés zárthelyire
    Házi feladat elkészítése28
    Kijelölt írásos tananyag elsajátítása14
    Vizsgafelkészülés24
    Összesen150
    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