460-2003/02 – 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 graduate
Study languageCzech
Year of introduction2013/2014Year of cancellation2019/2020
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
BIE0026 Ing. Martin Bielik
DOH089 Ing. Pavel Dohnálek, Ph.D.
DVO26 doc. Mgr. Jiří Dvorský, Ph.D.
PAP0084 Mgr. et Mgr. Richard Papřok
POL420 Ing. Marián Poláček
REV010 Ing. Lukáš Révay
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Graded credit 2+2
Combined Graded credit 10+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. 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

Implementation and presentation. Programming applications to simple exercises.

E-learning

Další požadavky na studenta

Students are expected to know high school math and computer skills at users level.

Prerequisities

Subject codeAbbreviationTitleRequirement
460-2001 ALG I Algorithms I Compulsory

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Introductory lecture - organizational matters, the sum necessary knowledge of the subject Algorithms I Linear data structures - abstract data structures, stack, queue, list Dynamic memory allocation - pointers, operators, references, dereference, memory allocation and deallocation Spojová implementation of linear data structures - use of OOP and dynamically allocated structures Graphs - basic concepts, graph as data structure, implementation of the graphs Graph traversal algorithms - depth and breadth first traversals Binary search trees I - basic concepts, search Binary search trees II - insertion, deletion, traversals Balanced and multiway trees - AVL-trees, Red-black trees. B-trees Hashing - hash table, collision resolving methods Pattern matching - searching for one or more samples, elementary lexical analysis of text Simple compiler - arithmetic and logical expressions compilation, postfix notation and its interpretation via the stack Problem solving techniques - divide and conquer, greedy, dynamic programming Responsibilities of computer exercises Repetition of the subject Algorithms I Implementation of stack, queue and list using array Dynamic memory allocation Linked list implementation Graphs, graph implementation options Graph traversal algorithms Binary trees Usage of hash tables Pattern matching The compiler is based on a recursive descent Project content Entering the project will aim to deal with the OOP.

Conditions for subject completion

Full-time form (validity from: 2013/2014 Winter semester, validity until: 2018/2019 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Graded exercises evaluation Graded credit 100 (100) 51
        Průběžný test znalostí Other task type 20  10
        Obhajoba projektu Project 40  21
        Závěrečná písemná práce Written test 40  20
Mandatory attendence parzicipation:

Show history
Combined form (validity from: 2013/2014 Winter semester, validity until: 2018/2019 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Graded exercises evaluation Graded credit 100 (100) 51
        První test Written test 20  10
        Druhý test Other task type 20  10
        Třetí test Other task type 20  10
        Obhajoba projektu Project 40  21
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2019/2020 (B2660) Computer Systems for the Industry of the 21st. Century P Czech Ostrava 1 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan
2018/2019 (B2660) Computer Systems for the Industry of the 21st. Century P Czech Ostrava 1 Compulsory study plan
2018/2019 (B3973) Automotive Electronic Systems P Czech Ostrava 1 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan
2017/2018 (B2660) Computer Systems for the Industry of the 21st. Century P Czech Ostrava 1 Compulsory study plan
2017/2018 (B3973) Automotive Electronic Systems P Czech Ostrava 1 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan
2016/2017 (B2660) Computer Systems for the Industry of the 21st. Century P Czech Ostrava 1 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner
V - ECTS - bc. 2014/2015 Full-time Czech Optional 401 - Study Office stu. block
V - ECTS - bc. 2013/2014 Full-time Czech Optional 401 - Study Office stu. block