ARCHIVE PAGE

This page is not updated any more.

Homework assignments
(MATH 3116-001, Fall 2023)
Instructor: Gábor Hetyei Last update: Saturday, November 18, 2023

Disclaimer: The information below comes with no warranty. If, due to typographical error, there is a discrepancy between the exercises announced in class and the ones below, or this page is not completely up to date, the required homework consists of those exercises which were announced in class. Check for the time of last update above. If, by my mistake, a wrong exercise shows up below, I will allow you extra time to hand in the exercise that was announced in class. If, however, exercises are missing because this page is not up to date, it is your responsibility to contact me before the due date. (No extra time will be allowed in that case.) This page is up to date if the last update happened after the last class before the next due date.

The deadlines do not apply to the Bonus questions, which expire only once we solve them in class, or on November 27 at latest.

Notation: 5.1/8a means exercise 8, part a, in chapter 5, section 1.

No. Date due: Problems:
12 Mo 11/20 at noon 4.4/2b (use slack graphs),8.
Board problem: Write the doubly stochastic matrix as a convex combination of permutation matrices. Show all steps!
Bonus: Show that no permutation matrix is the convex combination of other permutation matrices (B09, 3 points).
11 Mo 11/13 at noon 4.3/9,16.
10 Mo 11/6 at noon 4.3/6 (no need to show all your work: either show a flow that saturates demand, or a cut whose capacity is smaller than the demand).
9 Mo 10/30 at noon 4.3/2b. Show all slack graphs, all augmenting paths, final flow, and the minimal cut you find using the algorithm.
8 We 10/25 at noon 3.4/4c (use the heap from the lecture notes on November 16, only sort this heap, associated to 3.4/1a);   4.1/2a,2b,4a (bolden the edges that belong to the spanning tree, write above each vertex the cost to get there from the root, and write down the vertices in the order you added them to the spanning tree. You do not need to compute the entire spanning tree, only the part you need to find a minimum weight path);   4.2/2,4,8.
Bonus problem:
  1. Prove that Floyd algorithm finds the matrix of minimum costs as claimed. (B08, 5 points)
7 Mo 10/16 at noon 3.1/31a, 31c;   3.4/1a.

(Mandatory) Board problem: bubble sort (5,1,3,4,2). Show each step as in the notes of October 11.
6 Mo 10/9 at noon 3.1/2,4,6;   3.2/2,4,12ab,20.
5 Mo 10/2 at noon 2.4/14cd. In each question, you have to use the recurrence stated in Theorem 6 at least once!
Bonus questions:
  1. Find the chromatic polynomial of a cycle of length n. Prove your statement by induction. (B07, 5 points)
4 Mo 9/25 at noon 2.3/2ab, 10ab.
3 Mo 9/18 at noon 2.1/2,4,10;   2.2/2ac, 4bc, 16.
Bonus question:
  1. 2.1/8 (B04, 5 points)
  2. Prove that the hypercube graph has a Hamilton circuit. (B05, 5 points)
  3. Prove Grinberg's theorem. (B06, 5points)
2 Mo 9/11 at noon 1.4/2,8,20.
Bonus questions:
  1. Show that for maps with disconnected countries no fixed number of colors suffices to color all maps. (B03, 5 points)
  2. Special bonus question, due with this assignment: find the formula e=v-1 in the book (provide a page number, and name the kind of graphs it applies to).
1 We 9/6 at noon 1.1/2ab, 6a (just give an example), 8, 16a;   1.2/2, 6bfh;   1.3/2,6.
Bonus questions:
  1. Prove that the edge graph of the n-dimensional hypercube is bipartite. (The vertices of the n-dimensional hypercube are all binary strings of length n, two vertices are adjacent when exactly one of their coordinates differs.) (B01, 5 points)
  2. The Petersen graph is shown in the picture below.
    Show that the Petersen graph may also be defined as the graph whose vertices are all 2-element subsets of {1,2,3,4,5} with an edge connecting {i,j} and {k,l} exactly when {i,j} and {k,l} are disjoint. (B02, 5 points)