MA-351, Fall 2024, 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.
Due Thu October 10, 11:59pm.
Please consider the n by n triangular grid graph (n ≧ 2):
Row
i, with
1
≦
i
≦
n,
where row 1 is at the bottom,
has vertices
(
i,
j
)
in columns
j
with
i
≦
j
≦
n,
where column 1 is at the left,
which is the grid does not extend to above the anti-diagonal.
There are edges
{
(i, j),
(i, j+1)
}
for all i with 1 ≦ i ≦ n–1 and j with i ≦ j ≦ n–1,
and
{
(i, j),
(i+1, j)
}
i with 1 ≦ i ≦ j–1 and
for all j with 2 ≦ j ≦ n.
What is the diameter of this graph?
From vertex (1,1) to vertex (n,n)
how many shortest paths are there? Please explain.
Due Thur Oct 10, 11:59pm.
Suppose you have populations of
18000, 11000, 6000
in 3 states and n representatives
are to be allocated using Hamilton's method. There is an Alabama paradox
from
n=14 to n=15.
Here if there is a tie for the largest fractional parts the
state with fewer representatives gets the additional representative.
Please find a second pair (n,n+1) where a paradox is observed.
Due Thur Oct 17, 11:59pm.
DMM, §2.3, Problem 13 on page 51 (for digraph (b) on p. 49 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.]
Due Thur Oct 17, 11:59pm.
Please consider
Stirling's formula for approximating n!
(see also
the 1656 infinite factorization of π/2 by John Wallis
wikipedia link):
n
( 2*π*n )1/2 * (
)n
e
(rendered as an HTML table),
(rendered in presentation MathML)
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.
Convert the expression tree into a minimally parenthesized linear infix
expression string, using precedence and left-to-right rules whenever possible.
Write the prefix and postfix expression string equivalent to the expression tree.
Due Thurs Oct 17, 11:59pm.
DMM §3.3, Problem 8, page 107:
dmm_page_106.jpg.
Note: in order to
have a unique DFS tree, assume that the order of
the neighboring vertices of each vertex is alphabetical
and that you start at vertex labeled a.
Please also indicate when the one-way street assignment is impossible and why.
