Annotation
This course is one of the introductory programming courses. The course aims to introduce students to algorithmic problem solving techniques. The algorithms and data structures discussed will be demonstrated in C++. Students are encouraged to analyze algorithmic problems and to synthesize solutions from smaller units.
Lecturer
doc. Mgr. Jiří Dvorský, Ph.D.
Teaching
Subject syllabus:
- Introductory Lesson, Course Organization
- Introduction
- What Is an Algorithm
- Fundamentals of Algorithmic Problem Solving
- Important Problem Types
- Fundamental Data Structures
- Fundamentals of the Analysis of Algorithm Efficiency
- The Analysis Framework
- Asymptotic Notations and Basic Efficiency Classes
- Mathematical Analysis of Nonrecursive Algorithms
- Mathematical Analysis of Recursive Algorithms
- Brute Force and Exhaustive Search
- Selection Sort and Bubble Sort
- Sequential Search
- Brute-Force String Matching
- Closest-Pair Problem
- Convex-Hull Problem
- Exhaustive Search - Traveling Salesman Problem and Knapsack Problem
- Depth-First Search
- Breadth-First Search
- Decrease and Conquer
- Insertion Sort
- Topological Sorting
- Generating Permutations
- Generating Subsets
- Binary Search
- Computing a Median
- Interpolation Search
- Searching and Insertion in a Binary Search Tree
- Divide and Conquer
- Mergesort
- Quicksort
- Binary Tree Traversals and Related Properties
- Multiplication of Large Integers
- Strassen’s Matrix Multiplication
- The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer
Lectures and Seminars
Lectures are held every Wednesday from 10:45 to 12:15 in room E238. The seminar takes place immediately after the lecture in classroom EB113.
Credits
To be added
Study literature
Compulsory literature
- LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3rd ed. Boston: Pearson, 2012. ISBN 978-0-13-231681-1.
- CORMEN, Thomas H. Introduction to algorithms. 2nd ed. Cambridge, Mass.: MIT Press, 2001. ISBN 02-620-3293-7.
- CORMEN, Thomas H., Charles Eric LEISERSON, Ronald L. RIVEST a Clifford STEIN, [2022]. Introduction to algorithms. Fourth edition. Cambridge, Massachusetts: The MIT Press. ISBN 978-026-2046-305.
- SEDGEWICK, Robert. Algorithms in C. 3rd ed. Reading, Mass: Addison-Wesley, 1998. ISBN 978-020-1350-883.
Recommended literature
- STROUSTRUP, Bjarne. The C++ programming language. Fourth edition. Upper Saddle River, NJ: Addison-Wesley, 2013. ISBN 978-0321563842.
- SCHILDT, Herbert. Teach yourself C++. 3rd ed. Berkeley: Osborne McGraw-Hill, 1998. ISBN 978-0078823923.
Slides
Slides for the course can be downloaded here.
Software
Development environment for C++
- Microsoft Visual Studio Community 2022 is available for classroom use.
- I recommend downloading this development environment for home study. In general, however, any development environment and compiler that supports at least the C++17 specification can be used.
Other software
Other software that you will find useful when creating your programs:
- Source code documentation system Doxygen
- Typesetting system LaTeX