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, redblack 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  NPcomplete problems, Approximation algorithms

Learning activities and teaching methods

Monologic (reading, lecture, briefing), Demonstration, Work with multimedia 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 9788088168195.

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 9780999282946.

Wróblewski, Piotr; Goner, Jakub. Algoritmy. 1. vydání. Brno : Computer Press, 2015. ISBN 9788025141267.
