Back
460-2003/04 – 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
1
Semester
summer
Study language
Czech
Year of introduction
2019/2020
Year of cancellation
Intended for the faculties
FEI
Intended for study types
Bachelor
Instruction secured by
Login
Name
Tuitor
Teacher 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 study
Way 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 code
Abbreviation
Title
Requirement
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
Part-time form (validity from: 2019/2020 Winter semester)
Task name
Type of task
Max. number of points
(act. for subtasks)
Min. number of points
Max. počet pokusů
Graded credit
Graded credit
100
(100)
51
3
Průběžná aktivita
Other task type
30
15
2
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
Valid from
Valid until
Mandatory attendence participation
Apr 3, 2019 3:55:00 PM
Sep 16, 2022 4:50:57 PM
Every student has to obtain at least the minimum number of points for each task.
Conditions for subject completion and attendance at the exercises within ISP:
Course completion requirements - Completion of all mandatory tasks within individually agreed deadlines.
Show history
Valid from
Valid until
Conditions for subject completion and attendance at the exercises within ISP
Sep 16, 2022 4:50:57 PM
Sep 16, 2022 4:51:13 PM
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.
Occurrence in study plans
Academic year
Programme
Branch/spec.
Spec.
Zaměření
Form
Study language
Tut. centre
Year
W
S
Type 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
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 name
Academic year
Form of study
Study language
Year
W
S
Type of block
Block owner
Assessment of instruction
2022/2023 Winter
2021/2022 Winter
2020/2021 Winter