The subject explains the main contemporary approaches to
the design of algorithms. These approaches include various analysis techniques, design methods and computation models. We describe how we can:
- apply algorithm engineering (which aims to bridge the gap between theory and practice),
- use multi-level memory hierarchy and design cache-oblivious algorithms,
- speed up exact exponential algorithms (e.g., by branching techniques),
- design parameterized algorithms (algorithms that take advantage of specific inputs bound to a parameter),
- design approximation algorithms (fast algorithms that return approximate results of good quality),
randomized algorithms (fast algorithms that return uncertain results of good confidence),
- design quantum algorithms (algorithms that integrate quantum reality into computation).
Finally, we describe the concept of the realistic
(as opposed to the worst-case) complexity of algorithms and computational problems.
- nosilec: Borut Robič