|
Lecturer(s)
|
-
Hrubý Filip, Mgr. MSc.
-
Roubal Tomáš, RNDr. Ph.D.
-
Valdman Jan, doc. Dr.rer.nat. Ing. DSc.
|
|
Course content
|
Topics: 1. Introduction to algorithms and basic concepts 2. Analysis of time and space complexity 3. Basic data structures: arrays, lists, stacks, queues, hashes 4. Heaps and priority queues, amortization 5. Sorting and searching in arrays 6. Search trees I: BST, operations and properties 7. Search trees II: AVL and Red-Black trees 8. Graph algorithms I: representation, BFS, DFS, topological sorting 9. Graph algorithms II: shortest paths (Dijkstra, Bellman-Ford) 10. Graph algorithms III: minimum spanning trees and network flows 11. Text search (KMP, Rabin-Karp, Boyer-Moore overview) 12. Design techniques I: divide and conquer, greedy algorithms 13. Design techniques II: dynamic programming, NP-completeness, and approximation algorithms Translated with DeepL.com (free version) Content of tutorials/seminar: The content of the seminar corresponds to the topics from the lectures.
|
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), E-learning
- Semestral paper
- 70 hours per semester
- Preparation for credit
- 40 hours per semester
- Preparation for exam
- 40 hours per semester
|
|
Learning outcomes
|
The aim of the course is to acquaint students with basic algorithms and methods of algorithm design. Students will actively master the basic algorithmic constructions and procedures for the design of algorithms. During the course, they will get acquainted with basic abstract data types (array, list, tree, dictionary), with frequently used algorithms (sorting, graph algorithms, string-searching algorithms) and with algorithm design methods (divide and conquer, greedy algorithm, dynamic programming, etc.).
Students will understand the basic principles of algorithms; they will create simple algorithms and use them when solving their programmers' problems.
|
|
Prerequisites
|
Prerequisites, preconditions: Basic knowledge of mathematics in the scope of high school curriculum.
|
|
Assessment methods and criteria
|
Written examination
Participation in the exercise, reporting the tasks in the exercise, preparation of a seminar paper (creation of a program in any programming language including the given algorithm), passing the written final test.
|
|
Recommended literature
|
-
CORMEN, Thomas H. Algorithms unlocked. Cambridge, MA: MIT Press, 2013. ISBN 978-0262518802..
-
EDMONDS, J. How to Think about Algorithms, Cambridge: Cambridge University Press, 2008. ISBN 978-0521614108..
-
ERICKSON, Jeff. Algorithms. 1. Urbana-Champaign, USA: Independently published. (dostupné na https://jeffe.cs.illinois.edu/teaching/algorithms/). ISBN 978-1792644832..
-
KLEINBERG, J., TARDOS, E. Algorithm design. 3. vyd. Boston: Pearson, 2011. ISBN 978-0273752332..
-
MAREŠ, M. a T. VALLA. Průvodce labyrintem algoritmů. Praha: CZ.NIC, z.s.p.o., 2017. CZ.NIC. (dostupné na: https://knihy.nic.cz/files/edice/pruvodce_labyrintem_algoritmu.pdf). ISBN 978-80-88168-19-5..
-
MILKOVÁ, E., BERÁNEK, L., VOBORNÍK, P. Algortihms: Explanation, Exercises and Visualization of the Basic Algorithmic Constructions. Gaudeamus, Hradec Králové, 2009. ISBN 978-80-7041-635-8..
-
PROKOP, Jiří. Algoritmy v jazyku C a C++. 3., aktualizované a rozšířené vydání. Praha: Grada, 2015. Průvodce (Grada). ISBN 978-80-247-5467-3..
-
SEDGEWICK, Robert. Algoritmy v C. Praha: SoftPress, 2003. ISBN 80-86497-56-9..
-
WRÓBLEWSKI, Piotr. Algoritmy. Brno: Computer Press. 2015. ISBN 978-80-251-4126-7..
|