Discrete Mathematics

1. Combinatorics and Graph Theory:
Combinatorial analysis, enumerations, permutations, variations, combinations, recursions, generating functions, Fibonacci sequence, Stirling numbers of the first and second kind, number-theoretic partitions, Catalan numbers. Graph theory, graph algorithms, basic concepts in graph theory, applications of breadth-first and depth-first search, shortest paths, matchings, flows, colorings, Eulerian and Hamiltonian theorems, planarity, extremal graph theory, Ramsey-type theorems.
Literature:
• Katona Gy. Y. - Recski A. - Szabó Cs.: A számítástudomány alapjai, Typotex, 2002. Chapters 1 and 7.
• N. J. Vilenkin: Kombinatorika, Műszaki Könyvkiadó, 1971.
• Hajnal Péter: Összeszámlálási problémák, Polygon, Szeged, 1997.
• (*) Lovász L.: Combinatorial Problems and Exercises, North-Holland and Akadémiai Kiadó, 1979 and 1993; Hungarian translation: Kombinatorikai problémák és feladatok, Typotex, 1999.
• J. A. Bondy - U. S. R. Murty: Graph Theory with Applications, Macmillan Press, 1976.
• Katona Gy. Y. - Recski A. - Szabó Cs.: A számítástudomány alapjai, Typotex, 2002. Chapters 2 and 3.
• Diestel: Graph Theory, Springer, 1997 and 2000.
• Rónyai L. - Ivanyos G. - Szabó R.: Algoritmusok, Typotex, 1999. Chapter 6.
• Péter Hajnal: Gráfelmélet, Polygon, Szeged, 1997.
• (*) Lovász L.: Combinatorial Problems and Exercises, North-Holland and Akadémiai Kiadó, 1979 and 1993; magyar fordítás: Kombinatorikai problémák és feladatok, Typotex, 1999.

2. Matroid Theory:
Basic concepts, equivalent characterizations, algebraic and geometric representations, graphic, cographic, regular, and binary matroids, matroid partition, intersection, and matching problems.
Literature:
• D. J. A. Welsh: Matroid Theory, Academic Press, 1976. (At least chapters 1, 2, 4, 6, 9, 10, and 19.)
• A. Recski: Matroid Theory and its Applications, Springer, 1989. (At least chapters 7, 9, 11, and 13.)
• (*) J. Oxley: Matroid Theory, Oxford University Press, 1992.

3. Data Structures:
Data structures, search and sorting algorithms, graph algorithms, lists, arrays, search trees, AVL trees, 2-3 trees, B-trees, heaps, hashing, binary search, comparison-based sorting, key manipulation sorting, shortest paths, breadth-first and depth-first traversal, minimum spanning trees, searching of maximum matching, searching of maximum flow.
Literature:
• A.V. Aho - J. E. Hopcroft - J. D. Ullman: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. Chapters 2, 3, and 4.
• M. R. Garey - D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
• Rónyai L. - Ivanyos G. - Szabó R.: Algoritmusok, Typotex, 1999. (Chapters 1, 2, 3, 4, and 6.)
• T. H. Cormen - C. E. Leiserson - R. L. Rivest: Algoritmusok, Műszaki Könyvkiadó, 1997. (Parts II - V.)
• (*) D. E. Knuth: The Art of Computer Programming Vol. 3. (Sorting and Searching), Addison-Wesley, 1973; Hungarian translation: A számítógép-programozás művészete 3. Keresés és rendezés, Műszaki Könyvkiadó, 1988.

