|
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 understand primitive data types used 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 |
| Skills |
|---|
| to perform basic mathematical derivations and calculations |
| to use some common integrated development environment for Java on user level |
| to construct simple programs in Java |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| to interpret statements on problem complexity, to understand statements on complexity classes P, NP and NP-C |
| to name and describe the most commonly used sorting algorithms and to analyze their properties |
| to interpret statements on algorithm complexity and complexity classes O, Theta and Omega |
| to name and describe the most commonly used data types, their possible implementations and their implied properties |
| to describe the means of performing a Java program, in particular regarding the memory allocation on the heap and construction of stack frames |
| to determine the complexity of operations on particular implementations of abstract data structures, in particular of the standard implementations in the Java class libraries |
| Skills |
|---|
| to implement basic tree data structure processing algorithms, i.e. preorder, inorder and postorder traversal |
| to implement advanced algorithms to process dynamic data structures |
| to construct advanced data structures according for particular problems, with focus on choosing a proper and efficient abstract data structure and its implementation |
| to implement programs in Java using basic principles of object oriented programming |
| to analyze and to compare algorithms in terms of their computational and memory complexity |
| to implement basic graph processing algorithms, i.e. breadth first search, depth first search and topological ordering |
| Competences |
|---|
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Individual study |
| Lecture with visual aids |
| Lecture supplemented with a discussion |
| Practicum |
| 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.
|