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:
- Transform and conquer strategy. Data presorting. Gaussian elimination. AVL trees. Representation change. Heap and heapsort. Horner's rule. Binary exponentation. Problem reduction strategy. Reduction to graph problems.
- Space-time trade-offs. Hashing. B-trees.
- Dynamic programming. Three basic examples. Knapsack problem. Floyd algorithm.
- Greedy algorithms. Prim's and Kruskal's algorithms. Dijkstra's algorithms. Huffman coding.
- Iterative improvement strategy. Simplex methods.
- Coping with the limitation of algorithm power. P, NP and NP-complete problems.
- Backtracking. Eight queens problem.
- Approximation algorithms for NP-hard problems.
The highlighted topics form the basis of the teaching this semester.
Lectures
Classes are held on a bi-weekly basis at 10:45 AM in my office EA441.
Credits
Credit will be given for completing several homework assignments. The assignment is available in the MS Teams environment.
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.
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