Mathematics BSc
Course description
2013.
Borromean Rings
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 +
term grade		 applied math. mm1c1at4a
mm1c2at4a		 4 compulsory
Strong Weak Prerequisites
Practice class
Strong:
Programming fundamentalsL (im1c1pn2)
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.
↻