• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Версия для слабовидящихВерсия для слабовидящихЛичный кабинет сотрудника ВШЭПоиск
Расширенный поиск
Меню
Высшая школа экономики
Личный кабинет сотрудника ВШЭПоиск
Расширенный поиск

Course Syllabus

Бакалавриат 2019/2020

Алгоритмы и структуры данных 2

Статус: Курс обязательный (Программа двух дипломов НИУ ВШЭ и Лондонского университета "Прикладной анализ данных")
Направление: 01.03.02. Прикладная математика и информатика
Кто читает: Департамент больших данных и информационного поиска
Где читается: Факультет компьютерных наук
Когда читается: 2-й курс, 1 модуль
Формат изучения: с онлайн-курсом
Преподаватели: Гольденгорин Борис Исаакович, Мельников Евгений Юрьевич
Язык: английский
Кредиты: 4
Контактные часы: 56

Course Syllabus

Full Syllabus

Abstract

The objective of this course is to make students familiar with polynomially solvable (tractable) and intractable (NP-complete and NP-hard) problems including well known problems in combinatorial optimization and computer science (e.g. the traveling salesman problem and its polynomially solvable special cases; generalized p-median problem and its applications in data analysis; max-clique, basic models of integer linear programming models (discrete optimization models) and enumeration (branch-and-bound type) algorithms for solving general mixed-integer linear programming problems as well as its special cases (minimum spanning tree and its variations, linear assignment, and traveling salesman problem). The algorithmic line of this course will be represented by an introduction to the maximization of submodular set functions (discrete analog of convex functions), and their applications to data analysis problems. We conclude this course with an overview of time and space complexities for polynomially solvable and NP-hard problems. Pre-requisites: Discrete Mathematics 1, Algorithms and Data Structures 1.
Learning Objectives

Learning Objectives

  • 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.
Expected Learning Outcomes

Expected Learning Outcomes

  • 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.
Course Contents

Course Contents

  • 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.
Assessment Elements

Assessment Elements

  • non-blocking Homework assignments
  • non-blocking Midterm Test
    Midterm tеst will be announced at least one week in advance.
  • non-blocking Exam
  • non-blocking Student’s Presentation
    at most 10 min = 8min + 2 min for questions. The presentations will be based on team (individual) reports.
Interim Assessment

Interim Assessment

  • Interim assessment (1 module)
    0.4 * Exam + 0.2 * Homework assignments + 0.3 * Midterm Test + 0.1 * Student’s Presentation
Bibliography

Bibliography

Recommended Core Bibliography

  • 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.). [7] 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

Recommended Additional Bibliography

  • 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