Mathematics BSc
Course description
2013.
Course description
2013.
Design and analysis of algorithms 2
| Hours lect+pc |
Credits lect+pc |
Assessment | Specialization | Course code lect/pc |
Semester | Status |
|---|---|---|---|---|---|---|
| 2 + 2 | 2 + 3 | exam + term grade |
applied math. | mm1c1at5a mm1c2at5a |
5 | compulsory |
Course coordinator
- László Hunyadvári
- István Fekete
| Strong | Weak | Prerequisites | |
|---|---|---|---|
| Practice class | |||
|
Strong:
Design and analysis of algorithms1L-a
(mm1c1at4a)
| |||
| Lecture | |||
|
Weak:
practice class
| |||
Remarks
Syllabus designed by:
- László Hunyadvári, Department of Algorithms and their Applications, Faculty of Informatics.
- István Fekete, Department of Algorithms and their Applications, Faculty of Informatics.
Literature
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms. The MIT Press, 2009.
Recommended:
- D. E. Knuth: The Art of Computer Programming, I. and III. Addison-Wesley Professional, 1998.
- S. Lipschutz: Data Structures. McGraw-Hill, 2005.
- N. Wirth: Algorithms + Data Structures = Programs. Prentice Hall, 1976.
- A. Aho, J. Hopcroft, J. Ullman: Data Structures and Algorithms. Addison-Wesley, 1983.
Syllabus
- Search methods on associative data structures. Hash coding, hash tables, resolution of key collision by chaining and open addressing. How to construct good hash functions? Universal hashing.
- Sorting in linear time. Bucket sort, radix sort for lists. Least significant digit (LSD) and most significant digit (MSD) radix sorts.
- String matching methods and realizations by finite deterministic automata: Brute-force, Knuth-Morris-Pratt, Rabin-Karp, Dömölky-filter, Knuth-Morris-Pratt algorithms.
- Lossless data compression. Prefix-free codes, code-tree, Huffman code. The compression algorithm of Lempel-Ziv-Welch.
- epresentation of graphs. Breadth-first search, single source shortest paths: Dijkstra’s algorithm and Bellman-Ford algorithm, minimum spanning trees: algorithms of Prim and Kruskal, all pairs shortest paths: Warshall-Floyd algorithm. Depth-first search, topological ordering of DAGs, strongly connected components of graphs.