|
Lecturer(s)
|
-
Marek Josef, doc. Ing. Ph.D.
|
|
Course content
|
1. Permutations. Fast matrix multiplication. Permanents. 2. Groups and fields. Quadratic residues. Primality testing. 3. Graph algorithms. Generating graphs. 4. Graph isomorphism. Trees. Graph partitioning. 5. Graph connectivity. Cyclic connectivity. 6. Graph planarity. Matchings. Graph classes. 7. Matroids and matroid intersection. Submodular functions. 8. Independence. Graph colourings. Hamiltonian cycles. 9. Hypergraphs. Block designs. 10. Satisfiability. 11. Combinatorial geometry. 12. Probabilistic algorithms. On-line algorithms. 13. Parallel algorithms. Algorithm analysis.
|
|
Learning activities and teaching methods
|
Interactive lecture, Lecture, Practicum
- Preparation for comprehensive test (10-40)
- 20 hours per semester
- Contact hours
- 39 hours per semester
- Preparation for an examination (30-60)
- 45 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| An active knowledge of the content of the course KMA/DMA (or KMA/DMA-A) is assumed. The course KAM/TGD1 is recommended in parallel. |
| learning outcomes |
|---|
| A student will be able to: - solve algorithmically standard combinatorial problems, - analyze the complexity of algorithms, - apply suitable approximations algorithms. |
| teaching methods |
|---|
| Lecture |
| Interactive lecture |
| Practicum |
| assessment methods |
|---|
| Oral exam |
| Test |
|
Recommended literature
|
-
Schrijver, A. Combinatorial optimization. Berlin, 2003. ISBN 3-540-44389-4.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest and Clifford Stein:. Introduction to Algorithms, 3rd Edition.
-
Van Lint, J. H.; Wilson, R. M. A course in combinatorics. Cambridge : Harvard University Press, 2001. ISBN 0-521-00601-5.
|