Problems 1, 2 and 3, refer to the following setup:
Suppose you have two dice, a red one and a blue one. The red die is a fair die so it lands on any of its 6 sides with equal probability, but the faces of that die are not all unique: they are {2,2,4,4,6,6}. The blue die is a loaded/unfair die and lands on 4, 5, or 6 twice as often as it lands on 1, 2, or 3. The numbers 1, 2 and 3 are equally likely among themselves, and the numbers 4, 5 and 6 are equally likely among themselves.
(1) What is the probability of rolling a 3 on the blue die?
A) 1/3
B) 1/6
C) 2/9
D) 1/12
E) 1/4
F) 1/9
(2) You roll both die and sum up their visible faces. Which of the following represents the probability of the sum being 3?
A) 1/27.
B) 1/3.
C) 1/6.
D) 1/9. E) 2/9.
F) 1/36.
(3) Denote the co
ect probability in question (2) by p. You roll both die and sum up their visible faces, then repeat the process until you’ve recorded the sum 10 times total. Which of the following represents the probability of never seeing a sum of 3 in any of those 10 rolls?
A) 10p
B) p10
C) (1 − p)10
D) 0
E) 1 − (1 − p)10 F) 1
G) p/10
(4) Recall that to multiply an m × n matrix by an n × k matrix requires m × n × k multiplications. The Google PageRank algorithm uses a square matrix that’s filled with non-zero entries when pages link to one another. Suppose we have m web sites cataloged: this is then an m×m matrix. Denote this matrix by P. P is then run through an iterative algorithm that takes j loops to complete (for 5 < j < 100), and each step of this loop an m × m matrix is multiplied by P.
What is the complexity order of the PageRank algorithm?
A) mj logm
B) m2
C) m3
D) m4
E) m2j2 F) m2 logm
(5) Consider the set given by the following two rules:
· 1 ∈ E
· If x ∈ E, then .
What is the sum of all of the elements of E?
A) The sum is infinitely large.
B) The sum approaches 0 as you include all elements.C) The sum approaches 1 as you include all elements. D) The sum approaches 2 as you include all elements.
E)
F) The sum approaches 1/2 as you include all elements.
(6) Suppose you run a small farm stand that sells Colorado tomatoes and spinach. Each of the two types of produce can be bought as one of three varieties: organic, greenhouse, or field-grown. What is the minimum number of shoppers who each purchase one item needed to guarantee that at least five shoppers buy the same produce in the same variety?
A) 31
B) 26
C) 30D) 6 E) 25
F) 24
G) The number is not listed.
(7) Consider the function g(n) = 2n! + 18nn + 5n3 log(n3) − n2 which represents the complexity of some algorithm. What is the order of g?
A) n!
B) n3
C) n3 logn
D) nn
E) E) −n2
(8) Suppose the United States decides to abolish the penny and replace it with a 3 cent piece, leaving common coin denominations of 3,5,10, and 25 cents. Consider the claim P(k) : “it is possible to make any nonnegative integer k amount of change using only nonnegative integer counts of these denominations.”
A) This claim is valid and its proof is an example of strong induction.
B) This claim is valid and its proof is an example of weak induction.
C) This claim is invalid because it lacks a proper base case.
D) This claim is invalid because there are no assumptions where you could prove the property holds for P(k + 1) making change on k + 1 cents.
(9) Zach’s cooking is sometimes delicious and sometimes nutritious. Suppose in the month of March Zach cooked himself dinner 25 times. 14of those meals were nutritious and 17 were delicious. 8 meals were both nutritious and delicious. How many meals were neither nutritious nor delicious?
A) 23 B) 2
C) 31
D) 8
E) 0
(10) Consider creating a 9-digit number out of the digits 1-9, using each of those digits exactly once. How many such numbers contain the digits XXXXXXXXXXZach’s luggage code - in that order somewhere within them?
A) 9!
B) 5 · 5!
C) 6!
D) 4 · 5!
E) 5!
F) 99
Short Answers. If your answers do not fit in the given box, MAKE A NOTE of where the work is continued or it will NOT be graded!
(11) You’ve joined the CSCI Data Science team, and now you’re in charge of how to distribute projects for students to work on in teams. The 4 projects are: Data Science, Machine Learning, Algorithmic Theory, and Computational Biology. There are 22 students on the team, each of which needs a project.
Please leave your answer unsimplified, in terms of multiplications, sums, powers and factorials. Do not leave the answer in terms of P(n,r) or C(n,r) notations.
(a) How many different ways can you allocate the 22 students to the projects?
(b) For Part (b) only, you realize that you want to make sure that each of the 4 teams has at least3 students. Now how many different ways can you allocate the 22 students to the projects?
For each part, only count the ways to allocate numbers of students: putting 21 students on Data Science and 1 on Biology represents one way, not many. Each student should get a project.
Free response problems. If your answers do not fit in one page, MAKE A NOTE of where the work is continued! Show all work.
(12) Many variants of poker are played with both cards in players’ hands and shared community cards. Players’ hand are some combination of the two sets of cards. For parts (a) and (b), consider playing such that Anna, Brad, Charlie, and Dre each have 2 cards for themselves, and build a 5 card hand out of those 2 cards and 3 shared cards. Assume a standard 52-card deck is being used.
Please leave your answer unsimplified, in terms of multiplications, sums, powers and factorials. Do not leave the answer in terms of P(n,r) or C(n,r) notations.
(a) What is the probability that Anna has a flush, where her 2 cards and the 3 community cardsshare a suit?
(b) What is the probability that Brad also has a flush given that Anna has a flush?
(c) Suppose for the next round, when the cards are dealt a 4th community card is added to thecenter, and play. What is the probability that Charlie has a flush? For this variant, a flush means at least 5 of the 6 cards a player has access to - in their hand or the community - share a suit.
(d) For this round in part (c) with a 4th community card, what is the probability that Dre alsohas a flush given that Charlie has a flush?
(13) Use induction to prove the following rule. Be sure to state all relevant parts of the inductive proof,9 and mention whether you are using strong or weak induction.
(14) Consider the function f(n) = 18n2 − 2n2 log(n) + 5n3 which represents the complexity of some11 algorithm.
(a) Find the smallest nonnegative integer p for which np is a tight big-O bound on f(n). Be sure to justify any inequalities you use and provide the C and k from the big-O definition.
(b) Find the largest nonnegative integer p for which np is a tight big-Ω bound on f(n). Be sure to justify any inequalities you use and provide the C and k from the definition.
(c) Based on your work in parts (a) and (b), what is the order of f?
(d) Verify that your answer in part (c) is co
ect by computing any relevant limits. Show allwork.