460-2003/05 – Algorithms II (ALG II)
Gurantor department | Department of Computer Science | Credits | 5 |
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 | winter |
| | 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
The aim of the course is to acquaint students with object-oriented programming and to develop skills of students in the area of data structures. After completing the course, students will be able to:
Analyze the problem from the position given the OOP.
Develop and debug C++ program using OOP.
Use of binary trees and hash tables.
Assess the effectiveness of the solution of the problem.
Teaching methods
Lectures
Tutorials
Summary
This subject is a continuation of the course Algorithms I. In this course will be combined with the interpretation of object-oriented programming with the introduction of other frequently used data structures - binary trees and hash tables. OOP is seen rather to manage the implementation of a variety of tables, lists of operations to insert, search and subsequent deleting of elements than the proposal to more complex systems. This objective will be met in courses dealing with software engineering.
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 complete Algorihms I before this subject and also have the basic C++ programming skills and high school math knowledge.
Prerequisities
Co-requisities
Subject has no co-requisities.
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. Knapsack problem. Floyd algortihm.
Greedy algorithms. Prim's, 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.
Computer seminars
Gaussian elimination. AVL trees.
Implementation of heap and heapsort.
Hash tables.
B-trees.
Dynamic programming. Floyd algortihm.
Greedy algorithms. Prim's, Dijkstra's algorithms.
Huffman coding.
Simplex methods.
Backtracking. Eight queens problem.
Approximation algorithms for NP-hard problems.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.