COMP 283 FINAL EXAM ACTUAL QUESTIONS AND SOLUTIONS GRADED A+

COMP 283 FINAL EXAM ACTUAL QUESTIONS AND
SOLUTIONS GRADED A+
✔✔Is this a valid induction rule? To show that P is true of all natural numbers, show that
P(0) and P(1) and that for all n ∈ N, P(n) --> P(2n) and P(n) --> P(3n). - ✔✔false

✔✔Is this a valid induction rule? To show that P is true of all the integers, show that
P(0) and for all n ∈ N, P(n) --> P(n + 1). - ✔✔false

✔✔Is this a valid induction rule? To show that P(x, y) is true of all the integers, show
that P(0, 0) and for all n ∈ N, P(n, n) --> P(n + 1, n + 1). - ✔✔false

✔✔Is this a valid induction rule? To show that P(x, y) is true for all x, y ∈ N, show that
P(0, 0), ∀m, n ∈ N(P(m, n) --> P(m, n + 1)), and ∀m, n ∈ N(P(m, n) --> P(m + 1, n)). -
✔✔true

✔✔Is this a valid induction rule? To show that P(x, y) is true for all x, y ∈ N, show that
P(0, 0), ∀n ∈ N(P(0, n) --> P(0, n + 1)), ∀m, n ∈ N(P(m, 0) --> P(m + 1, 0)), and ∀m ∈
N((∀k ∈ NP(m, k)) --> ∀n ∈ N(P(m + 1, n) --> P(m + 1, n + 1))). - ✔✔true

✔✔Is this a valid induction rule? To show that P(x) is true for all x ∈ N, show that if -P(y)
for y ∈ N and y > 0 then -P(y - 1). - ✔✔false

✔✔Is the following relations R well-founded? Define R(x, y) on the integers by x < y. -
✔✔false

✔✔Is the following relations R well-founded? Define R(x, y) on the natural numbers by x
< y. - ✔✔true

✔✔Is the following relations R well-founded? Define R on lists of natural numbers by
R(x, y) if the list x is shorter than y or if x, y have the same length and the sum of the
elements of x is smaller than the sum of the elements of y. - ✔✔true

✔✔K5 is planar. - ✔✔false

✔✔K3,3 is planar. - ✔✔false

✔✔All trees are planar graphs. - ✔✔true

✔✔All trees can be colored with two colors so that no adjacent vertices have the same
color. - ✔✔true

, ✔✔K5 can be colored with four colors so that no two adjacent vertices have the same
color. - ✔✔false

✔✔A tree with 10 nodes must have at least 8 edges. - ✔✔true

✔✔Any connected undirected graph without a cycle is a tree. - ✔✔true

✔✔Any complete graph Kn can be colored with n colors so that no two adjacent vertices
have the same color. - ✔✔true

✔✔A bipartite graph Km,n requires at least 3 colors to color it so that no adjacent
vertices
have the same color. - ✔✔false

✔✔A tree with n vertices has at least n/2 leaves. - ✔✔false

✔✔A graph in which every vertex has odd degree, has an Eulerian path. - ✔✔false

✔✔Every tree has a Hamiltonian path. - ✔✔false

✔✔If any two vertices in an undirected graph can be connected by a path then the
graph
has only one connected component. - ✔✔true

✔✔Any complete graph Kn has a Hamiltonian path. - ✔✔true

✔✔If n is odd then Kn has an Eulerian path. - ✔✔true

✔✔Km,n has an Eulerian path if m is odd and n is even. - ✔✔false

✔✔How many 4-cliques are there in K6? - ✔✔15

✔✔If a planar graph has 5 edges and 4 vertices then how many faces does it have? -
✔✔3

✔✔How many complete ordered binary trees are there with 5 non-leaf vertices? - ✔✔42

✔✔What is the probability to roll a sum of at most 4 on 2 rolls of a fair 6 sided die? -
✔✔1/6

✔✔Suppose A and B are independent events and P r{A} = 1/2 and P r{B} = 2/3. What is
P r{A ∩ B}? - ✔✔1/3