====== 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 [[https://cw.felk.cvut.cz/brute/|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 | - | {{ :courses:ko:01_gurobi.pdf |}} | {{:courses:ko:01_grading_and_rules.pdf|}}  {{:courses:ko:gurobi_examples.zip|}} |
| 2 | Semester Project, LP and ILP basics | - | {{ :courses:ko:semester_project_cocontest_2019.pdf |Cocontest assignment}} | [[https://cw.fel.cvut.cz/old/_media/courses/a4b33opt/opt.pdf|Linear Programming, Duality (in Czech)]] \\ [[http://stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|Convex optimisation, Linear Programming, Duality (in English)]] \\ {{ :courses:ko:lab02_codes.zip |Example source codes}}|
| 3 | ILP 1 | HW1, deadline for choosing semester project | {{ :courses:ko:03_ilp.pdf |}}  |[[https://orinanobworld.blogspot.com/2011/07/perils-of-big-m.html|Notes and issues with big-M]], \\ {{ :courses:ko:lab03_skeletons.zip |Program skeletons}} \\ {{ :courses:ko:hw1_public_instances.zip |HW1 Public instances}} \\ {{ :courses:ko:lab03_codes.zip | Example source codes}} |
| 4 | ILP 2 - Unexpected applications | - | {{ :courses:ko:04_ilp.pdf |}}| [[http://rtime.felk.cvut.cz/~novakan9/ko/fivers.html|Game of Fivers]], \\ [[https://link.springer.com/article/10.1007/s10601-018-9285-6|Optimal adversarial examples to fool a DNN via ILP]], \\ [[http://www.m-hikari.com/imf-password2009/45-48-2009/aksopIMF45-48-2009-2.pdf|Solving Rubik's cube]], \\ {{ :courses:ko:lab_codes_04.zip |}}   |
| 5 | Shortest Paths | Consultation | {{ :courses:ko:05_stp.pdf |}} | [[https://dl.acm.org/citation.cfm?id=1276390|Content-aware image resizing via STP]], \\ {{ :courses:ko:czech_republic.txt |}}, \\ {{ :courses:ko:image_approximation_skeleton.zip | Czech republic approximation (skeleton)}} |
| 6 | Network Flows | HW2 | {{ :courses:ko:06_flows.pdf |}} | [[http://jeffe.cs.illinois.edu/teaching/algorithms/book/11-maxflowapps.pdf|Examples to practice]], \\ {{ :courses:ko:hw2_public_instances.zip |}}, \\  [[https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time| Pseudopolynomial time complexity]] |
| 7 | Minimum Cost Flows | HW3 | {{ :courses:ko:07_mcf.pdf |}} |{{ :courses:ko:hw3_public_instances.zip |}} |
| 8 | Dynamic Programming | CoContest consultation | {{ :courses:ko:08_dynamic.pdf |}}| - |
| 9 | Practical Test | - |- | - |
| 10 | Traveling Salesman Problem | HW4 | {{ :courses:ko:10_tsp.pdf |}}| {{ :courses:ko:hw4_public_instances.zip |}}, {{ :courses:ko:circle_approximation.py |}} |
| 11 | consultation | - | | |
| 12 Tuesday | Bratley's problem | HW5 | {{ :courses:ko:12_bratley.pdf |}}| {{ :courses:ko:hw5_public_instances.zip |}}, [[http://schedulingzoo.lip6.fr/|Scheduling ZOO]]|
| 12 Thursday | class is canceled, Wednesday schedule |- | | |
| 13 Tuesday | class is canceled, Wednesday schedule | - | - | |
| 13 Thursday | Bratley's problem | HW5 | {{ :courses:ko:12_bratley.pdf |}}| {{ :courses:ko:hw5_public_instances.zip |}}, [[http://schedulingzoo.lip6.fr/|Scheduling ZOO]]|
| 14 | Presentation of the semester project solutions | Attendance is **mandatory**. | {{ :courses:ko:ko_presentation_cocontest_1_.pdf |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.