Lecturer(s)
|
-
Beránek Ladislav, doc. Ing. CSc.
|
Course content
|
Content: 1. Introduction to algorithms, definitions, basic approaches. 2. Temporal and spatial complexity 3. Data structures - compact and 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 skeleton, flows in a graph 8. Search in text 9. Algorithm design - Divide and conquer 10. Design of algorithms - Hungry algorithm 11. Algorithm design - Dynamic programming 12. Hard problems - NP-complete problems, Approximation algorithms
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), Demonstration, Work with multi-media resources (texts, internet, IT technologies)
- Class attendance
- 56 hours per semester
- Semestral paper
- 28 hours per semester
- Preparation for classes
- 28 hours per semester
- Preparation for credit
- 12 hours per semester
- Preparation for exam
- 36 hours per semester
|
Learning outcomes
|
The aim of the course is to get acquainted 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, text search) and with algorithm design methods (divide and conquer, hungry algorithm, dynamic programming) . Knowledge of Python, C # or Java is suitable for completing the course.
Students will master the basic algorithmic constructions and procedures for the design and implementation of algorithms and know the basics of algorithm analysis.
|
Prerequisites
|
Prerequisite is a basic knowledge of any programming language.
|
Assessment methods and criteria
|
Test, Seminar work
Processing of exercises. Successful passing of the credit test and written exam.
|
Recommended literature
|
-
Edmonds, J. How to Think about Algorithms. Cambridge: University Press, 2008.
-
MAREŠ, Martin a Tomáš VALLA. Průvodce labyrintem algoritmů. Praha: CZ.NIC, z.s.p.o., 2017. ISBN 978-80-88168-19-5.
-
McMillan, M. Data Structures and Algorithms Using C#. New York: Cambridge University Press, 2007.
-
Roughgarden, T. Algorithms Illuminated (Part 3): Greedy Algorithms and Dynamic Programming. Boston: Soundlikeyourself Publishing, LLC, 2019. ISBN 978-0999282946.
-
Wróblewski, Piotr; Goner, Jakub. Algoritmy. 1. vydání. Brno : Computer Press, 2015. ISBN 978-80-251-4126-7.
|