FI:I063 Design of Algorithms II - Course Information

I063 Design of Algorithms II

Faculty of Informatics
Spring 1998

Extent and Intensity

2/0. 2 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).

Teacher(s)

prof. RNDr. Ivana Černá, CSc. (lecturer)

Guaranteed by

Contact Person: prof. RNDr. Ivana Černá, CSc.

Prerequisites

Before enrolling this course the students should go through I002 Design of Algorithms I and M010 Combinatorics and Graph Theory.

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

Syllabus

Complexity of algorithms -- worst-case and average-case analysis, amortized analysis.
Advanced analysis techniques -- the aggregate method, the accounting method, the potential method. Applications in designing effective data structures.
Advanced design techniques -- divide et impera, dynamic programming, greedy algorithms. Theoretical foundations and applications.
Selected topics -- matrix operations (decomposition and inverting matrices), polynomials and the FFT, string matching (the Knuth-Morris-Pratt algorithm, the Boyer-Moore algorithm).
The design of randomized algorithms -- expected vs. average running time. Las Vegas and Monte Carlo algorithms. Input randomization, random search, control randomization, symetry breaking. Examples.
The design of approximation algorithms -- relative approximation, approximation schemes. Applications: graph covering, traveling-salesman problem, scheduling, set covering, string matching.
Online algorithms and competitive analysis. Proof techniques -- potential functions, Yao's minimax principle.

Language of instruction

Czech

Teacher's information

http://www.fi.muni.cz/usr/cerna/i063.html