460-2001/06 – Algorithms I (ALG I)
Gurantor department | Department of Computer Science | Credits | 4 |
Subject guarantor | doc. Mgr. Jiří Dvorský, Ph.D. | Subject version guarantor | doc. Mgr. Jiří Dvorský, Ph.D. |
Study level | undergraduate or graduate | Requirement | Compulsory |
Year | 2 | Semester | summer |
| | Study language | English |
Year of introduction | 2019/2020 | Year of cancellation | |
Intended for the faculties | FEI | Intended for study types | Bachelor |
Subject aims expressed by acquired skills and competences
Acquaint students with the basics of structured programming, the basics of C + +. After completing the course, students will be able to:
Work with integrated development environment for C++.
Define a describe basic programming constructions.
Develop and debug a simple program C++.
Use data structures such as array, list, etc.
Write a recursive function.
Use sorting and searching algorithms in their programs.
Teaching methods
Lectures
Tutorials
Summary
This subject is the introductory programming course. Students are expected to have the basic C++ knowledge and high school math knowledge. Discussed algorithms and data structures will be demonstrated in C++. A large emphasis is placed on practical implementation discussed algorithms and data structures. Students are encouraged analysis and synthesis solutions to the problems of smaller units.
Compulsory literature:
Recommended literature:
Way of continuous check of knowledge in the course of semester
Conditions for granting credit
Implementation and presentation of the project.
Programming applications to simple exercises.
Attendance on exercises.
E-learning
Other requirements
Students are expected to have the basic C++ knowledge and high school math knowledge.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Algorithm. Algorithmic problem solving strategies. Important problem types.
Analysis of complexity of algorithms.
Brute force strategy. SelectSort. BubbleSort. Sequential search. Convex hull problem. Closest pair problem.
Complete search strategy. Traveling salesman problem. Knapsack problem. Graph traversal.
Decrease and conquer strategy. InsertSort. Generate permutations and subsets. Binary search algorithm. Finding the median. Interpolation search. Searching and insertion in a binary search tree.
Divide and conquer strategy. QuickSort. MergeSort. Convex hull problem. Closest pair problem.
Computer seminars
Iterative algorithms complexity analysis.
Recursive algorithms complexity analysis.
Implementation of convex hull problem, closest pair problem.
Traveling salesman problem - experiments with complete search solution.
Graph traversal algorithms usage.
Generate permutations and subsets.
Implementation of binary search algorithm, interpolation search algorithm and median finding.
Binary search tree implementation.
Implementation of divide and conquer strategy solutions.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks