Discrete Optimisation
Faculty
Alex Dainiak
Associate Professor at Moscow Institute of Physics and Technology
Course length
Duration
Total hours
Credits
Language
Course type
Fee for single course
Fee for degree students
Skills you’ll learn
Overview
Combinatorics is the main theoretical background for computer science, in particular for data science. As combinatorics deals with finite structures it provides tools, concepts naturally fitting the programme’s goals. The module starts with elementary and advanced counting techniques that enable students to evaluate effectiveness of algorithms, resource requirements of data structures and manipulations.
Then graph theory is introduced. Graphs provide a perfect language to formulate problems arising in connection with computational questions. Finally advanced combinatorial structures and problems are treated that help students in dealing with abstractions of the field and in avoiding pitfalls of of not being exact and precise enough.
A good theoretical background for data sciences and applied computer sciences is like a good foundation for a building, without that, it collapses.
Learning highlights
- Formulate a discrete optimisation problem using precise notation.
- Estimate if the problem is computationally tractable in terms of precise solution. If not, then what general heuristics one may apply to solve the problem.
- Evaluate the quality of concrete heuristics using various measures.
Course outline
4 classes
Classical problems in discrete optimisation:
Problems on graphs and networks, cover problems, bin packing, knapsack, scheduling. Quality metrics for approximate algorithms.
Local search algorithms:
Pros and cons. Kernigan–Lin modification of local search (KL-heuristic).
Tree problems:
Recap of minimum spanning tree (MST) problem. Steiner tree problem; application of metric closure.
Heuristics directly based on local search:
Simulated annealing and tabu search.
Prerequisites
This course is one of three in a wholistic series.
Students that have already taken MSL-111 and those with prior experience with HTML, CSS, and Javascript building simple web pages will be good candidates for this module.
Alex was born in Moscow in 1985. His first encounter with programming happened in 1998 at a Pascal circle and that was love at first sight (or, better said, first line of code).
Alex teaches math and programming since graduating from the Moscow State University.
See full profileApply for this course
Discrete Optimisation
by Alex Dainiak
Total hours
45 Hours
Dates
Jan 28 - Feb 15, 2019
Fee for single course
€1500
Fee for degree students
€750
How to secure your spot
Complete the form below to kickstart your application
Schedule your Harbour.Space interview
If successful, get ready to join us on campus
FAQ
Will I receive a certificate after completion?
Yes. Upon completion of the course, you will receive a certificate signed by the director of the program your course belonged to.
Do I need a visa?
This depends on your case. Please check with the Spanish or Thai consulate in your country of residence about visa requirements. We will do our part to provide you with the necessary documents, such as the Certificate of Enrollment.
Can I get a discount?
Yes. The easiest way to enroll in a course at a discounted price is to register for multiple courses. Registering for multiple courses will reduce the cost per individual course. Please ask the Admissions Office for more information about the other kinds of discounts we offer and what you can do to receive one.