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 algorithms1La
(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. AddisonWesley Professional, 1998.
 S. Lipschutz: Data Structures. McGrawHill, 2005.
 N. Wirth: Algorithms + Data Structures = Programs. Prentice Hall, 1976.
 A. Aho, J. Hopcroft, J. Ullman: Data Structures and Algorithms. AddisonWesley, 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: Bruteforce, KnuthMorrisPratt, RabinKarp, Dömölkyfilter, KnuthMorrisPratt algorithms.
 Lossless data compression. Prefixfree codes, codetree, Huffman code. The compression algorithm of LempelZivWelch.
 epresentation of graphs. Breadthfirst search, single source shortest paths: Dijkstra’s algorithm and BellmanFord algorithm, minimum spanning trees: algorithms of Prim and Kruskal, all pairs shortest paths: WarshallFloyd algorithm. Depthfirst search, topological ordering of DAGs, strongly connected components of graphs.