ARCHIVE PAGE

This page is not updated any more.

Homework assignments
(MATH 3116-001, Fall 2015)
Instructor: Gábor Hetyei Last update: Monday, November 23, 2015

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 30 at latest.

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

No. Date due: Problems:
13 Mo Dec 2 4.5/4b.
12 Mo Nov 23 4.4/8
Board problem: Write the doubly stochastic matrix
as a convex combination of permutation matrices.
11 Mo Nov 16 4.3/6,9. Only explain how you would set up the network flow problem, find a maximum flow and a minimum cut, and interpret the result. There is no need to record augmenting paths and slack graphs, step by step.
4.4/2b
10 Mo Nov 9 4.3/2b.
9 Mo Nov 2 4.2/2,4,8.
Our second test is on Monday November 2. You may download the Sample Test 2 to prepare for it.
8 Mo Oct 26 Board problem: Use bubble sort to sort the list 5,1,3,4,2. Show all phases.
3.4/1a, 4c;   4.1/2ab, 4a
For 3.4/4c you should use Mike Copley's Java applet to build a heap.
Notes regarding the Java applet:
  1. The applet does not take negative numbers, so you have to "cheat".
  2. Then apply the algorithm described in the book and shown in Figure 3.25 to sort the heap. Warning: the procedure in our book to sort the heap is different from what is shown by the applet, so only use the applet to build the heap. Show each stage of the heap while it is being sorted.
  3. By default the Java applet is blocked. Under Windows, open the Control Panel, search for "java" in the search box, and open the Java control panel. Under the "Security" tab, click "Edit Site List" and add the URL http://www2.hawaii.edu/~janst/demos/s97/mike/HSApplet.html

Bonus Problem: 4.1/8
7 Mo Oct 19 3.2/2,4,12ab,20.
Bonus question: Express the degree of each vertex in terms of the adjacency matrix, using matrix multiplication. (I told the solution of this one on Wednesday, October 21, 2015, so this one is not open any more.)
6 We Oct 14 2.4/4,8,14abcd;   3.1/2,6, 31ac.
Bonus questions:
  1. Prove or disprove that every triangulation of a polygon can be colored using three colors, even the ones obtained by adding additional vertices.
  2. Find the chromatic polynomial of a cycle of length n.
5 Mo Oct 5 2.3/2ab, 10ab.
Bonus question: 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.
4 Mo Sep 28 2.2/2ac,4bcp, 16.
Bonus question: Prove Grinberg's theorem (Theorem 3 in section 2.2), using Euler's formula.
3 Mo Sep 21 1.4/2,8,20.
Bonus question: Work out 1.2/2d in detail, explaining how s(x) is directly related to the degree of the vertex x in some graph, and what this implies regarding the parity of the sum of s(x)
Bonus problem (2pts), expires when this assignment is due: Find the theorem in the book (page number, theorem number) stating the number of edges of a tree.
2 We Sep 16 2.1/2,4,10 Bonus question: 2.1/8
1 We Sep 9 1.1/2ab, 6a, 8, 16a;   1.2/2,4,6bfh;   1.3/2,6,12a.
Bonus question: 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.)