Combinatorial Optimization 2017
Combinatorial Optimization 2017
Back to the main page
The official homepage of the lecture:
Course
The lectures are on every Monday 08:30-10:00 (except 17th of April and 1st of May, because they are national holidays), and on every second thursdays 08:30-10 (16th of February; 2nd, 16th and 30th of March; 13th and 27th of April; 11th of May )
The exams:
Results of the exams.
You can see the grades what you have earned alredy. For those where the grade is yellow,
I offer an opportunity to get a better grade by answering me 1 theoretical question during the retake (if You choose this option please write me an email).
I will ask one question from the theory of that exam where you have acquired less points. (If the two results are the same, then you can decide).
Examples of the first exam
Solutions of the first exam
Examples of the retake of the first exam
03.16. 8:00
04.20. 8:00 (retake of first)
05.08. 8:00 (Modified from 05.08 17:00)
05.11. 8:00 (retake of second) (Modified from 05.17 10:00)
05.17 10:00 (reretake: you have to register on Neptun) (this was the date of the second retake)
The grades will be calculated from the overall percentage of the written exams. (0-47: 1; 48-65: 2; 66-83: 3; 84-101: 4; 102-120: 5).
There are two midterm tests during the semester. The condition of completing the subject is a result of at least 40% on all midterm
tests.
If you have any questions or comments please write me an email (cscsgy at gmail dot com).
Topic of the first exam:
Tasks:
1. Prove that a given problem is in NP
2. Give a polynomial reduction between two given problems
3,4,5. Use one of the algorithms: BFS, Kruskal, Ford-Fulkerson, Alternating path method
6. Theoretical question
Main topics what we have learnt about:
Algorithms,
Polynomials,
Graph theory,
Combinatorial optimization,
Running time,
Polynomial reduction,
Bipartite graphs,
Spanning trees,
Greedy algorithm,
Kruskal's algorithm,
BFS,
Flows,
Ford–Fulkerson algorithm,
Assignment problem,
Hungarian algorithm,
Dijstra's algorithm,
Floyd-Warshall algorithm,
Dynamic programming,
DP solution for Knapsack problem,
Classes of decision problems:
P,
NP,
NP-complete,
Problems what we have learnt:
Prime,
Composite,
Partition,
Subset sum,
Knapsack problem,
Graph theoretical problems:
Connectivity,
Perfect matching,
Path existence,
Shortest path,
k-Clique,
k-Coloring,
Hamiltonian cycle,
Widest path,
Minimum spanning tree,
Maximum flow,
Useful examples:
Dijkstra: video, picture
Knapsack: video, slides
Floyd: video
Homeworks to practice: (If you send me a solution in email [or give it to me in a paper on a lecture],
then I correct the mistakes and send back how many points would that solution worth in the exam)
1. Prove that the Hamiltonian path problem
(Input: G graph, Output: True if there exists a Hamiltonian path in the graph) is in NP.
2. Prove that the maximum weight matching problem
(Input: G graph, a weight function w(e) on the edges, and number k, Output: True if there exists a matching with weight at least k) is in NP.
3. Prove that the k-Coloring problem
(Input: G graph and number k, Output: True if there exists a good coloring with at most k colors) is in NP.
4. Give a polynomial reduction from the Hamiltonian cycle problem to the
longest cycle problem (Input: G graph and number k, Output: True if there exists a cycle with at least k edges).
5. Give a polynomial reduction from the Hamiltonian path problem to the
longest path problem (Input: G graph and number k, Output: True if there exists a path with at least k edges).
6. Give a polynomial reduction from the 3-Coloring problem to the k-Coloring problem.
7. Run the BFS algorithm in the given graphs:
from 0, and from 6: G_1
from 10, and from 6: G_2
from M, and from I: G_3
8. Run the Kruskal algorithm in the given graphs:,
G_1,
G_2,
G_3
9. Run the Ford-Fulkerson algorithm in the given graphs:
from a to f: G_1
from s to t: G_2
from 1 to 8: G_3
from s to t: G_4
New homeworks:
10. Solve the following knapsack problems using dynamic programming (Limit: weight-value pairs):
a) 10: 1-1,2-8,3-10,4-10,5-19,6-25 Solution
b) 6: 3-25,2-20,1-15,4-40,5-50 Solution
11. Run the Dijkstra method to find the shortest paths (from one node to all the others) in the following graphs:
a) From A and from G Solution
b) From k and from e Solution
12. Run the modified Dijkstra method to find the widest paths (from one node to all the others) in the following graphs:
a) From 3 and from 4 Solution
b) From 3 and from 7 Solution
13. Run the modified Dijkstra method to find the widest shortest paths (widest among the shortests from one node to all the others) in the following graphs:
a) From 4 (the first numbers are the distances, the seconds are the weights) Solution
b) From C and from G (here the numbers are the weights and the distances are equal to one in every edge) Solution
14. Run the Floyd method to find the shortest paths (between each two nodes) in the following graphs:
a) G1 Solution
b) G2 Solution
c) G3
Solution
15. Formalize the flow problem of these networks as linear programming problems.
a) network1 (from 1 to 3)
b) network2 (from + to -)
16. Formalize the knapsack problems of the 10th homework as integer programming problems.
17. Formalize the maximum weight matching problems on these graphs as integer programming problems.
a) graph1
b) graph2
18. Draw the set of solutions of these LP-s in coordinate systems.
a) LP1
b) LP2
19. Give the dual of these LP-s.
a) LP1
b) LP2
c) LP3
20. Decide if these matrices are totally unimodular (TU) or not (you should use the theorem for c) and d)).
a) M1
b) M2
c) M3
d) M4
21. Solve the knapsack problems of 10 with the branch and bound method
Collection of other useful materials:
Alexander Schrijver's lecture
MIT course (usable for us: 'Matching Algorithms','The Matching Polytope: Bipartite Graphs','Flow Duality and Algorithms','Minimum Cuts ','Linear Programs','NP-completeness','Approximation Algorithms')
Princeton lecture of Robert Sedgewick and Kevin Wayne (usable for us: 'Undirected Graphs','Directed Graphs','Minimum Spanning Trees','Shortest Paths','Linear Programming','Reductions')