| Description |
Efficient algorithms are sought for solving problems in discrete mathematics. Different algorithms and applications to various problems are studied through special reading assignments, lecture presentations, and group discussions. Branch and bound strategy. Dynamic programming principle. Optimal paths in graphs. Optimal spanning trees in graphs. 2-coloring and odd cycles in a graph. Depth-first search in a graph and its applications. Properties of depth-first search tree. Graph decomposition algorithms. Graph assembling algorithms. Graph planarity algorithms. Euler problems. Hamiltonian problems. Some packing and covering problems for graphs. Metric problems on graphs. Set transformation algorithms. Search trees of different types. Various sorting algorithms. The main ideas of the NP-theory (the theory of problem complexity). |