|
Lecturer(s)
|
-
Adámek Adam, Ing.
-
Klika Zdeněk, Ing. Ph.D.
|
|
Course content
|
1. Complexity of algorithms - revision and extension of knowledge. Abstract data types 2. Searching and sorting algorithm - medians, quantils, bucket sort, radix sort, comparison of sorting algorithms 3. Data structures I - stack, queue, list, dictionary, inverted list 4. Data structures II - balanced searching trees (AVL, Red-Black, B), hash tables, graphs, sets 5. Graph algorithms - shortest path (Dijkstra, Floyd-Warshall), minimum spanning tree (Prim-Jarnik, Kruskal), bipartite graphs 6. Sets algorithms - generating of permutations and subsets 7. Text algorithms - string agreement, aproximate agreement, shortest and longest common subsequence 8. Data compression I - lossless algorithms (RLE, LZW, Huffman, arithmetic coding) 9. Data compression II - lossy methods (JPEG, wavelet compression, fractal compression 10. Cryptography - introduction, basic algorithms. 11. Programmer practice - using suitable data structures,effect of cache on program running, effect of floating point implementation of real numbers on calculation
|
|
Learning activities and teaching methods
|
Seminar classes, Lecture
- Contact hours
- 65 hours per semester
- Undergraduate study programme term essay (20-40)
- 30 hours per semester
- Preparation for an examination (30-60)
- 40 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| algorithmize simple problems |
| programming in one of the basic programming languages (Java,C,Pascal) |
| Skills |
|---|
| analyze a simple task |
| create a simple program in a basic programming language |
| write and debug a simple program in the development environment for given language |
| create user and programmer documentation for that program |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| analyze the problem and choose appropriate data structures and algorithms |
| use and implement basic data structures used in informatics (stack, queue, search trees, dictionaries, hash tables, sets, graphs) |
| use and implement basic sorting and searching algorithms and graph algorithms (shortest path, minimum spanning tree, network flows) |
| use and implement text processing algorithms, combinatorial algorithms, and data compression algorithms |
| to enumerate and explain the basic cryptographic algorithms |
| Skills |
|---|
| analyze the problem and choose appropriate data structures and algorithms |
| create a program in one of the basic programming languages |
| create user and programmer documentation for the problem |
| evaluate the solution of the problem, eventually, suggest possible modifications of the solved problem that could not be realized |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecture |
| Practicum |
| Skills |
|---|
| Practicum |
| Individual study |
| Competences |
|---|
| Practicum |
| Individual study |
| assessment methods |
|---|
| Knowledge |
|---|
| Written exam |
| Seminar work |
| Skills |
|---|
| Written exam |
| Skills demonstration during practicum |
| Seminar work |
| Competences |
|---|
| Skills demonstration during practicum |
| Seminar work |
| Individual presentation at a seminar |
|
Recommended literature
|
-
Cormen, Thomas H. Introduction to algorithms. MIT Press, 2009. ISBN 978-0262033848.
-
Goodrich, Michael T.; Tamassia, Roberto. Data structures and algorithms in Java. John Wiley & Sons, 2005. ISBN 0-471-73884-0.
-
McConnell, Steve. Dokonalý kód : umění programování a techniky tvorby software. Vyd. 1. Brno : Computer Press, 2005. ISBN 80-251-0849-X.
-
Sedgewick, Robert. Algorithms in Java. Pts. 1-4, Fundamentals, data structures, sorting, searching. 3rd ed. Boston : Addison-Wesley, 2003. ISBN 0-201-36120-5.
-
Skiena, Steven S. The algorithm design manual. 2nd ed. New York : Springer, 2008. ISBN 978-1-848-00-069-.
-
Töpfer, Pavel. Algoritmy a programovací techniky. 1. vyd. Praha : Prometheus, 1995. ISBN 80-85849-83-6.
|