Discrete Mathematics 2
Goldengorin, Boris I.
- Students will learn basic concepts, models and methods of discrete optimization, which are necessary for further learning computational methods, algorithms for big data, machine learning, algorithms and computational complexity, operations research, game theory, and combinatorial optimization.
- Students will acquire skills in using discrete math 2 models and methods to formalize and solve applied problems in data analysis.
- Students will be able to model, solve and make conclusions based on the problems and solution methods including exact and heuristic algorithms.
- Students will be able to find mathematical structures in the object they work with.
- Students will acquire basic math skills for learning advanced courses in applied data analysis and computer science.
- Students will learn basic math notions that are needed to work in broad areas of applied data analysis.
- The linear programming (LP) problem and its applications.
- The simplex method in graphical and tabular forms.
- Shadow prices and their interpretations.
- Sensitivity analysis in LP.
- The primal and dual problems in LP and their properties.
- The transportation problem, northwest and Vogel’s heuristics.
- The assignment problem (AP) and its applications.
- The Hungarian algorithm for solving the AP.
- The shortest path (SP) problem and its applications.
- The SP algorithm for finding an optimal solution.
- The minimum spanning tree (MST) problem, its variations and applications.
- The bottleneck MST.
- The Kruskal’s and Prim’s algorithms for finding a MST.
- The max-flow-min-cut problem (MFP) and its applications.
- The Ford-Fulkerson’s algorithm for solving the MFP.
- The traveling salesman problem (TSP) and its applications.
- Computation of upper and lower tolerances for the following problems: LP, SP, MST, AP, MFP, TSP.
- Applications of upper tolerances to the uniqueness (nonuniqueness) of optimal solution(s) for the LP, SP, MST, AP, MFP, TSP.
- The branch and bound algorithm for the Asymmetric TSP (ATSP) based on the AP.
- The branch and bound algorithm for the Symmetric TSP based on the 1-tree problem.
- The following heuristics for solving the TSP: greedy (nearest neighbor), tolerance based greedy, nearest insertion, 2, 3-opt.
- The integer LP (ILP) and its applications.
- The branch and bound algorithm for the ILP based on the LP.
- Pseudo-Boolean polynomials: theory and algorithms.
- Homework AssignmentsHomework problems will be assigned starting from second week just once a week. Each student is expected to solve the problems individually. Each homework will be represented by the mini-group printed report containing an abstract, introduction, individual solutions by every member of the mini-group, summary, and conclusion, and references. The sections of an assignment will be discussed by all members of the mini-group and reflecting the mini-group consensus.
- 2 in-class TestsThere will be two written tests. Tests will be announced at least one week in advance.
- Student’s PresentationEach presentation takes at most 10 min = 8min + 2 min for questions. Presentations will be based on team (individual) reports.
- Final Exam
- Interim assessment (2 module)0.2 * 2 in-class Tests + 0.4 * Final Exam + 0.3 * Homework Assignments + 0.1 * Student’s Presentation
- Boros, E., & Hammer, P. L. (2002). Pseudo-Boolean optimization. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.5E6D740E
- Rosen, K. H., Shier, D. R., & Goddard, W. (2017). Handbook of Discrete and Combinatorial Mathematics (Vol. Second edition). Boca Raton, FL: Chapman and Hall/CRC. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1617301
- Discrete mathematics, Biggs, N. L., 2004