460-2003/02 – 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 | 2013/2014 | Year of cancellation | 2019/2020 |
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:
Additional study materials
Way of continuous check of knowledge in the course of semester
Implementation and presentation.
Programming applications to simple exercises.
E-learning
Other requirements
Students are expected to know high school math and computer skills at users level.
Prerequisities
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
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction