582630 Design and analysis of algorithms (luonnos 2.8.2016)

Principal theme Prerequisite knowledge Approaches the learning objectives Reaches the learning objectives Deepens the learning objectives
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)

 

02.08.2016 - 15:33 Veli Mäkinen
13.03.2011 - 21:43 Jyrki Kivinen