Discrete Mathematics and Optimization
Complex exam questions
Responsible: György Dósa and Zsolt Tuza
Exam material: freely chosen 6 topics from the lfollowing list, which the candidate agrees with the examiner in advance.
Literature: selected by the examiner based on the topics chosen by the student
1. Computational complexity of algorithmic problems: Problem types (decision, etc.), deterministic and non-deterministic Turing machine, Church-Turing hypothesis. P, NP, co-NP, PTAS, APX classes, undecidability. NP- and APX-completeness, complexity of basic problems, reduction principles.
2. Data structures, sorting and search algorithms: Elementary data structures, comparison-based sorting, information theory lower bound, heap, merging, search trees. Sorting in linear time, median search and sorting statistics. Hash table, quick sort, random binary search tree, (2,3)-trees.
3. Traversals of graphs and trees, applications: Euler line, Hamilton circle, breadth first and depth first search, connected and strongly connected components, pre-, in-, postorder traversal, traveling salesman problem, Chinese postman problem.
4. Graph and network optimization algorithms: Shortest paths, minimum weight spanning trees. Maximal matchings, "Hungarian method", network flows, Menger path-systems. Linear-time algorithms on graphs with limited tree-width, connection with monadic second-order logic.
5. Graph colorings: General estimates for chromatic number and chromatic index, relationship with controllability. Colorability of planar graphs. Approximability and online coloring. Perfect graphs, their special classes (complement-reducible graphs, perfect classes derived from chordal or bipartite graphs), characterization, algorithms. Perfect graph theorem.
6. Approximation algorithms: Classic algorithms of bin packing, such as Next Fit, First Fit, First Fit Decreasing, Best Fit, Any Fit, Worst Fit. Their asymptotic and absolute approximation ratios. The weight function technique (the classical weight function of FF and its Sgall decomposition, the amortization lemma).
7. Classical results of scheduling theory: Scheduling of parallel machines, makespan minimization. Graham's List Scheduling (LS) algorithm and its ordered version, the Longest Processing Time (LPT) algorithm. Upper bounds on the approximation ratios and inputs that prove tightness. The Multifit algorithm. Approximation scheme for Pm | | Cmax. Online Scheduling: algorithsm for the Pm | | Cmax problem (LS and algorithms with better approximation bounds).
8. The general form of LP problems, the primal simplex method, optimality conditions, multi-objective optimization, goal programming.
9. Duality in linear programming. Weak and strong duality theorems. The relationship between dual feasibility and primal optimality, the dual simplex algorithm.
10. Methods of solving multivariable unconstrained problems. Steepest descent methods, Newton's method, conjugacy, method of conjugate directions.
11. Conditional optimization problems. General form, equality and inequality conditions, first-order necessary optimality conditions, second-order optimality conditions, Lagrange function, Kuhn-Tucker theorem.
12. Integer programming, formalization of the problem, relaxed problem, integer programming, solution methods, most important models, branch and bound-based algorithms.
13. Application of heuristics to solve integer problems (estimations, genetic algorithms, tabu search, simulated annealing). Traveling salesman problem. Heuristics for solving the traveling salesman problem. Set cover: mathematical models and heuristics.
14. Interval arithmetic, interval division methods, acceleration tools, interval Newton procedure, speed of convergence.