Labs

The goal of the labs is to exercise the topics presented on lectures.

On some labs you will receive homework assignment, which are implementation of an algorithm or a method solving some interesting combinatorial optimisation problem. In all cases, the solutions to homework assignments are submitted to UploadSystem where they are automatically checked and evaluated. There are no strict deadlines, however, you will be penalised by -1 points for each week after deadline. Completing all homeworks successfully is a mandatory requirement for the assessment. Moreover, we encourage you to solve the homeworks since in the practical test you will use algorithms implemented for the homeworks.

Plan of the Labs

Week No.	Title	Notes	Handouts	Other materials
1	Introduction, Gurobi installation	-	01_gurobi.pdf	01_grading_and_rules.pdf gurobi_examples.zip
2	Semester Project, LP and ILP basics	-	Cocontest assignment	Linear Programming, Duality (in Czech) Convex optimisation, Linear Programming, Duality (in English) Example source codes
3	ILP 1	HW1, deadline for choosing semester project	03_ilp.pdf	Notes and issues with big-M, Program skeletons HW1 Public instances Example source codes
4	ILP 2 - Unexpected applications	-	04_ilp.pdf	Game of Fivers, Optimal adversarial examples to fool a DNN via ILP, Solving Rubik's cube, lab_codes_04.zip
5	Shortest Paths	Consultation	05_stp.pdf	Content-aware image resizing via STP, czech_republic.txt, Czech republic approximation (skeleton)
6	Network Flows	HW2	06_flows.pdf	Examples to practice, hw2_public_instances.zip, Pseudopolynomial time complexity
7	Minimum Cost Flows	HW3	07_mcf.pdf	hw3_public_instances.zip
8	Dynamic Programming	CoContest consultation	08_dynamic.pdf	-
9	Practical Test	-	-	-
10	Traveling Salesman Problem	HW4	10_tsp.pdf	hw4_public_instances.zip, circle_approximation.py
11	consultation	-
12 Tuesday	Bratley's problem	HW5	12_bratley.pdf	hw5_public_instances.zip, Scheduling ZOO
12 Thursday	class is canceled, Wednesday schedule	-
13 Tuesday	class is canceled, Wednesday schedule	-	-
13 Thursday	Bratley's problem	HW5	12_bratley.pdf	hw5_public_instances.zip, Scheduling ZOO
14	Presentation of the semester project solutions	Attendance is mandatory.	Cocontest presentation	-

Classroom computers

OS: Debian Linux 64b, select “DCE PXE” (without number) during booting

Login: username + main CTU password (the one you use for KOS)

Development environments: CLion (C++), IntelliJ (Java), PyCharm (Python), Visual Studio Code, GVim, Eclipse, Geany are installed. CLion, IntelliJ and PyCharm are installed in /opt and their license have to be activated via creating JetBrains account with faculty email. For interactive Python, you can use IPython.

Table of Contents

Labs

Plan of the Labs

Classroom computers