I063 Algorithm Design II

Faculty of Informatics
Spring 2004
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Timetable
Tue 10:00–11:50 D2
Prerequisites (in Czech)
SOUHLAS
.
Course Enrolment Limitations
The course is only offered to the students of the study fields 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.
  • The design and application of effective data structures. Binomial and Fibonacci heaps. Splay trees. Union-find data structure.
  • Advanced design techniques -- divide et impera, dynamic programming, greedy algorithms, backtracking. Theoretical foundations and applications.
  • The design of randomized algorithms -- input randomization, random search, control randomization, symetry breaking. Expected vs. average running time. Las Vegas and Monte Carlo algorithms. Derandomization. Applications: searching trees, independent sets.
  • 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. Probabilistic on-line algorithms. Applications: paging, robot motion.
Literature
  • Brassard,G.- Bratley,P. Fundamentals of algorithmics. Prentice Hall, 1996
  • Cormen,T.H. - Leiserson,C.E. - Rivest,R.L. Introduction to algorithms. MIT Press, 1990
  • Kozen, D. The Design and Analysis of Algorithms. Springer-Verlag, 1992
  • Motwani,R. - Raghavan,P. Randomized algorithms. Cambridge University Press, 1995
Assessment methods (in Czech)
Predmet sa otvara posledny krat a je urceny studentom, ktori mali zapisany predmet I063 semestri ja studiaro 2003, ale v tomto semestri predmet neukoncili. Vyuka sa bude konat formou indiviualneho studia.
Language of instruction
Czech
Further Comments
The course is taught last offered.
The course is also listed under the following terms Spring 1998, Spring 1999, Spring 2000, Spring 2001, Spring 2002, Spring 2003.

I063 Algorithm Design II

