|
Lecturer(s)
|
-
Slánský Vlastimil, doc. Ing. Ph.D.
|
|
Course content
|
1. Problem, algorithm, program. Programming language, program execution. Object, class, instance. 2. Generic programming, interface, polymorphism. Recursive programs. 3. Computational complexity, O, Omega and Theta sets. 4. Sorting. InsertSort, ShellSort, QuickSort, MergeSort. 5. Abstract data types. Collections. Stack - implementation by an array and by a linked structure. 6. Elliminating recursion using a custom stack. Queue - possible implementations. 7. List, Iterator, possible implementations. 8. Table, hash table, hash function. 9. Trees, binary search tree, balanced trees. 10. Graph, implementation by incidence list/matrix. Breadth-first search. 11. Topologic ordering, Depth-first search. 12. Priority queue, heap. 13. Formalization and classification of problems. Problem classes P, NP and NP-C
|
|
Learning activities and teaching methods
|
- Contact hours
- 52 hours per semester
- Preparation for comprehensive test (10-40)
- 13 hours per semester
- Preparation for an examination (30-60)
- 26 hours per semester
- Undergraduate study programme term essay (20-40)
- 39 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| to understand primitive data types used fro representing integers, floats and characters in a computer |
| to understand basic control flow in imperative programming |
| to describe programming principles in imperative programming language, with focus on control flow |
| to demonstrate knowledge of basic math terminology and methods |
| Skills |
|---|
| to use some common integrated development environment on user level |
| to perform basic mathematical derivations and calculations |
| to construct simple programs in an imperative programming language |
| Competences |
|---|
| N/A |
| N/A |
| N/A |
| N/A |
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| to interpret statements on algorithm complexity and complexity classes O, Omega and Theta |
| to interpret statements on problem complexity, to understand statements on complexity classes P, NP and NP-C |
| to describe the process of program execution in a computer, especially from the point of view of memory allocation in stack and on heap and the creation of stack frames |
| to determine the computational complexity of operations on perticular implementations of abstract data types, in particular with the standard implementations |
| to enumerate the most common sorting algorithms and to analyze their properties |
| to enumerate the most common abstract data types, to describe their possible implementations and their resulting properties |
| Skills |
|---|
| to analyze and to compare algorithms from the point of view of their complexity class |
| to implement programs using basic concepts of object oriented programming |
| to implement advanced programs for processing of dynamic data structures |
| to implememnt basic algorithm for procesing of graphs, i.e. the depth-first search, the breadth-first search and the topological ordering |
| to implement basic algorithms for processing of tree data structures, i.e. pre-, in- and post-order traversal |
| to design advanced data structures based on particular assignments, especially focusing on the choice of an appropriate imlementation of an abstract data type |
| to build custom implementations of asbtract data types tailored for particular programming tasks |
| Competences |
|---|
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecture |
| Lecture with visual aids |
| Lecture supplemented with a discussion |
| Practicum |
| E-learning |
| Self-study of literature |
| Cooperative instruction |
| Task-based study method |
| Individual study |
| Skills |
|---|
| Lecture |
| Lecture with visual aids |
| Lecture supplemented with a discussion |
| Practicum |
| E-learning |
| Task-based study method |
| Cooperative instruction |
| Self-study of literature |
| Individual study |
| Competences |
|---|
| Lecture |
| Lecture with visual aids |
| Practicum |
| E-learning |
| Task-based study method |
| Self-study of literature |
| Individual study |
| assessment methods |
|---|
| Knowledge |
|---|
| Oral exam |
| Written exam |
| Combined exam |
| Test |
| Continuous assessment |
| Seminar work |
| Skills |
|---|
| Oral exam |
| Written exam |
| Combined exam |
| Test |
| Continuous assessment |
| Seminar work |
| Competences |
|---|
| Oral exam |
| Written exam |
| Combined exam |
| Test |
| Seminar work |
| Continuous assessment |
|
Recommended literature
|
-
Jim Keogh, Ken Davidson. Datové struktury bez předchozích znalostí. 2006.
-
Ryant, Ivan. Algoritmy a datové struktury objektově. Vydání první. 2017. ISBN 978-80-270-1660-0.
|