|
Lecturer(s)
|
-
Slánský Vlastimil, doc. Ing. Ph.D.
|
|
Course content
|
1. Problem, algorithms, program. Program and programming language. Program execution. Object, class. 2. Linked data structured. Program correctness. Program analysis. 3. Abstract data type. Stack and queue. 4. Linked list. Examples of recursion. Recursive programs. 5. Recursion and stack. Tree, basic concepts. Binary tree. Binary search tree. 6. Graphs and their implementation. Graph search. Topological sort. 7. Direct-address tables. Hash tables. Hash function. 8. Priority queue. Heap. Sort using priority queue. 9. Sorting problem. Heap sort. Shell sort. Quicksort. Mergesort. 10.Generic programming. Inheritance. Interface. 11.Abstract problem. Algorithmically unsolvable problems. Lower bound for sorting. Classification of problems. 12.NP-complete problems. Satisfiability of logical circuit. Proof of NP-completeness. 13. Examples of practical application of algorithms.
|
|
Learning activities and teaching methods
|
Lecture supplemented with a discussion, Lecture with visual aids, Practicum
- Preparation for formative assessments (2-20)
- 8 hours per semester
- Individual project (40)
- 40 hours per semester
- Contact hours
- 65 hours per semester
- Preparation for an examination (30-60)
- 30 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| to understand basic imperative control flow in Java |
| to describe programming principles in imperative programming language, with focus on control flow |
| to describe basic means of data representation in a computer |
| to demonstrate knowledge of basic math terminology and methods |
| to understand primitive data types used in Java |
| Skills |
|---|
| to use some common integrated development environment for Java on user level |
| to perform basic mathematical derivations and calculations |
| to construct simple programs in Java |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| určit výpočetní složitost operací nad konkrétními implementacemi abstraktních datových struktur, zejména u standardních implementací v knihovně jazyka Java |
| popsat způsob vykonání programu v jazyce Java, zejména z hlediska alokace paměti v zásobníku a na hromadě a vytváření zásobníkových rámců |
| vyjmenovat a popsat nejrozšířenější abstraktní datové typy, možnosti jejich implementace a z toho plynoucí vlastnosti |
| interpretovat výroky o složitosti algoritmů a složitostních třídách O, Theta a Omega |
| interpretovat výroky o složitosti problémů, porozumět výrokům o třídách složitosti P, NP a NP-C |
| vyjmenovat a popsat nejpoužívanější algoritmy řazení a analyzovat jejich vlastnosti |
| Skills |
|---|
| implementovat základní algoritmy zpracování stromových datových struktur, tj. preorder, inorder a postorder procházení |
| implementovat základní algoritmy zpracování grafů, tj. prohledávání do šířky a do hloubky a topologické řazení |
| analyzovat a provnávat algoritmy z hlediska třídy výpočetní a paměťové složitosti |
| vytvářet složitější datové struktury podle konkrétních zadání, zejména s ohledem na volbu vhodné a efektivní abstraktní datové struktury a její implementace |
| implementovat programy využívající základní principy objektového programování v jazyce Java |
| implementovat složitější algoritmy zpracovávající dynamické datové struktury |
| Competences |
|---|
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Individual study |
| Lecture with visual aids |
| Lecture supplemented with a discussion |
| Practicum |
| E-learning |
| assessment methods |
|---|
| Continuous assessment |
| Written exam |
| Test |
| Seminar work |
|
Recommended literature
|
-
Cormen, Thomas H. Introduction to algorithms. Cambridge : MIT Press, 2001. ISBN 0-262-03293-7.
-
Lafore, Robert. Data structures & algorithms in Java. Corte Madera : Waite Group Press, 1998. ISBN 1-57169-095-6.
-
Sedgewick, Robert. Algorithms in Java. Pts. 1-4, Fundamentals, data structures, sorting, searching. 3rd ed. Boston : Addison-Wesley, 2003. ISBN 0-201-36120-5.
-
Šafařík, Jiří. Počítače a programování 2. ZČU, 2005.
|