Faculty of Informatics
Spring 2003
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
doc. Ing. RNDr. Barbora Bühnová, Ph.D. (assistant)
Mgr. Tomáš Hanžl (assistant)
RNDr. Lukáš Hejtmánek, Ph.D. (assistant)
Mgr. Pavel Krčál (assistant)
Mgr. Petr Liška (assistant)
Mgr. Pavel Moravec (assistant)
doc. Mgr. Adam Rogalewicz, Ph.D. (assistant)
Mgr. Jitka Žídková (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Timetable
Tue 8:00–9:50 D1
Prerequisites
( I002 Algorithms I || IB002 Algorithms I )&&! IB108 Algorithm Design II &&(!NOW( IB108 Algorithm Design II ))
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.
  • The design and application of effective data structures. Binomial and Fibonacci heaps. Splay trees. Union-find data structure.
  • Advanced design techniques -- divide et impera, dynamic programming, greedy algorithms, backtracking. Theoretical foundations and applications.
  • The design of randomized algorithms -- input randomization, random search, control randomization, symetry breaking. Expected vs. average running time. Las Vegas and Monte Carlo algorithms. Derandomization. Applications: searching trees, independent sets.
  • 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. Probabilistic on-line algorithms. Applications: paging, robot motion.
Literature
  • Brassard,G.- Bratley,P. Fundamentals of algorithmics. Prentice Hall, 1996
  • Cormen,T.H. - Leiserson,C.E. - Rivest,R.L. Introduction to algorithms. MIT Press, 1990
  • Kozen, D. The Design and Analysis of Algorithms. Springer-Verlag, 1992
  • Motwani,R. - Raghavan,P. Randomized algorithms. Cambridge University Press, 1995
Language of instruction
Czech
Further Comments
The course is taught last offered.
Teacher's information
http://www.fi.muni.cz/usr/cerna/NAII/i063.html
The course is also listed under the following terms Spring 1998, Spring 1999, Spring 2000, Spring 2001, Spring 2002, Spring 2004.

I063 Design of Algorithms II

Faculty of Informatics
Spring 2002
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Mgr. Pavel Krčál (assistant)
doc. Mgr. Radek Pelánek, Ph.D. (assistant)
doc. Mgr. Adam Rogalewicz, Ph.D. (assistant)
Mgr. Jitka Žídková (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Timetable
Wed 10:00–11:50 D2
Prerequisites
I002 Algorithms I && M010 Combinatorics and Graph Theory
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.
  • The design and application of effective data structures. Binomial and Fibonacci heaps. Splay trees. Union-find data structure.
  • Advanced design techniques -- divide et impera, dynamic programming, greedy algorithms, backtracking. Theoretical foundations and applications.
  • The design of randomized algorithms -- input randomization, random search, control randomization, symetry breaking. Expected vs. average running time. Las Vegas and Monte Carlo algorithms. Derandomization. Applications: searching trees, independent sets.
  • 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. Probabilistic on-line algorithms. Applications: paging, robot motion.
Literature
  • Brassard,G.- Bratley,P. Fundamentals of algorithmics. Prentice Hall, 1996
  • Cormen,T.H. - Leiserson,C.E. - Rivest,R.L. Introduction to algorithms. MIT Press, 1990
  • Kozen, D. The Design and Analysis of Algorithms. Springer-Verlag, 1992
  • Motwani,R. - Raghavan,P. Randomized algorithms. Cambridge University Press, 1995
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i063.html
The course is also listed under the following terms Spring 1998, Spring 1999, Spring 2000, Spring 2001, Spring 2003, Spring 2004.

I063 Design of Algorithms II

Faculty of Informatics
Spring 2001
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Timetable
Mon 9:00–10:50 D2
Prerequisites
I002 Algorithms I && M010 Combinatorics and Graph Theory
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.
  • The design and application of effective data structures. Binomial and Fibonacci heaps. Splay trees. Union-find data structure.
  • Advanced design techniques -- divide et impera, dynamic programming, greedy algorithms, backtracking. Theoretical foundations and applications.
  • The design of randomized algorithms -- input randomization, random search, control randomization, symetry breaking. Expected vs. average running time. Las Vegas and Monte Carlo algorithms. Derandomization. Applications: searching trees, independent sets.
  • 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. Probabilistic on-line algorithms. Applications: paging, robot motion.
Literature
  • BRASSARD, Gilles and Paul BRATLEY. Fundamentals of algorithmics. London: Prentice-Hall International, 1996, xix, 524 s. ISBN 0-13-073487-X. info
  • MOTWANI, Rajeev and Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
  • KOZEN, Dexter C. The Design and Analysis of Algorithms. New York: Springer-Verlag, 1992, 320 s. ISBN 0387976876. info
  • CORMEN, Thomas H., Charles Eric LEISERSON and Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i063.html
The course is also listed under the following terms Spring 1998, Spring 1999, Spring 2000, Spring 2002, Spring 2003, Spring 2004.

I063 Design of Algorithms II

Faculty of Informatics
Spring 2000
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Prerequisites
I002 Algorithms I && M010 Combinatorics and Graph Theory
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.
  • The design and application of effective data structures. Binomial and Fibonacci heaps. Splay trees. Union-find data structure.
  • Advanced design techniques -- divide et impera, dynamic programming, greedy algorithms, backtracking. Theoretical foundations and applications.
  • The design of randomized algorithms -- input randomization, random search, control randomization, symetry breaking. Expected vs. average running time. Las Vegas and Monte Carlo algorithms. Derandomization. Applications: searching trees, independent sets.
  • 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. Probabilistic on-line algorithms. Applications: paging, robot motion.
Literature
  • BRASSARD, Gilles and Paul BRATLEY. Fundamentals of algorithmics. London: Prentice-Hall International, 1996, xix, 524 s. ISBN 0-13-073487-X. info
  • MOTWANI, Rajeev and Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
  • KOZEN, Dexter C. The Design and Analysis of Algorithms. New York: Springer-Verlag, 1992, 320 s. ISBN 0387976876. info
  • CORMEN, Thomas H., Charles Eric LEISERSON and Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Language of instruction
Czech
Further Comments
The course is taught annually.
The course is taught: every week.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i063.html
The course is also listed under the following terms Spring 1998, Spring 1999, Spring 2001, Spring 2002, Spring 2003, Spring 2004.

I063 Design of Algorithms II

Faculty of Informatics
Spring 1999
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
I002 Design of Algorithms I && M010 Combinatorics and Graph Theory
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
Further Comments
The course is taught annually.
The course is taught: every week.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i063.html
The course is also listed under the following terms Spring 1998, Spring 2000, Spring 2001, Spring 2002, Spring 2003, Spring 2004.

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
The course is also listed under the following terms Spring 1999, Spring 2000, Spring 2001, Spring 2002, Spring 2003, Spring 2004.
  • Enrolment Statistics (recent)