Ten problems, each worth ten points:
(0 points)
Write the Honor Code Pledge, and sign your name.
(10 points)
A diagnostic message can be sent out over a computer network to perform tests over all links and in all devices. What sort of paths should be used to test all links? To test all devices?
(10 points — 3 points each parts a and b, 4 points part c)
Suppose that a connected planar graph has eight vertices, each of degree three. Into how many regions is the plane divided by a planar representation of this graph?
Suppose that a connected planar graph has 30 edges. If a planar representation of this graph divides the plane into 20 regions, how many vertices does this graph have?
Suppose that a connected bipartite planar simple graph has e edges and v vertices. Show that e≤2v-4 if v≥3.
(10 points)
Use Huffman coding to encode these symbols with given frequencies: a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30.
(10 points)
Determine the orders in which a preorder, inorder, and postorder traversal visit the vertices of the given ordered rooted tree.
a
/ \
/ \
b c
/ \
/ \
d e
/ \
/ \
f g
(10 points)
The roads represented by this graph are all unpaved. The lengths of the roads between pairs of towns are represented by edge weights. Which roads should be paved so that there is a path of paved roads between each pair of towns so that a minimum road length is paved?
---------------------------------- Manhattan
/ / \
/ 25 / \ 60
/ / 55 \
80 / ----------- Tonopah ------- Warm Springs
/ / /
/ 40 / 35 /
/ 25 / 20 /
Dyer ---------- Silverpeak --------- Goldfield
\ / / \
21 \ 23 / 20 / \
\ / 25 / \
Oasis ---------------- Lida \
| | \ 70
10 | 12 | \
| 30 | \
Deep Springs ---------- Gold Point \
\ |
45 \ |
\ |
Beatty
(10 points — 5 points each part)
A rooted tree T is called an Sk-tree if it satisfies this recursive definition. It is an S0-tree if it has one vertex. For k>0, T is an Sk-tree if it can be built from two Sk-1-trees by making the root of one the root of the Sk-tree and making the root of the other the child of the root of the first Sk-tree.
Draw an Sk-tree for k=0,1,2,3,4.
Show than an Sk-tree has 2k vertices and a unique vertex at level k.
(10 points — 3 points each parts a and b, 4 points part c)
Show that ¬(p⊕q) and p⇔q are logically equivalent.
Show that p⇔q and ¬p⇔¬q are logically equivalent.
Show that (p∧q)⇒r and (p⇒r)∧(q⇒r) are not equivalent.
(10 points — 4 points part a, 3 points each parts b and c)
Determine whether ∀x(P(x)⇒Q(x)) and ∀xP(x)⇒∀xQ(x) are logically equivalent. Justify your answer.
Show that ∃x(P(x)∨Q(x)) and ∃xP(x)∨∃xQ(x) are logically equivalent.
Show that ∃xP(x)∧∃xQ(x) and ∃x(P(x)∧Q(x)) are not logically equivalent.
(10 points — 3 points each parts a and b, 4 points part c)
Let A, B, and C be sets. Show that
(A-B)-C ⊆ A-C.
(A-C)∩(C-B) = ∅.
(B-A)∪(C-A) = (B∪C)-A.
(10 points)
Show that if A and B are sets with the same cardinality and C and D are sets with the same cardinality, then A×C and B×D have the same cardinality.
Show that the union of two countable sets is countable.
Show that the set ℤ+×ℤ+ is countable. (As a reminder, ℤ+ is the set of positive integers.)