|
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
-
applies and combines design methods to obtain efficient approximation algorithms (Approximation Algorithms)
-
applies dynamic programming fluently in practical problem solving (String Processing Methods: approximate string matching; Biological Sequence Analysis: viterbi, sequence alignments)
-
derives complex recursive algorithms (String Processing Methods: suffix sorting)
|
|
Graph algorithms |
-
applies basic graph algorithms (Data Structures)
|
-
describes several basic graph theoretical concepts and problems
|
-
applies algorithms for several graph theoretical problems
-
reduces related problems to maximum flow and describes the principles of how maximum flows are solved
|
-
applies innovatively graph algorithms in practical problem solving (Algorithms in Molecular Biology: applications of flows)
-
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)
|
-
differentiates concepts best / worst / amortized / average / expected case complexity
-
classifies some algorithms according to their respective complexity
|
-
solves simple recurrences
-
derives the complexity of simple combinatorial algorithms using an appropriate analysis method
|
-
solves more complex recurrences
-
derives approximation guarantees (Approximation Algorithms)
-
derives fluenty expected case bounds (Randomized algorithms)
-
applies amortized analysis in specialized algorithms (String Processing Methods: KMP, Aho-Corasick, suffix trees)
|
|
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)
|