Upon completing this course, the student has knowledge of and ability to apply important techniques and results from the field of algorithms, including linear programming, integer linear programming, approximation, NP-completeness, parallel algorithms, and online algorithms.
There is a project done in groups (40 percent) and two exams, both an approximately half of the materials (30 percent each). You must have at least a 4.5 for the project and for the average of the exams to pass the course, and at least a 5.5 for the overall average.
If the project was graded less than 4.5, and you have an average of at least 4 for the exams and the project, you can do a new project.
If the average of your exams was graded less than 4.5, and you have an average of at least 4 for the exam and the project, you can do the re-exam.
If your average was at least 4 and less than 5.5, you can do the re-exam.
Some details on grading for the 2nd chance exam or project can be found on the Blackboard site of the course.
In data science we distinguish:
This course and other courses in the field of algorithms focus on prescriptive analysis. The purpose of this course iis to teach topics that:
- Descriptive analysis: what is the current situation?
- Predictive analysis: what is going to happen in the future?
- Prescriptive analysis: which decision should I make?
- are important for the working area of algorithms (in practice and theory)
- are prerequisites for other courses in the COSC program
- that are not encountered by all students in the bachelor.
It therefore contains a broad range of topics.
In many real-life decision problems in e.g. (public) transportation, logistics, energy networks, healthcare, computer networks and education we want to select a very good solution from a large set of possible solutions.
In the course you learn how to model such problems and how to solve them by optimization algorithms. We focus on discrete models.
You shall learn about computational complexity and about meaning of exact optimization algorithms, heuristics and what-if analysis.
For deterministic problems, we study well-known algorithms from combinatorial optimization, including algorithms for linear programming, integer linear programming, online algorithms, shortest paths, approximation.
Lectures, self-study, exercises, assignments.
The material of the course consists of course notes and slides.
The following books are not mandatory but interesting for further reading:
- Laurence A. Wolsey, "Integer Programming", Wiley-Interscience publication, 1998, ISBN 0-471-28366-5.
- M.R. Garey and D.S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness", W.H. Freeman and Company, New York, 1979, ISBN 0-7167-1044-7.
- John Kleinberg, Eva Tardos "Algorithm Design", Pearson/Addision Wesley, 2005. ISBN 0-321-29535-8.