Algorithmic Combinatorics (Discrete Mathematics II)
Winter 2014/15.
|
Exercises.
Exercise Sheet 1-3. (9 solutions due October 29th)
Exercise Sheet 4. (due November 14th)
Exercise Sheet 5. (due November 21st)
Exercise Sheet 6. (due November 28th)
Exercise Sheet 7. (due December 5th)
(4/12/2014: fixed typos in Exercise 4)
Exercise Sheet 8. (due December 12th)
(4/12/2014: Made Exercise 1(ii) a bonus, added a hint for Exercise 2(ii), corrected a typo in Exercise 4)
Exercise Sheet 9. (due December 19th)
(12/12/2014: Some clarification added to Exercises 4(iii) and 5; 16/12/2014: fixed typo in Exercise 3(i))
Solution to Exercise 3.
Exercise Sheet 10. (due January 9th)
Mock Exam. (due 12 noon, January 16th)
Exercise Sheet 11. (due January 23rd) (17/1/2015: Exercise 1 corrected - subscripts fixed. Exercise 3 corrected - the objective function should be minimised. )
Exercise Sheet 12. (due January 30th) (29/1/2015: Correction made to the hint for Exercise 2.)
Exercise Sheet 13. (due February 6th) (5/2/2015: Exercise 6 - definition of the matrix A corrected)
Exercise Sheet 14. (submit by February 13th for feedback) (5/2/2015: several changes since initial posting earlier in the day; 13/2/2015: correction to Ex 2 (iii))
Solutions to Exercise Sheet 14.
Exercise Sheet 15. (Local Lemma practice for the second exam)
Solutions to Exercise Sheet 15.
Covered material.
Week 1-3 (Additive Combinatorics)
Lecture Notes (Examinable material
Sections 1,2,3,5,7, minus Chang's Lemma, plus statement of
Balog-Szemerédi-Gowers Theorem.)
Weeek 4: [Aigner]: sorting problem,
MergeSort, number of comparisons in MergeSort, information
theoretic lower bound on the running time of any sorting
algorithm, Stirling-formula, Big-O notation, polynomial running time; Algorithms (input/output,
definiteness, correctness, termination, running time, worst
case/average case), [LPV]: minimum spanning tree problem, running time
of Kruskal's Algorithm for MST; Arthur-Merlin story (perfect matching vs Hamilton
cycle), NP intersection co-NP, P vs NP, polynomial
running time, NP-hard, NP-complete problems, [West]: Recall: Hall's
Theorem, Kőnig's Theorem,
characterization of maximum matchings via minimum vertex cover in bipartite graphs.
certificates.
Week 5: [PLV]: Travelling Salesman Problem
(TSP), 2-approximation algorithm for TSP with triangle inequality
[West]: Recall: matching M is maximum if and only if there is no M-augmenting
path, Tutte's Theorem, Augmenting Path Algorithm (APA) to find a maximum matching
and minimum vertex cover in a bipartite graph,Termination and
correctness of APA, Running time is O(mn), the weighted bipartite
matching problem
Week 6: [West]: Hungarian Algorithm, correctness and termination for
arbitrary real weights.
Recall: proper vertex-colorings, chromatic number, upper bound
with Greedy Coloring. Scheduling meetings with project leader
requests, definition of list-coloring, list-chromatic number,
upper bound with Greedy Coloring Algorithm, examples:
K_{2,2}, K_{m,m}. Recall: planar graphs, 5-color theorem,
4-color theorem. Planar graphs are 5-list-colorable (Thomassen's Theorem).
Week 7: [West]: definition of edge-coloring, edge-chromatic
number. Examples: K_4, K_5, K_n, lower bound in terms of max degree,
Petersen. Konig's Theorem about edge-chromatic number of bipartite
graphs. Definition of line graphs, first upper bound on the
edg-chromatic number in terms of the max degree with the help of line
graph. Vizing's Theorem (Schrijver's proof). Edge-list
coloring. List Coloring Conjecture. Galvin's Theorem (proof for
for K_{n,n} via kernels and stable matchings) Stable Matching Problem,
Proposal Algorithm, Proof of termination and correctness of the Proposal
Algorithm,
Week 8: [West]: Recall:
connectivity of a graph is at most its edge-connectivity, characterizations of 2-connected
graphs, Expansion Lemma. 2-connectivity is in NP intersection
co-NP. Four versions of Menger's Theorem (local/global,
vertex/edge), LVMT implies all others. k(n)-connectivity is in NP
intersection co-NP for every function k(n).
Definition of networks, feasible flows, value, maximum flow.
Characterization of maximum flows via augmenting paths, definition of source/sink
cut, capacity of cut, Weak Duality
Lemma, MaxFlow/MinCut Theorem, Ford-Fulkerson Algorithm, termination,
Integrality Theorem, proof of Menger's Theorem (local edge and
vertex versions)
Week 9: [West]: proof of Local Vertex Menger Theorem. [vLW]:
Baranyai's Theorem.
[MG]: linear programming,
definitions, types of linear programs, solving by picture in 2D.
Week 10: [MG]: examples (diet problem, flows), history, motivations,
word problems, integer linear programming,
LP-relaxation, maximum
weighted matching in bipartite graphs, Theorem: there is always an
optimal solution with integer coordinates.
approximation algorithm via LP-relaxation: minimum
vertex cover; LP-relaxation giving nothing: maximum independent set;
Week 11: [MG] every LP can be written in equational form; Farkas Lemma, geometric interpretation, three
equivalent formulations, Weak Duality Lemma,
proof of Strong Duality Theorem using
Farkas Lemma, analytic proof of Farkas Lemma;
Week 12: [MG] (feasible) basis, basic
feasible solution, every LP which is feasible and bounded has an
optimal solution that is basic; finite algorithm to solve LP using
basic feasible solutions, simplex algorithm (
Game Theory (examples of zero-sum games, payoff matrix, best response, worst-case
optimal strategy, (mixed) Nash-equilibrium, weak duality)
Week 13: [MG]: totally unimodular matrices, proof of Kö nig's Theorem
via linear programming; discussion of Helly-type theorems, theorem of
Alon on the transversal number of finite family of d-intervals
Week 14: [*] randomised algorithms; matrix multiplication verification; polynomial zero-testing; Schwartz-Zippel theorem
Week 15: [**] testing for perfect matchings; two-colourability of hypergraphs; random colouring lower bound; deterministic lower bound via Maker-Breaker games; improved lower bound via randomised greedy colouring.
Week 16: [***] Local Lemma (proof for hypergraph 2-coloring),
Application: list-coloring, Algorithmic Local Lemma (proof for
hypergraph 2-coloring)
Notes.
Below are some rough notes and transparencies that contain a skeleton of
some topics of the lectures;
Here are the lecture notes of Giorgis
Petridis for the first three weeks.
Rough
notes to the fourth week
Kruskal's algorithm
Matchings, PvsNP, TSP
Bipartite matching algorithms (updated 18.11)
Listcoloring, edge-coloring, stable matchings (updated 26.11)
Connectivity, network flows, Baranyai's Theorem (updated 10.12)
[*] Lecture notes (skeletal) for Week 14:
Tuesday lecture,
Wednesday lecture
[**] Lecture notes (skeletal) for Week 15:
Tuesday
lecture,
Wednesday lecture,
Erdos-Selfridge
[***] A couple of notes for Week 16:
Local Lemma,
Algorithmic Local Lemma