Course objectives:
|
The aim is to give an overview of modern combinatorial algorithms and their applications in various fields of mathematics.
|
Requirements on student
|
Credit: selected paper presentation.
Exam: written and oral part.
|
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.
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
|
Literature
|
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Preparation for comprehensive test (10-40)
|
20
|
Preparation for an examination (30-60)
|
45
|
Contact hours
|
39
|
Total
|
104
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
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
|
Knowledge - knowledge resulting from the course: |
A student will be able to:
- solve algorithmically standard combinatorial problems,
- analyze the complexity of algorithms,
- apply suitable approximations algorithms.
|
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Oral exam |
Test |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Lecture |
Interactive lecture |
Practicum |
|