Discrete Mathematics II
Winter 2012/13.
|
Exercises.
Exercise Sheet 1.
Exercise Sheet 2.
Exercise Sheet 3. (Nov 3: Slight change in text of Exercise 3)
Exercise Sheet 4.
Exercise Sheet 5. (Dec 4: Cleared up notational ambiguity in
Exercise 1)
Exercise Sheet 6. (Nov 25: Changes to Exercise 3 and 4, Dec 4:
clarified Exercise 1, further change to Exercise 4)
Exercise Sheet 7.
Solution to Exercise 1.
Exercise Sheet 8.
Exercise Sheet 9.
Exercise Sheet 10.
Exercise Sheet 11.
Exercise Sheet 12.
Exercise Sheet 13.
Covered material.
Week 1: [LPV]: Arthur-Merlin story (perfect matching vs Hamilton
cycle), NP intersection co-NP, P vs NP, algorithms (input/output,
definiteness, correctness, termination, efficiency), polynomial
running time, NP-complete problems, [Aigner]: sorting problem,
MergeSort, number of comparisons in MergeSort, information
theoretic lower bound on the running time of any sorting
algorithm, Big-O notation, Stirling-formula, [LPV]: running time
of Kruskal's Algorithm for MST, Travelling Salesman Problem
(TSP), 2-approximation algorithm for TSP,[West]: Hall's Theorem,
characterization of maximum matchings, Kőnig's Theorem, matching M is maximum if and only if there is no M-augmenting path, Augmenting Path Algorithm (APA) to find a maximum matching and a minimum vertex cover in bipartite graphs.
Week 2: [West]: Termination and correctness of APA, Running time is O(mn), Weighted bipartite matching problem, Hungarian Algorithm, correctness and termination for arbitrary real weights. Stable Matching Problem, Proposal Algorithm
Week 3: [West]: Proof of termination and correctness of the Proposal
Algorithm, Recall: colorings, edge-colorings, chromatic number,
edge-chromatic number; definition of list-coloring, scheduling
meetings with project leader requests, list-chromatic number,
upper bound with Greedy Coloring Algorithm, examples: clique,
K_{2,2}, K_{m,m}, List Coloring Conjecture (proof by Galvin for
K_{n,n} via kernels and stable matchings)
Week 4: [West]: Planar graphs are 5-list-colorable; Recall:
connectivity of a graph is at most its edge-connectivity; characterizations of 2-connected
graphs, Expansion Lemma, k(n)-connectivity is in NP intersection co-NP for every
function k(n), Local Menger Theorem implies the Global Menger
Theorem; Definition of networks, flows.
Week 5: [West]: Characterization of maximum flows, MaxFlow/MinCut
Theorem, Ford-Fulkerson Algorithm, termination,
Integrality Theorem, Menger's Theorem (edge- and vertex-,
global and local versions)
Week 6: [vLW] Baranyai's Theorem [MG]: linear programming,
examples (diet problem, flows), history, motivations, definitions,
types of linear programs, solving by picture in 2D.
Week 7: [MG]: word problems, integer linear programming,
LP-relaxation, maximum
weighted matching in bipartite graphs, Theorem: there is always an
optimal solution with integer coordinates.
Week 8: [MG]: approximation algorithm via LP-relaxation: minimum
vertex cover; LP-relaxation giving nothing: maximum independent set;
every LP can be written in equational form; (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
Week 9: [MG]: convexity, convex sets, convex combination, convex hull,
characterization of convex hull, hyperplanes, half-spaces, convex
polyhedra, polytop, dimension, cube, crosspolytop, simplex;
characterization basic feasible solutions of LP in equational form as
vertices of a polyhedra. definition of basic feasible solution of
general LP; basic example of the simplex method (in dimension 2), the
geometric picture, simplex on unbounded polyhedron
Week 10: [MG]:
examples: degenerate LP, auxuliary LP for deciding feasibility/finding
feasible basis;
expressing the unique simplex tableau from a feasible basis;
description and proof of correctness of the simplex method in general;
various pivot rules
Week 11: [MG]: Simplex algorithm using Bland's rule terminates on a
bounded and feasible input; discussion of efficiency of simplex method
(Klee-Minty cube, diameter of a polytope
(Hirsch Conjecture) and of algorithms polynomial in input size (ellipsoid,
interior point methods), algorithms with running time measured in
n and m (randomized Bland's rule)) (no proofs); primal and dual linear program,
weak duality, strong duality with proof via the termination of the
simplex method
Week 12: [MG]: dualization ``dictionary'' (how to obtain the dual of
any linear program); Farkas Lemma, geometric interpretation, three
equivalent formulations, proof of Strong Duality Theorem using the
Farkas Lemma, analytic proof Farkas Lemma;
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: [MG]: (fractional) matching (number) and (fractional) transversal
(number) of a hypergraph; coding theory, Hamming distance,
error-correcting codes, sphere-packing bound, Delsarte bound,
strengthening of the Delsarte bound
Week 15: Exercises
Week 16: Hirsch Conjecture, bound on the diameter of a polyhedron
(Kalai-Kleitman); strongly polynomial vs weakly polynomial algorithms,
randomized simplex algorithms, RandomFacet on an
abstract cube is subexponential
Below are some rough notes and transparencies that contain a skeleton of
some topics of the lectures;
Rough
notes to first week
Matchings
List coloring
Connectivity and network flows (Nov 25: Non-convergent flow network corrected)