Mathematics BSc
Course description
2013.

Design and analysis of algorithms 1
Hours
lect+pc
Credits
lect+pc
Assessment Specialization Course code
lect/pc
Semester Status
2 + 2 2 + 3 exam +
applied math. mm1c1at4a
mm1c2at4a
4 compulsory
Course coordinator
Strong Weak Prerequisites
Practice class
Strong:
Lecture
Weak:
practice class
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
• Abstract concepts of programming: state space, problem specification, solution, abstract program. Constructing correct programs, program correctness proof. Simple widely used small programs.
• Algorithmic solvability of problems, time and space complexity, asymptotic estimation of resources, order of growth.
• Abstraction levels of data types: „abstract data type” (ADT), „abstract data structure” (ADS), representation (by arrays or pointers).
• Basic data structures: arrays, stacks, queues, priority queues, lists, trees.
• Selections: maximum, parallel minimum and maximum, kth largest element and median. Lower bound analysis.
• Sorting algorithms using comparisons. Principles of the sorting methods. Bubble sort, insertion sort and sorting with maximum search. Tournament sort, heapsort, quicksort, merge sort, Shell-sort, Batcher’s bitonic sort. Lower bounds of efficiency: worst case and average case analysis.
• Search methods on associative data structures (1). Sequential search, binary search, search trees, AVL-trees, B-trees.