| Algorithm design methods |
- applies basic algorithms on lists, trees and graphs (Data Structures)
|
- describes the most important principles of algorithm design and some of their applications
|
- applies the most important principles of algorithm design
- applies data structures with efficient amortized complexity
|
- applies and combines, as needed, different algorithm design methods in practical problem solving
|
| Graph algorithms |
- applies basic graph algorithms (Data Structures)
|
- describes several basic graph theoretical concepts and problems
|
- applies algorithms for several graph theoretical problems
|
- applies innovatively graph algorithms in practical problem solving
- solves optimization problems using network flow algorithms and linear programming (Discrete Optimisation)
|
| Analysis of algorithms |
- derives the worst-case time and space complexity of simple algorithms (Data Structures)
|
- describes the average case and amortized complexity of an algorithm
- classifies some algorithms according to their average or amortized complexity
|
- solves simple recurrences
- derives the average and amortized complexity of an algorithm
|
- solves more complex recurrences
|
| NP-completeness |
- describes Turing machines (Models of Computation)
|
- explains what NP-completeness means with respect to possibilities for solving these problems efficiently
- describes a number of NP-complete problems
|
- describes some basic theorems related to NP-completeness
- describes the P=NP problem
- forms polynomial reductions between problems and constructs algorithms for problems in NP
|
- describes a large number of NP-complete problems and their restricted versions solvable in polynomial time (Approximation Algorithms, Randomized Algorithms)
- knows other complexity classes and problems belonging to them (Computational Complexity)
|
Printer-friendly version