Algorithms II

* Exchange students do not have to consider this information when selecting suitable courses for an exchange stay.

Course Unit Code460-2003/02
Number of ECTS Credits Allocated5 ECTS credits
Type of Course Unit *Compulsory
Level of Course Unit *First Cycle
Year of Study *First Year
Semester when the Course Unit is deliveredSummer Semester
Mode of DeliveryFace-to-face
Language of InstructionCzech, English
Prerequisites and Co-Requisites
PrerequisitiesCourse Unit CodeCourse Unit Title
460-2001Algorithms I
Name of Lecturer(s)Personal IDName
DVO26doc. Mgr. Jiří Dvorský, Ph.D.
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.
Learning Outcomes of the Course Unit
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.
Course Contents
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.
Recommended or Required Reading
Required Reading:
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.

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. Algoritmy v C. Praha: SoftPress, 2003. ISBN 80-864-9756-9.
WRÓBLEWSKI, Piotr. Algoritmy. Brno: Computer Press, 2015. ISBN 978-80-251-4126-7.
WIRTH, N. Algoritmy a štruktúry údajov, Alfa, Bratislava 1989.
Studijní opora (skripta), dostupné na stránkách garanta předmětu, www.cs.vsb.cz/dvorsky
Recommended Reading:
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.
STROUSTRUP, Bjarne. C programovací jazyk. Praha: Softwarové Aplikace a Systémy, 1997. ISBN 80-901-5072-1.
VIRIUS, Miroslav. Pasti a propasti jazyka C. 2., aktualiz. a rozš. vyd. Brno: CP Books, 2005. ISBN 80-251-0509-1.
SCHILDT, Herbert. Nauč se sám C: [poznej, vyzkoušej, používej]. Praha: SoftPress, 2001. ISBN 80-864-9713-5.
ECKEL, Bruce. Myslíme v jazyku C. Praha: Grada, 2000. Knihovna programátora (Grada). ISBN 80-247-9009-2.
Planned learning activities and teaching methods
Lectures, Tutorials
Assesment methods and criteria
Task TitleTask TypeMaximum Number of Points
(Act. for Subtasks)
Minimum Number of Points for Task Passing
Graded exercises evaluationGraded credit100 (100)51
        Průběžný test znalostíOther task type20 10
        Obhajoba projektuProject40 21
        Závěrečná písemná práceWritten test40 20