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: 2024. október 25.

    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. 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: hiring problem, randomized version of  quicksort. 
     
    4. Excpected height of a randomly generated binary search tree, 3 coloring in O(1).

    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. Nework flows: Edmonds-Karp algorithm, Dinitz algorithm, applications.

     
    8. Data Structures for disjoint sets (union-find with path compression and its analysis). Persistent data structures, lazy evaluation.
     
    9. Maximum size matchings in non-bipartite graphs, Edmonds algorithm.
     
    10. Fast matrix multiplication , Karatsuba algorithm.
     
    11. Parametric complexity: Kernel tachnique, dynamic programming.
     
    12. Parametric complexity: Iterative compressing, randomized algorithms.
     
    13. Random graph modells: Erdős-Rényi, Barabasi, finding communities in social networks.
     


    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. Katalin Friedl, associate professor, Department of Computer Science and Information Theory

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