| Course Unit Code | 460-2003/04 |
|---|
| Number of ECTS Credits Allocated | 5 ECTS credits |
|---|
| Type of Course Unit * | Optional |
|---|
| Level of Course Unit * | First Cycle |
|---|
| Year of Study * | Second Year |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | |
|---|
| Prerequisities | Course Unit Code | Course Unit Title |
|---|
| 460-2001 | Algorithms I |
| 460-2055 | Object Oriented Programming |
| Name of Lecturer(s) | Personal ID | Name |
|---|
| DVO26 | doc. 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 |
|---|
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.
|
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
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.
|
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. 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 Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Graded credit | Graded credit | 100 (100) | 51 |
| Průběžná aktivita | Other task type | 30 | 15 |
| Obhajoba projektu | Project | 30 | 15 |
| Závěrečná písemná práce | Written test | 40 | 21 |