Subject » BMEVISZDV05
Advanced Datastructures and Techniques for Analysis of Algorithms
Haladó adatszerkezetek és algoritmuselemzési technikák
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Haladó adatszerkezetek és algoritmuselemzési technikák
Advanced Datastructures and Techniques for Analysis of Algorithms
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZDV05 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | vizsga | ||||||||||||
| Credits | 5 | ||||||||||||
| Subject coordinator |
DR. Katona Gyula
position: egyetemi tanár
contact:
katona.gyula@vik.bme.hu
|
||||||||||||
| Responsible department |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Faculty | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Subject website | http://cs.bme.hu/haladoadat/ | ||||||||||||
| Primary curriculum type | — | ||||||||||||
| Direct prerequisites – Strong prerequisite | none | ||||||||||||
| Direct prerequisites – Weak prerequisite | none | ||||||||||||
| Direct prerequisites – Parallel prerequisite | none | ||||||||||||
| Direct prerequisites – Milestone prerequisite | none | ||||||||||||
| Direct prerequisites – Exclusion | none |
Objectives
Programme
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.
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).
Learning outcomes
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Knowledge
No learning outcomes recorded.
Skills
No learning outcomes recorded.
Attitudes
No learning outcomes recorded.
Autonomy and responsibility
No learning outcomes recorded.
Oktatási módszertan
4 hours of lectures per week.
Tanulástámogató anyagok
Online források
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
Recommended preliminary knowledge for completing the subject
Knowledge type competencies
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
Basic data structures and algorithms.
Please check http://cs.bme.hu/haladoadat/ for more details.
Skill type competencies
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Recommended (non-compulsory) preliminary competencies
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
Basic data structures and algorithms.
Please check http://cs.bme.hu/haladoadat/ for more details.
General rules
Requirements:
Signature: Homework
Final: Oral exam
Assessment methods
In-term assessments
No detailed assessments provided.
Weight of in-term assessments
No weights provided.
Exam-period assessments
No detailed assessments provided.
Weight of exam elements
No weights provided.
Grade calculation
No grade thresholds provided.
Attendance requirements
No attendance requirements provided.
Rules for retake and resubmission
Not provided.
Short description
Not provided.
Detailed description
Not provided.
Recommended courses
Not provided.
Workload to complete the subject
No workload breakdown provided.
Validity of subject requirements
Requirements valid from:
—
Requirements valid until:
—
Curriculum placement
No curriculum placements recorded for this subject version.