BIE-EFA – Efficient Algorithms

Annotation

Students get a solid overview of efficient algorithms for solving classical algorithmic problems: selecting, searching, sorting, and other basic forms of reshaping and processing tree-like data structures. Students are able to design and implement such algorithms, analyze their complexity, and develop an optimized efficient algorithm under specific requirements or constraints. They are able to recognize a proper algorithm variant for any specific usage.

Lecture Program

  1. Mathematical foundations for the theory of algorithmic complexity.
  2. Sorting in $n\log n$, advanced analysis of QuickSort.
  3. Sorting in linear time, sorting in external memory.
  4. Recursion, complexity analysis of recursive algorithms, transformation to iterative algorithms.
  5. Binary heaps, priority queues, binomial and Fibonacci heap.
  6. Dynamic programming.
  7. Search problem, 1D address search, mapping function.
  8. Hash tables, open and chained addressing, hash functions.
  9. Associative search, binary search trees, pattern matching in a text.
  10. Multidimensional search, multidimensional search trees.
  11. Balancing of search trees.

Labs Program

  1. Recap of discrete and asymptotic mathematics.
  2. [2] Implementation, stabilization, and in-depth complexity analysis of sorting algorithms.
  3. Implementation and complexity analysis of sorting in external memory.
  4. Comparison of recursive and iterative algorithm designs, mutual transformations.
  5. Advanced heaps.
  6. Dynamic programming techniques.
  7. Address search, design of mapping functions.
  8. Hash table usage, open and chained addressing.
  9. Search trees, binary search trees, pattern matching.
  10. Multidimensional search trees, closest neighbor.
  11. Balanced search trees.



Last modified: 7.9.2010, 11:08