Course for international guest/part time students
- Faculty
- Faculty of Science
- Organization
- TTK Department of Computer Science
- Code
- algelm1u0um17gm
- Title
- Algorithms (p)
- Usual semester
- Autumn
- ECTS
- 3
- Language
- hu
- Learning outcomes
- Knowledge: Knowledge of basic concepts, results and methods in the field. Ability: Application of knowledge in the field, understanding of interrelationships and problem solving. Attitude: Desire to improve mathematical knowledge and to learn as much as possible, and to apply knowledge as widely as possible. Autonomy and Responsibility: Formulate and analyse mathematical questions independently and evaluate the limits of their applicability responsibly.
- Course content
- Sorting and selection. Computing with large numbers, Euclidean algorithm, RSA. Fast Fourier transform and its applications. Applications of dynamic programming. Graph algorithms: implementation and applications of breadth-first and depth-first search (shortest paths, bicolorability, strongly connected orientations, two-connected blocks, finding strongly connected components). Applications of Dijkstra's algorithm (widest path, safest path, PERT method, selection of the cheapest among the shortest paths). Bellman-Ford algorithm, Johnson's algorithm, Karp's minimum mean circle algorithm, Suurballe and Tarjan's algorithm. Stable matching. Hopcroft-Karp algorithm, Dinic algorithm, disjoint paths. Network codes. Concept of approximation algorithm, examples (Ibarra-Kim, metric TSP, Steiner tree, vertex cover). Fixed parameter tractability. Parallel algorithms (Brent's theorems, minimum, addition, multiplication, sorting, applications of matrix multiplication).
- Assessment method
- term grade