COMP 283 COMPREHENSIVE EXAM QUESTIONS AND
SOLUTIONS GRADED A+
✔✔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
✔✔Suppose A and B are mutually exclusive events and P r{A} = 1/2 and P r{B} = 1/3.
What is P r{A ∪ B}? - ✔✔5/6
✔✔What is the expected number of heads in ten tosses of a fair coin? - ✔✔5
✔✔What is the expected sum of three rolls of a fair six sided die? - ✔✔10.5
, ✔✔What is the probability that the second roll of a fair six sided die will be larger than
the
first? - ✔✔15/36
✔✔What is the probability that three rolls of a fair six sided die will all give the same
value? - ✔✔1/36
✔✔What is the expected number of tosses of a fair coin until one gets a heads? - ✔✔2
✔✔What is the expected number of tosses of a fair coin until one gets two heads in a
row? - ✔✔6
✔✔What is the expected number of rolls of a fair six sided die until one gets a number
larger
than two? - ✔✔3/2
✔✔What is the expected value of the product of two successive rolls of a fair six sided
die? - ✔✔12.25
✔✔Suppose A and B are events, P r{A} = 1/2, P r{B} = 1/2, and P r{A ∩ B} = 1/8. What
is P r{A ∪ B}? - ✔✔7/8
✔✔Suppose A and B are events, P r{A} = 2/3, and P r{B} = 2/3. What is the minimum
possible value of P r{A ∩ B}? - ✔✔1/3
✔✔If 5 balls are placed randomly into 3 bins, what is the expected number of balls in
each
bin? - ✔✔5/3
✔✔Suppose one randomly colors the vertices of a clique K4 with two colors. What is the
probability that all vertices will have the same color? - ✔✔1/8
✔✔T/F: If X is a non-negative random variable then P r{X ≥ 5} ≤ E(X)
5. - ✔✔true
✔✔ aa ∈ {a} - ✔✔false
✔✔ab ∈ {a}* - ✔✔false
✔✔ba ∈ {a}{b} - ✔✔false
✔✔ab ∈ {a} U {b} - ✔✔false
SOLUTIONS GRADED A+
✔✔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
✔✔Suppose A and B are mutually exclusive events and P r{A} = 1/2 and P r{B} = 1/3.
What is P r{A ∪ B}? - ✔✔5/6
✔✔What is the expected number of heads in ten tosses of a fair coin? - ✔✔5
✔✔What is the expected sum of three rolls of a fair six sided die? - ✔✔10.5
, ✔✔What is the probability that the second roll of a fair six sided die will be larger than
the
first? - ✔✔15/36
✔✔What is the probability that three rolls of a fair six sided die will all give the same
value? - ✔✔1/36
✔✔What is the expected number of tosses of a fair coin until one gets a heads? - ✔✔2
✔✔What is the expected number of tosses of a fair coin until one gets two heads in a
row? - ✔✔6
✔✔What is the expected number of rolls of a fair six sided die until one gets a number
larger
than two? - ✔✔3/2
✔✔What is the expected value of the product of two successive rolls of a fair six sided
die? - ✔✔12.25
✔✔Suppose A and B are events, P r{A} = 1/2, P r{B} = 1/2, and P r{A ∩ B} = 1/8. What
is P r{A ∪ B}? - ✔✔7/8
✔✔Suppose A and B are events, P r{A} = 2/3, and P r{B} = 2/3. What is the minimum
possible value of P r{A ∩ B}? - ✔✔1/3
✔✔If 5 balls are placed randomly into 3 bins, what is the expected number of balls in
each
bin? - ✔✔5/3
✔✔Suppose one randomly colors the vertices of a clique K4 with two colors. What is the
probability that all vertices will have the same color? - ✔✔1/8
✔✔T/F: If X is a non-negative random variable then P r{X ≥ 5} ≤ E(X)
5. - ✔✔true
✔✔ aa ∈ {a} - ✔✔false
✔✔ab ∈ {a}* - ✔✔false
✔✔ba ∈ {a}{b} - ✔✔false
✔✔ab ∈ {a} U {b} - ✔✔false
