Algorithms 2 0800-ALGOR2
1. Backtracking algorithms
a. Knight's tour problem.
b. Eight queens puzzle
c. general backtracking algorithm
d. Hanoi tower problem, permutations, combinations etc. in backtracking problem view.
2. Knapsack problems and its versions.
3. Algorithms and data structures for set operations.
a. Naive set representation.
b. Hashing for sets and dictionaries.
c. Balanced trees.
d. Link lists.
e. Union-find problem.
4. Strongly connected components.
5. Euler and Hamilton graphs, travelling salesman problem.
6. Maximum flow problem
7. Complexity classes
8. Fibonacci heap
9. Automatas and formal languages.
10. String searching problem.
a. Naive algorithm.
b. Fast algorithms, connection with automatas.
c. Suffix trees.
11. Boolean satisfiability problem.
12. Computational geometry.
Total student workload
Learning outcomes - knowledge
Learning outcomes - skills
Learning outcomes - social competencies
Teaching methods
Observation/demonstration teaching methods
Expository teaching methods
- problem-based lecture
Exploratory teaching methods
- points system
- observation
- case study
- experimental
- classic problem-solving
- situational
- brainstorming
- project work
Online teaching methods
- exchange and discussion methods
- integrative methods
- methods developing reflexive thinking
- cooperation-based methods
Prerequisites
Course coordinators
Assessment criteria
1. Present work.
2. Tests.
3. Task lists.
5. Exam.
Bibliography
A. V. Aho, J. E. Hopcroft, J. D. Ullman.
Projektowanie i analiza algorytmów.
Helion, Warszawa, 2003.
A. V. Aho, J. E. Hopcroft, J. D. Ullman.
Projektowanie i analiza algorytmów.
Państwowe Wydawnictwa Naukowe, Warszawa, 1983.
Niklaus Wirth.
Algorytmy + Struktury Danych = Programy.
Wydawnictwa Naukowo–Techniczne, Warszawa, wydanie 2, 1989.
T. H. Cormen, C. E. Leiserson, R. L Rivest.
Wprowadzenie do algorytmów.
Wydawnictwa Naukowo–Techniczne, Warszawa, 1997.
A. V. Aho, J. D. Ullman.
Wykłady z informatyki z przykładami w języku C.
Helion, Warszawa, 2003.
L. Banachowski, K. Diks, W. Rytter.
Algorytmy i struktury danych.
Wydawnictwa Naukowo–Techniczne, Warszawa, 1996.
M. M. Sysło, N. Deo, J. Kowalik.
Algorytmy optymalizacji dyskretnej.
Państwowe Wydawnictwa Naukowe, Warszawa, 1993.
D. Harel.
Rzecz o istocie informatyki. Algorytmika.
Wydawnictwa Naukowo–Techniczne, Warszawa, 1992.
L. Banachowski, A. Kreczmar, W. Rytter.
Analiza algorytmów i struktur danych.
Wydawnictwa Naukowo–Techniczne, Warszawa, 1989.
L. Banachowski, A. Kreczmar.
Elementy analizy algorytmów.
Wydawnictwa Naukowo–Techniczne, Warszawa, 1982.
D. E. Knuth.
Sztuka Programowania, wolumen I–III.
Wydawnictwa Naukowo–Techniczne, 2002.
Additional information
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: