Lecturer: Zdeněk Hanzálek
Lab teachers: Ondřej Benedikt, Antonín Novák, Theodor Krocan and Marek Vlk
Due to the current situation and the closure of the faculty, the teaching/learning is ongoing in a distance form.
This course is focusing on the problems and algorithms of combinatorial optimization (often called discrete optimization). Following the courses on linear algebra, graph theory, and basics of optimization, we show optimization techniques based on graphs, integer linear programming, heuristics, approximation algorithms and state space search methods. We focus on application of optimization, e.g. logistics, transportation, planning of human resources, scheduling in production lines, message routing and scheduling in parallel computers.
Optimization, Discrete Mathematics, Logics and Graph Theory.
This timetable is for the czech version (B4M35KO) of the course. The timetable of the english version (BE4M35KO) is provided by prof. Hanzálek.
Week No. | Dates | Title | Notes | Handouts | Stream |
---|---|---|---|---|---|
1 | 17.2.-23.2. | Introduction of Basic Terms, Example Applications | Test 0 | https://rtime.felk.cvut.cz/~hanzalek/KO/Basic_e.pdf | |
2 | 24.2.-1.3. | Integer Linear Programming - Algorithms | https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf | ||
3 | 2.3.-8.3. | Integer Linear Programming - Problem Formulations | https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf | ||
4 | 9.3.-15.3. | Shortest Paths | https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf | ||
5 | 16.3.-22.3. | Problem Formulation by Shortest Paths | https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf | ||
6 | 23.3.-29.3. | Flows and Cuts - Algorithms and Problem Formulation | https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf | ||
7 | 30.3.-5.4. | Bipartite Matching. Multi-commodity Network Flows | https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf | ||
8 | 6.4.-12.4. | Knapsack Problem, Pseudo-polynomial and Approximation Algorithms | https://rtime.felk.cvut.cz/~hanzalek/KO/knapsack_e.pdf | ||
9 | 13.4.-19.4. | Traveling Salesman Problem and Approximation Algorithms | https://rtime.felk.cvut.cz/~hanzalek/KO/TSP_e.pdf | ||
10 | 20.4.-26.4. | Mono-processor Scheduling | https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf | ||
11 | 27.4.-3.5. | Scheduling on Parallel Processors | | https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf | |
12 | 4.5.-10.5. | Class is cancelled | |||
13 | 11.5.-17.5. | Project Scheduling with Time Windows | https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf | ||
14 | 18.5.-24.5. | Constraint Programming | Theory Test | https://rtime.felk.cvut.cz/~hanzalek/KO/cp_e.pdf | YT stream |
Students may receive a total of 100 points. The final exam is worth 50% of the grade, while the other 50% can be obtained during the semester.
The points are distributed according to the following table.
Category | Maximum points | ||
Semester | Homeworks (5 assignments, 3 points per each) | 15 | |
Theoretical test (written online) | 16 | ||
Practical test (written online) | 8 | ||
Semester project | 11 | Minimum points | |
Total semester ^{1)} | 50 | 30 | |
Final exam ^{2)} | Written part | 50 | 20 |
Total exam | 50 | 20 | |
Total | 100 | 50 |
^{1)} To get an ungraded assessment the following requirements have to be met:
The last date of awarding the ungraded assessments is 12. 6. 2020. If you will fail to obtain at least the required minimum of points for the assessment by then, you will fail also the entire class.
^{2)} Only the students, who obtained the ungraded assessment are allowed to take the exam. The exam constitutes of the written part (50 points). To pass the written exam, it is necessary to get at least 20 points.
Final grading scale:
Points | [0,50) | [50,60) | [60,70) | [70,80) | [80,90) | [90,100] |
---|---|---|---|---|---|---|
Grade | F | E | D | C | B | A |
The following applies only to students who got an ungraded assessment in the previous year (all other students have to undergo the course from scratch).
Although the assessments are not fully recognized, the students may opt-in to transfer some points from the previous year to the current one (they may also undergo the course from scratch to get a higher number of points). The following rules apply