MA-351 Homework 2
Due as indicated for each problem.

All solutions must be submitted on the Moodle web site for the class at wolfware.ncsu.edu. You may upload a photo of your handwritten solution or a file of your typed solution.
Note my office hours on my schedule.
  1. Due Thur Oct 12, 11:59pm.
    A subgraph of the (n+1)st-dimensional hypercube is constructed by removing all edges {0b2...bn+1, 1b2...bn+1}, bi ∈ {0,1}, except {00...0,10...0} and {01...1,11...1}. Overall, 2n-2 edges are removed. Please prove that the resulting subgraph has diameter n+1.

  2. Due Thur Oct 12, 11:59pm.
    Suppose you have populations of 11000, 9000, 5000 in 3 states and n representatives are to be allocated using Hamilton's method. There is an Alabama paradox from n=12 to n=13. Please find a second pair (n,n+1) where a paradox is observed.

  3. Due Thur Oct 19, 11:59pm.
    DMM, §2.3, Problem 13 on page 51 (for digraph (b) only): A (sub)set C of vertices in a digraph D = (V,A) is called a vertex contrabasis if every vertex u in V can reach at least one vertex in C and the set is minimal in the sense that no proper subset of C has this property. Find all vertex contrabases for the digraph (b) of Fig. 2.17. dmm_page_49.jpg.
    Hint: does the notion of converse help here? [Exer. 12: The converse D' of a digraph D is defined as follows: the vertex sets are the same, and (u,v) is an arc in D if and only if (v,u) is an arc in D', that is, to form D', we reverse all arcs of D.]

  4. Due Thur Oct 19, 11:59pm.
    Please consider those paths of length 2n on an (n+1) × (n+1) grid from the bottom left to the top right grid point that correspond to a binary tree with n vertices and therefore do not contain to a grid point below the diagonal, as discussed in class. Among those paths, consider those special paths whose only grid points on the diagonal are the starting and ending point, that is, all intermediate points are stricly above the diagonal.
    1. What property in regard to the subtrees of the corresponding tree is implied for all special paths?
    2. How many such special paths are there in terms of n.

  5. Due Thur Oct 19, 11:59pm.
    Please consider the formula, which multiplies two fractions, for approximating the n-th Catalan number, based on Stirling 's formula for approximating n! (see also the 1656 infinite factorization of π/2 by John Wallis wikipedia link):
    1
    		22*n
    		*
    		  (rendered as an HTML table),  
    n+1
    		(π*n)1/2
    		1 n+1 * 22*n (π *n) 1/2   (rendered in presentation MathML).
    1. Using the binary operators + (plus), – (minus), * (times), / (divides), and ↑ (exponentiation), all of which have exactly 2 operands, draw the expression tree corresponding to this expression. Please note that 1/2 is a division and not a constant.
    2. Convert the expression tree into a minimally parenthesized linear infix expression string, using precedence and left-to-right rules whenever possible.
    3. Write the prefix and postfix expression string equivalent to the expression tree.