4. Computational Models:
Computational models, formal languages, computational complexity, finite automata, determinization, minimization, regular expressions, pushdown automata, Turing machines, RAM machines, Chomsky hierarchy, connections between different automata, recursive and recursively enumerable languages, algorithmically undecidable problems, time and space complexity, P, PSPACE, NP, NP-complete languages, randomized Turing machines, randomized algorithms, RP language class, Kolmogorov complexity, approximation methods.
Literature:
• V. Aho - J. E. Hopcroft - J. D. Ullman: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. (Chapters 1, 5, 10, and 11.)
• J. E. Hopcroft - J. D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
• M. R. Garey - D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
• Rónyai L. - Ivanyos G. - Szabó R.: Algoritmusok, Typotex, 1999. (Chapters 1, 6, 7, 8, and 9.)
• Bach I.: Formális nyelvek, Typotex, 2001.
• Lovász L.: Algoritmusok bonyolultsága, ELTE Kiadó.
• C. H. Papadimitriou: Computational Complexity, Addison-Wesley, 1994; Hungarian translation: Számítási bonyolultság, Novadat, 1999.

5. Linear programming:
The question of solvability of linear systems of equations and its solution. Gauss-Jordan elimination method. Solvability of linear inequality systems. Alternative theorems, Farkas' lemma and its variants. Solving linear inequality systems with pivot algorithms. Convex polyhedra. Minkowski theorem, Farkas' theorem, Weyl theorem, Motzkin's decomposition theorem. Linear programming problem, examples of linear programming problems, graphic illustration. The concept of admissible solution and basis solution of a linear programming problem, the basic algorithm of the simplex method. Cyclization and its exclusion possibilities: lexicographic simplex method, application of Bland's rule. Finding an initial admissible basis, the two-phase simplex method. The explicit basis inverse and the modified simplex method. The duality theory of linear programming. The theorems of complementary differences. The dual simplex method. Special linear programming problems and problems that can be reduced to them. Unique upper bound technique. Sensitivity analysis. The Dantzigâ€“Wolfe decomposition procedure. Theory of linear programming based on interior point methods. Self-dual problem, level sets, existence and uniqueness of central path. Calculation of Newton directions. Analytic center, Sonnevend's theorem. Deakin ellipsoid, affine scaling interior point method and its polynomiality. Goldmannâ€“Tucker model, Goldmannâ€“Tucker theorem. Obtaining an exact solution by a strongly polynomial rounding procedure. Hachian's ellipsoid method. Karmarkar's potential function interior point algorithm. Special interior point algorithms.
Suggested books:
• A. Schrijver, Theory of Linear and Integer Programming, John Wiley, New York, 1986.

6. Stochastic Programming:
Decision under uncertainty, Bernoulli decision. Probability bounds of union of events. Markov decision process. Bellmann equations; Value and policy iteration algorithms. Theory of the logconcave measures. Theory and numerical solution techniques of programming problems under individual or joint probabilistic constraints. Models with random objective function. Dynamic stochastic programming models. Two-stage stochastic programming problems and their mathematical properties. Solution of the two-stage stochastic programming problems by basis decomposition technique when the random vector of the problem has discrete distribution; Multi-stage stochastic programming problems; Stochastic gradient methods; Gauss process, Bayes optimization. Selected applications of the stochastic programming. News vendor decision problem, optimal control of a storage level; Queuing problems; Electric power generation capacity expansion under uncertainty. System reliability computation. Example for optimal control of reservoirs. PERT optimization problem. Optimization problems in finance.
Suggested books:
• Kall, Peter, Stein W. Wallace, and Peter Kall. Stochastic programming. Vol. 5. Chichester: Wiley, 1994.
• Kail, Peter, and Janos Mayer. "Stochastic linear programming, models, theory, and computation." (2005).
• Birge, John R., and Francois Louveaux. Introduction to stochastic programming. Springer Science Business Media, 2011.

7. Combinatorial Optimization:
Network flows, Ford-Fulkerson algorithm. Characterization of even graphs, maximum size matching in even graphs. KĹ‘nig, Frobenius and Hall theorems. Graph colorings. Lower and upper bounds on the chromatic number. EgervĂˇry's algorithm. Fourier-Motzkin elimination. Approximation algorithms. Scheduling problems.
Suggested books:
• B. Korte, J. Vygen, Combinatorial optimization, Springer, 2018.