BIE-EIA – Efficient Implementation of Algorithms

Annotation

Students learn to combine their programming skills (ability to design efficient algorithms) and HW knowledge (utilization of all available features of a particular processor and memory architecture). Students learn the basics of code tuning and optimization.

Lectures Program

  1. Efficient algorithms, asymptotic complexity and its practical disadvantages.
  2. Recap of basic computer architecture concepts (pipeline, vector instructions, cache, TLB).
  3. Optimal data structures and their combinations.
  4. Basic routines for numerical linear algebra (dense matrices).
  5. Basic routines for numerical linear algebra (sparse matrices).
  6. Models of cache behavior.
  7. [2] Source code transformations.
  8. Compilers and optimizations.
  9. Available math libraries.
  10. Multicore architectures.
  11. Multicore programming (OpenMP, Java).
  12. Models of cache behavior in multicore environments.

Labs Program

  1. Performance metrics.
  2. Algorithms for searching elements.
  3. Algorithms for searching patterns in text.
  4. Assignment No. 1.
  5. Sorting of arrays and linked lists.
  6. Sieve of Eratosthenes.
  7. Assignment No. 2.
  8. Sorting on a disk.
  9. Assignment No. 3.
  10. Graph algorithms.
  11. Encryption.
  12. Data compression.
  13. Checking the assignments.


Last modified: 7.9.2010, 11:09