Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Exam 3
QUESTIONS PACKET
EECS 203
Practice Exam 2
Name (ALL CAPS):
Uniqname (ALL CAPS):
8-Digit UMID:
***MAKE SURE YOU HAVE PROBLEMS 1 - 19 IN THIS BOOKLET.***
General Instructions
You have 120 minutes to complete this exam. You should have two exam packets.
• Questions Packet: Contains ALL of the questions for this exam, worth 100 points
total. There are 13 Multiple Choice questions (4 points each) and 6 Free Response
questions (8 points each). You may do scratch work on this part of the exam, but only
work in the Answers Packet will be graded.
• Answers Packet: Write all of your answers in the Answers Packet, including your
answers to multiple choice questions. For free response questions, you must show
your work! Answers alone will receive little or no credit.
• You may bring TWO 8.5” by 11” note sheet, front and back, created by you.
• You may NOT use any other sources of information, including but not limited to
electronic devices (including calculators), textbooks, or notes.
• After you complete the exam, sign the Honor Code Pledge on the front of the Answers
Packet.
• You must turn in both parts of this exam.
• You are not to discuss the exam until the solutions are published.
Part A1: Single Answer Multiple Choice
[Only one answer choice is correct in Part A1]
Problem 1. (4 points)
You play a game that involves rolling a 6-sided die and flipping a coin each round. If you
played 8 rounds of this game, how many possible outcomes are there?
(a) 8(6 · 2)
(b) 8(6 + 2)
(c) (6 + 2)8
(d) (6 · 2)8
(e) 62
Solution: (d) (6 · 2)8
Because each round you are rolling a 6-sided die AND flipping a coin, we will be using
the product rule to get the total number of possible outcomes per round. This gives us
6 · 2 outcomes per round. Next, since we want the outcomes of all 8 rounds combined,
we apply the product rule again to get (6 · 2)8
Problem 2. (4 points)
6 green balls, 8 blue balls, and 3 red balls are placed in a bag. You are asked to select 3 balls
from the bag without replacement. If the first ball you pick is green, what is the probability
that after all three picks, you end up with at least two green balls?
(a) 6·5
17·16
(b) 6·5·4
17·16·15
(c) 1− 11·10
17·16
(d) 1− 11·10
16·15
(e) 5
16
Solution: (d)
We are looking for the probability of drawing at least 1 green ball on your last two draws.
To find this, we can find the probability you pick no green balls on your last two draws,
and subtract that from 1. Because we are drawing without replacement, there are 16
total balls in the 16 bag on draw 2. The probability you don’t pick a green ball on your
second draw is the same as the probability of drawing a blue or red ball on your second
draw, which is 11/16 . Similarly, we find the probability for not drawing a green ball on
draw 3 to be 10/15. Multiplying these two probabilities and subtracting from 1 gives us
answer d.
Problem 3. (4 points)
Let G = T1∪T2, where T1 and T2 are each spanning trees with 8 and 12 vertices, respectively,
and T1 and T2 share no vertices. What is the sum of the degrees of each vertex in G?
(a) 40
(b) 20
(c) 18
(d) 36
(e) 64
Solution: (d)
Note that Trees are planar graphs, and thus, we can apply Euler’s Polyhedral formula
(v + f − e− c = 1) on each T1 and T2 to solve for the number of edges.
For T1:
v = 8 (given)
f = 1 (trees have 1 face)
e = unknown
c = 1 (trees are connected).
This gives us 8 + 1− e− 1 = 1 =⇒ e = 7 for T1.
For T2:
v = 12 (given)
f = 1 (trees have 1 face)
e = unknown
c = 1 (trees are connected).
This gives us 12 + 1− e− 1 = 1 =⇒ e = 11 for T2.
This means that G has 7 + 11 = 18 edges in total. By handshake theorem, the
sum of the degrees of all vertices is 2|E| = 2(18) = 36.
Problem 4. (4 points)
How many edges are in Kn ∪Km if they share exactly j vertices?
(a) mnj
(m−1)(n−1)(j−1)
(b)
(
n
2
)
+
(
m
2
)− (j
2
)
(c) m+ n− j
(d)
(
n
2
)
+
(
m
2
)
+
(
j
2
)
(e)
(
m+n−j
2
)
Solution: b
By Inclusion-Exclusion, we know that the number of edges in Kn ∪Km = the number of
edges in Kn + the number of edges in Km - the number of edges in Kn ∩Km.
Kn ∩ Km must be a complete graph with j vertices. So since there are
(
x
2
)
edges in a
complete graph with x vertices, there are
(
n
2
)
+
(
m
2
)− (j
2
)
edges in Kn ∪Km.
Problem 5. (4 points)
Hao has a bag of 14 identical cat treats. How many ways are there to give out all of Hao’s
treats to 5 differently colored cats with each cat receiving at least two treats?
(a)
(
14
5
)
5!
(b)
(
8
3
)
(c)
(
14
5
)
25
(d)
(
9
5
)
(e)
(
8
4
)
Solution: (e)
This is a balls ’n bars problem. The indistinguishable cat treats are the 14 balls and the
5 distinguishable cats mean 5-1=4 bars. Since each cat has to have at least 2 treats we
end up with 14− 2 · 5 = 4 balls left. 4 balls and 4 bars gives us (8
4
)
Problem 6. (4 points)
If p(E) = 0.8 and p(F ) = 0.4, what is the minimum possible value of p(E ∩ F )?
(a) 0
(b) 0.16
(c) 0.20
(d) 0.32
(e) 0.40
Solution: (c)
Using p(E ∪ F ) = p(E) + p(F ) − p(E ∩ F ). Rearranging, we get p(E ∩ F ) = p(E) +
p(F ) − p(E ∪ F ). We can plug in the values we know, getting 0.8 + 0.4 − p(E ∪ F ). If
we want to minimize this value, we want to subtract as much as possible. The largest
p(E ∪ F ) could be is 1 (since 0.8+0.4 is at least 1, but it should still be a probability)
This means the smallest p(E ∩ F ) can be is 0.8 + 0.4− 1 = 0.2
Problem 7. (4 points)
What is the tightest big-O bound on the runtime of this algorithm?
procedure happyfinal(n):
happyfinal(n/8)
happyfinal(n/8)
k = 1
for i := 1 to n:
for j := 1 to n:
k = k * 2
happyfinal(n/8)
happyfinal(n/8)
return
(a) O(
√
n)
(b) O(n log n)
(c) O(n2)
(d) O(n2/3)
(e) O(n2 log n)
Solution: (c)
The runtime for this algorithm, T (n), can be described as
T (n) = 4T (n/8) + n2
a = 4 because the function happyfinal is called 4 times, b = 8 because happyfinal is called
with input size ⌊n/8⌋, and d = 2 because the nested for loops run in n2 time (notice k
has nothing to do with the runtime of these loops). Applying the master theorem, we
observe that 4
82
< 1, so T (n) = O(nd) = O(n2).
Problem 8. (4 points)
What is the coefficient for the y18 term in the expansion of (5x5y2 + 8
x3
)24?
(a) 0
(b)
(
24
15
)
518 · 86
(c)
(
24
6
)
56 · 818
(d)
(
24
24
)
524 · 80
(e)
(
24
9
)
59 · 815
Solution: e
The binomial theorem tells us that
(5x5y2 +
x3
)24 =
24∑
k=0
(
24
k
)
(5x5y2)k(
8
x3
)24−k
We can simplify this to get
=
24∑
k=0
(
24
k
)
5k824−kx5k−3(24−k)y2k =
24∑
k=0
(
24
k
)
5k824−kx8k−72y2k
We want our term to have y18, so we need 2k = 18, so k = 9. Plugging this in, we get(
24
)
59824−9x8·9−72y2·9 =
(
24
9
)
59815x0y18 =
(
24
9
)
59815y18
8