460-2003/04 – Algorithms II (ALG II)

Gurantor departmentDepartment of Computer ScienceCredits5
Subject guarantordoc. Mgr. Jiří Dvorský, Ph.D.Subject version guarantordoc. Mgr. Jiří Dvorský, Ph.D.
Study levelundergraduate or graduateRequirementCompulsory
Year2Semesterwinter
Study languageCzech
Year of introduction2019/2020Year of cancellation
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
DVO26 doc. Mgr. Jiří Dvorský, Ph.D.
REC0021 Ing. Radovan Rečka
SIG0033 Ing. Filip Šigut
VRO0018 Ing. David Vronka
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Graded credit 2+2
Part-time Graded credit 14+0

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:

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

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 codeAbbreviationTitleRequirement
460-2001 ALG I Algorithms I Compulsory
460-2055 OOP Object Oriented Programming Recommended

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 seminar 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

Full-time form (validity from: 2019/2020 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of pointsMax. počet pokusů
Graded credit Graded credit 100 (100) 51 3
        Průběžná aktivita Other task type 30  15 1
        Obhajoba projektu Project 30  15 1
        Závěrečná písemná práce Written test 40  21 2
Mandatory attendence participation: Participation in the exercises is compulsory and is monitored. The scope of the compulsory participation will be communicated to the students by the course supervisor at the beginning of the semester.

Show history

Conditions for subject completion and attendance at the exercises within ISP: Course completion requirements - Completion of all mandatory tasks within individually agreed deadlines. Attendance at exercises - The level of attendance at exercises is agreed by the student with the course supervisor at the beginning of the semester.

Show history

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2024/2025 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2024/2025 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan
2024/2025 (B0541A170008) Computational and Applied Mathematics P Czech Ostrava 2 Optional study plan
2024/2025 (B0541A170008) Computational and Applied Mathematics K Czech Ostrava 2 Optional study plan
2023/2024 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan
2023/2024 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2023/2024 (B0541A170008) Computational and Applied Mathematics P Czech Ostrava 2 Optional study plan
2023/2024 (B0541A170008) Computational and Applied Mathematics K Czech Ostrava 2 Optional study plan
2022/2023 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan
2022/2023 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2022/2023 (B0541A170008) Computational and Applied Mathematics K Czech Ostrava 2 Optional study plan
2022/2023 (B0541A170008) Computational and Applied Mathematics P Czech Ostrava 2 Optional study plan
2021/2022 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2021/2022 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan
2021/2022 (B0541A170008) Computational and Applied Mathematics P Czech Ostrava 2 Optional study plan
2021/2022 (B0541A170008) Computational and Applied Mathematics K Czech Ostrava 2 Optional study plan
2021/2022 (B2660) Computer Systems for the Industry of the 21st. Century P Czech Ostrava 1 Compulsory study plan
2020/2021 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan
2020/2021 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2020/2021 (B2660) Computer Systems for the Industry of the 21st. Century P Czech Ostrava 1 Compulsory study plan
2020/2021 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2020/2021 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan
2020/2021 (B0541A170008) Computational and Applied Mathematics P Czech Ostrava 2 Optional study plan
2020/2021 (B0541A170008) Computational and Applied Mathematics K Czech Ostrava 2 Optional study plan
2019/2020 (B0541A170008) Computational and Applied Mathematics P Czech Ostrava 2 Optional study plan
2019/2020 (B0541A170008) Computational and Applied Mathematics K Czech Ostrava 2 Optional study plan
2019/2020 (B0613A140014) Computer Science TZI P Czech Ostrava 2 Compulsory study plan
2019/2020 (B0613A140014) Computer Science TZI K Czech Ostrava 2 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

Assessment of instruction



2023/2024 Winter
2022/2023 Winter
2021/2022 Winter
2020/2021 Winter