|
Lecturer(s)
|
-
Geyer Jakub, Mgr. Ph.D.
-
Valdman Jan, XXX MSc.
|
|
Course content
|
Topics: 1. Introduction to algorithms, definitions, basic approaches. 2. Temporal and spatial complexity. 3. Data structures: linked lists, stack, queue, heap. 4. Sorting and searching algorithms. 5. Search trees: BST, AVL, Red-Black trees. 6. Graph algorithms: representation of a graph in a computer, traversing a graph, the shortest path. 7. Graph algorithms: minimal spanning tree, flows in a graph. 8. String-searching algorithms. 9. Algorithm design: Divide and conquer. 10. Algorithm design: Greedy algorithm. 11. Algorithm design: Dynamic programming. 12. Difficult problems: NP-complete problems, approximation algorithms. 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..
|