Algorithms and Data Structures 2
Goldengorin, Boris I.
Мельников Евгений Юрьевич
- Students will learn basic concepts of computational complexities for problems and algorithms (both exact and heuristic), which are necessary for further learning computational methods, algorithms for big data, algorithms and computational complexity, machine learning, operations research, game theory, and combinatorial optimization.
- Students will acquire skills in using algorithms and data structures 2 models and methods to formalize and solve applied problems.
- Students will learn basic notions of algorithms and data structures to solve intractable problems in computer science.
- Students will be able to find mathematical structures defined on graphs and Booleans (Hasse diagrams).
- Students will acquire basic skills to recognize and prove the time and space complexities for exact and heuristic algorithms.
- The Minimum Spanning Tree (Kruskal and Prim’s Algorithms) 1-Tree, and Linear Assignment Problems (Hungarian Algorithm).
- The Traveling Salesman Problem (TSP): Symmetric and Asymmetric Cases of TSP.
- The Branch and Bound Algorithms for the Symmetric TSP (STSP).
- The Branch and Bound Algorithms for the Asymmetric TSP (ATSP).
- Upper, Lower, and Bottleneck Tolerances in Combinatorial Optimization.
- Upper Tolerances Based Algorithm for the ATSP.
- Lower Tolerances Based Algorithm for the ATSP.
- Data Correcting Approach for Real-Valued Functions.
- Data Correcting Approach for ATSP.
- Heuristics for solving the TSP: greedy (nearest neighbor), tolerance based greedy, nearest insertion, 2, 3-opt.
- Introduction to Submodular Functions: Local, Global Maxima on Hasse Diagram and Their Components.
- Supermodular Functions Applied to the Simple Plant (Uncapacitated Facility) Location Problem (SPLP).
- Cherenin-Khachaturov’s Theorem. Excluding vs Preservation Rules. Dichotomy (Preliminary Preservation) Algorithm.
- Branch-and-Bound (BnB) Algorihm for Supermodular Function Minimization Problem and Its Applications to the SPLP.
- Non-binary branching rules applied to the pseudo-Boolean formulation of the SPLP. The branching rule: Make Quadratic Terms Linear.
- The Quadratic Cost Partition Problem (QCP) - an example for maximization of a submodular set function.
- Six equivalent definitions of submodular set functions.
- Cherenin’s Theorem (quasi-concavity of submodular functions).
- The greedy algorithm for submodular set functions.
- Boolean and pseudo-Boolean polynomials.
- Truncation Theorem for the p-Median problem in pseudo-Boolean formulation.
- Overview of BnB type Algorithms: Branch and Cut, Cutting Planes, Branch and Cut and Price, Data Correcting Algorithms, Tolerance Based Branch and Bound, Climer and Zhang's cut-and-solve algorithms.
- The theory of NP-Completeness; Relationship between P and NP classes; Polynomial transformations from a language (problem) to another language (problem).
- Cook, Karp, and Levin’s Theorem (sketch of the proof). Algorithm for proving NP-Completeness.
- Six basic NP-Complete problems: 3-Satisfiability, 3 Dimensional Matching, Vertex Cover, Clique, Hamiltonian cycle (circuit).
- Overview of the Algorithms and Data Structures 2 course.
- Homework assignments
- Midterm TestMidterm tеst will be announced at least one week in advance.
- Student’s Presentationat most 10 min = 8min + 2 min for questions. The presentations will be based on team (individual) reports.
- Interim assessment (1 module)0.4 * Exam + 0.2 * Homework assignments + 0.3 * Midterm Test + 0.1 * Student’s Presentation
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.
- Fisher, M. L., Nemhauser, Â. G. L., & Wolsey, L. A. (1978). An analysis of approximations for maximizing submodular set functions - 1. CORE Discussion Papers RP. https://doi.org/10.1007/BF01588971
- Goldengorin, B., & Pardalos, P. M. (2012). Data Correcting Approaches in Combinatorial Optimization. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=538347
- N. Chiba, & T. Yamanouchi. (n.d.).  M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.C8155A74
- Robert Sedgewick, & Kevin Wayne. (2014). Algorithms : Part I. [N.p.]: Addison-Wesley Professional. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1600534
- Sharlee Climer, & Weixiong Zhang. (2006). Cut-and-solve: An iterative search strategy for combinatorial optimization problems. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.FEA12BAE