EECS 203 Practice Exam 1 Fall 2024 PDF

PRACTICE Exam 1 Solutions EECS 203, Fall 2024 Name (ALL CAPS): Uniqname (ALL CAPS): 8-Digit UMID: Instructions When you receive this packet, fill in your name, Uniqname, and UMID above. Once the exam begins, make sure you have problems 1-16 in this...

PRACTICE Exam 1 Solutions EECS 203, Fall 2024 Name (ALL CAPS): Uniqname (ALL CAPS): 8-Digit UMID: Instructions When you receive this packet, fill in your name, Uniqname, and UMID above. Once the exam begins, make sure you have problems 1-16 in this booklet. Write your UMID in the blank at the top of every other page. No one may leave within the last 10 minutes of the exam. After you complete the exam, sign the Honor Code below. If you finish when time is called, your proctor will give you time to sign the Honor Code. Do not detach the scratch paper at the end of the packet. Do not discuss the exam until solutions have been released! Materials No electronics allowed, including calculators. You may use one 8.5′′ by 11′′ note sheet, front and back, created by you. You may not use any other sources of information. Honor Code This exam is administered under the College of Engineering Honor Code. Your signature endorses the pledge below. We will not grade your exam without your signature. I have neither given nor received unauthorized aid on this examination, nor have I con- cealed any violations of the Honor Code. I further agree not to discuss any aspect of this examination in any way, shape, or form until the solutions have been published. Signature: EECS 203 Page 1 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Part A: Single Answer Multiple Choice Instructions There are 6 questions in this section. Shade the bubble you believe to be correct. There is only one correct answer option for each question in this section. If you shade more than one bubble, your answer will be marked as incorrect. Example. a b c d e Make sure to SHADE A BUBBLE next to the question title, as shown above. Problem 1. (4 points) a b c d e Emily is throwing three distinguishable balls into three distinguishable buckets. How many ways can they put all the balls in the buckets such that at least one bucket is empty? (a) 3 (b) 6 (c) 12 (d) 21 (e) 27 Solution (d) There are two cases: you can either put all 3 balls in the same bucket, or put 2 balls in one bucket and the remaining ball in another bucket. Case 1: put all 3 balls in the same bucket You just need
to choose which of the 3 distinguishable buckets to put the balls in, so 3 there are 1 ways to put all 3 balls in the same bucket. Case 2: put 2 balls in one bucket and the remaining ball in another bucket 3
First, choose the 2 balls that will be put together in the same bucket: 2. 3
Next, choose the 2 buckets that will contain at least one ball: 2. Finally, pick
the
bucket out of these 2 that contains the 2 balls you chose earlier. There are 32 32 · 2 ways to put 2 balls in one bucket and the remaining ball in another bucket. EECS 203 Page 2 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide In total, there are 21 = 31 + 3

3
2 2 · 2 ways to put all the balls in the buckets such that at least one bucket is empty. Alternate Solution: Start by counting all ways to place them regardless of whether a bucket is empty. Each ball has 3 options, so we have 33 = 3 · 3 · 3 = 27 ways to place them. This overcounts by all the ways we put them in buckets such that they are all full. This can only be done with each bucket having 1 ball in it. There are 3! = 6 ways to rearrange which buckets they go in. This makes 27 − 6 = 21 ways that are valid. Problem 2. (4 points) a b c d e Suppose we color each of the vertices of C4 red or blue at random (equally likely). What is the probability that no edge connects two vertices of the same color? (a) 1/16 (b) 1/8 (c) 1/4 (d) 1/3 (e) 1/2 Solution (b), With C4 , there are only two ways we can color the vertices such that no two adjacent vertices are the same color. Starting from the top-left, colors alternating like Red-Blue- Red-Blue or the other way around, with Blue-Red-Blue-Red. Thus the size of the event space is 2. The size of the sample space is the total number of ways one can color the graph using 2 colors. Each vertex will have 2 options - Red or Blue. Thus, the total number of combinations would be 2 × 2 × 2 × 2 = 24 = 16 |E| 2 1 Putting this together, we have that the probability p = |S| = 16 = 8 EECS 203 Page 3 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Alternate solution: Fix one vertex as the starter vertex. In any coloring, it must have a color. For that color of that vertex, there are 23 = 8 ways we could color the other vertices, only 1 of which has no two adjacent vertices the same color. Again, this gives p = |E| |S| = 18. Problem 3. (4 points) a b c d e What is the Big-Θ bound on the runtime of this algorithm? Pokern for i := 1 to n do end j ← 1 while j < n do end j ← j ∗ 2 print ‘All in’ for i := 1 to n do end print ‘Doubled up’ (a) Θ(n3 ) (b) Θ(n2 log(n)) (c) Θ(n2 ) (d) Θ(n log(n)) (e) Θ(n) Solution There are two main loops to examine in this algorithm. Looking at the inside of the first one first: we see that j starts at 1 and doubles until it is no longer less than n, at which point this terminates. This is repeated n times overall. The runtime of the inner loop is thus log n for an overall runtime of n log n of the first nested loop. As the second loop is only n runtime, we can absorb it into the first loop and the runtime of the algorithm is Θ(n log n + n) = Θ(n log n) EECS 203 Page 4 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 4. (4 points) a b c d e Mariko likes to study at a local cafe. She noticed the following about her caffeine and study habits: When Mariko drinks coffee, the probability that she finishes her homework is 3/4. When she finishes her homework, the probability that she drank coffee is 3/7. She drinks coffee 2/7 of the time. How often does she finish her homework? (a) 1/4 (b) 3/7 (c) 1/2 (d) 3/4 (e) 3/14 Solution (c) Let H = Mariko finishes her homework, and let C = Mariko drinks coffee. P (H|C) = 3/4, P (C|H) = 3/7, P (C) = 2/7. Solution 1: These terms are 3 of the 4 terms in Bayes Theorem when finding P (H|C): P (C|H)P (H) P (H|C) = P (C) 3 3/7 · P (H) = 4 2/7 Solving for P (H), we get P (H) = 1/2. Solution 2: We can use conditional probabilities to compute their intersectional probability. For ex- ample, we have P (H|C) = 3/4 and P (C) = 2/7, so we know P (H ∩C) = P (H|C)P (C) = 3/4 · 2/7 = 3/14. We can also compute this using P (C|H). P (H ∩ C) = P (C|H)P (H). We know P (C|H) = 3/7, and from above, we know that P (H ∩ C) = 3/14, so apparently 3/14 = 3/7 · P (H). Dividing through by 3/7 yields P (H) = 1/2. EECS 203 Page 5 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 5. (4 points) a b c d e You’re setting up groups for students to work on a homework assignment. How many ways are there to split 7 students in two groups of two and one group of three? You may assume that the students are distinguishable. (a) 72 52

(b) P (7, 2) + P (5, 2) + P (3, 3) (c) 72 52 · 21

(d) P (7, 2)P (5, 2)P (3, 3) (e) 3!2!2! Solution (c) You choose 2 out of the 7 students for your first group of two, and then choose the next 2 out of the remaining 5 students for your second group of two. The 3 students left, form the group of three. However, this way of counting introduces order between the first and the second group (not the third group since its different size makes it distinguishable compared to the groups of 2). Since the two groups are indistinguishable, the order in which the groups are picked shouldn’t matter (ie, there should be no difference between the “first” and the “second” group of 2). So we divide by 2!. Incorrect Options: (a) This introduces order between the two groups of 2. Example: if you choose students A and B for your first group of 2 followed by students C and D. This is considered dif- ferent from choosing C and D first followed by A and B. To remove this ordering, the correct solution divides by 2! (b) This is the same as option d, however, the terms are added instead of multiplied. Adding the terms is further incorrect because adding implies that selecting the three groups are three different cases which are mutually exclusive. Since choosing the three groups is a sequential action, the correct option multiplies the terms. (d) This option considers the groups distinguishable like in option a, and takes into ac- count the order in which students are selected in each group (since it uses permutation instead of combination). (e) This option has the students for each group picked already and counts the number of ways to order the students in each group. 3! for the students in the group of 3, 2! for one of the groups of 2 and 2! for the other group of 2. EECS 203 Page 6 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 6. (4 points) a b c d e What is the Big-Θ bound on the runtime of this algorithm? AdvancedAlgorithmn if n ≤ 1 then end return for i := 1 to 10 do end AdvancedAlgorithm(n/2) for i := 1 to n do end j := 1 to n for k := 1 to n do end print ‘final stretch!’ (a) Θ(n3 ) (b) Θ(log n) (c) Θ(n4 ) (d) Θ(n3 log n) (e) Θ(nlog2 10 ) Solution (e) Θ(nlog2 10 ) This algorithm calls itself recursively 10 times, each with size n/2. It then prints “final stretch” a bunch of times. We have 3 nested loops each running n cycles, so we have n · n · n = n3 runtime for the loops. This gives a recurrence of T (n) = 10T (n/2) + n3. This is in the form that the Master Theorem applies to. a = 10, b = 2, and d = 3, so a/bd = 10/23 = 10/8 > 1. This means the algorithm runs in time O(nlogb a ) = O(nlog2 10 ) EECS 203 Page 7 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Part B: Multiple Answer Multiple Choice Instructions There are 3 questions in this section. Shade whichever boxes you believe are correct. This could be all answers, no answers, or anything in between. If there are no correct answers, leave all the boxes blank. Example a b c d e Make sure to SHADE 0 OR MORE BOXES next to the question title, as shown above. Problem 7. (4 points) a b c d e Which of the following can you always find if you only know P (E|F ) and P (F )? (a) P (E ∩ F ) (b) P (E ∩ F ) (c) P (E ∩ F ) (d) P (E|F ) (e) P (E|F ) Solution (a), (b), (e) (a) P (E ∩ F ) = P (E|F )P (F ) (b) P (E ∩ F ) = P (E|F )P (F ) (by part e, we can find P (E|F )) Alternately: P (E ∩ F ) = P (F ) − P (E ∩ F ) (by part a, we can find P (E ∩ F ) (c) P (E ∩ F ) = P (E|F )P (F ). While we can compute P (F ), any value for P (E|F ) would still be consistent with our fixed values. Knowing P (E) would also be sufficient to determine the value (d) see part c (e) P (E|F ) = 1 − P (E|F ) EECS 203 Page 8 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 8. (4 points) a b c d e You roll a fair five-sided die with faces 1, 2, 3, 4, and 5 and a fair three-sided die with faces 1, 2, and 3. Let X be the random variable representing the outcome of the five-sided die. Let Y be the random variable representing the outcome of the three-sided die. Which of the following statements are correct? (a) p(X = 3) = 0.2 (b) p(X > 3) = 0.4 (c) p(Y = 2) < p(X = 2) (d) E(X) = 3 (e) E(X + Y ) = 5 Solution (a), (b), (d), (e) Since the dice are fair, then each face comes up with equal probability, therefore, p(X = 1) = p(X = 2) = p(X = 3) = p(X = 4) = p(X = 5) = 0.2, and p(Y = 1) = p(Y = 2) = p(Y = 3) = 31. This explains answer (a). Answer (b) follows directly since p(X > 3) = p(X = 4) + p(X = 5) =.2 +.2 =.4. It also follows directly that p(Y = 2) = 31 > 0.2 = p(X = 2), and thus (c) is false. Now to calculate E(X), we see E(X) =.2 · 1 +.2 · 2 +.2 · 3 +.2 · 4 +.2 · 5 = 3, thus (d) is correct. Then E(Y ) = 31 · 1 + 13 · 2 + 13 · 3 = 2. By linearity of expectation, E(X + Y ) = E(X) + E(Y ), and so E(X + Y ) = 3 + 2 = 5, thus (e) is correct. EECS 203 Page 9 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 9. (4 points) a b c d e Consider positive-valued functions f and g, where: f is O(n3 ) and Ω(n) g is O(n2 ) and Ω(log n) Which of the following could be true? (a) f · g is Θ(n2 ) (b) f · g is Θ(n5 log n) (c) f + g is Θ(n) (d) f + g is Θ(n2 log n) (e) 1000f is Θ(n3 ) Solution (a), (c), (d), (e) A tight-bound estimate must grow no faster than the upper-bound estimate and no slower than the lower-bound estimate. To get the lower-bound and upper-bound estimates for f · g, we can multiply their respective Big-Ω and Big-O functions: f · g is Ω(n log n) f · g is O(n5 ) To get the lower-bound and upper-bound estimates for f + g, we can take the maximum their respective Big-Ω and Big-O functions: f + g is Ω(n) f + g is O(n3 ) (a) f · g is Θ(n2 ) could be true since n2 grows faster than n log n and slower than n5. (b) f · g is Θ(n5 log n) could NOT be true since that would mean that it grows faster than our upper-bound estimate for f · g. (c) f + g is Θ(n) could be true since n grows at the same rate as n and slower than n3. (d) f + g is Θ(n2 log n) could be true since n2 log n grows at the same rate as n and slower than n3. (e) 1000f is Θ(f ), so we have the same bounds on 1000f as we did on f. This means 1000f could be Θ(n3 ). EECS 203 Page 10 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Part C: Short Answer Instructions There are 2 questions in this section Write your solution in the space provided below the question Don’t simplify your answers Show your work and include justification Problem 10: Combinatorial Proof (8 points) Use a combinatorial proof to show that:   X n     3n n 2n = · n k=0 k n−k Story: LHS: RHS: EECS 203 Page 11 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Solution Our Story: Count the number of ways to pick n animals from a total of n dogs, and 2n cats. LHS:
For the left side, simply choose n animals from the total of 3n animals, for a total of 3nn choices. RHS: For the right side, each term in the summation represents the
number of ways to pick k dogs to include from the n total dogs, which is counted by nk. For each choice of k dogs, we
need to pick n − k animals left from the remaining two groups. This is counted 2n by n−k to this sum. We multiply these two numbers because for each possibility of 2n
choosing a dog, we have n−k ways to choose the remaining animals. We also need to cover every possible combination of dogs and cats to form a group of size n, so we sum over k = 0 to k = n Conclusion:
Pn Since
2nthe
two sides count the same situation, it must be the case that 3n n n = k=0 k · n−k Grading Guidelines [8 points] Story +1 Set up 3n objects +1 Divide the 3n objects into pools, and one of the pools have n objects. (No credit if this is done in RHS, or if RHS doesn’t refer to a SPECIFIC pool created here.) +1 Choosing n generic objects from the objects above, ignoring the pool division. LHS +1 Correct combinatorial explanation of 3n choose n RHS +1 Correctly explaining the meaning of k +1 Correct combinatorial explanation of n choose k +1 Correct combinatorial explanation of 2n choose n-k +1 Correctly justify the sum over k=0 to n in RHS, especially the domain of k Common Mistakes Many students did not preallocate their pools of objects beforehand in the story, choosing only to divide the pools in the RHS. Oftentimes the division into pools involves a choice, something which is not ac- counted for. For instance, students might have setup their story saying that “there are 3n people”. Then, in the RHS, they say “out of these 3n people, pick the first n of them, and choose k from those n”. Alright, but how do you define an order on the 3n people? According to the story, there just are 3n people, with no semblance of a preexisting order amongst the people. Adding an ordering to the EECS 203 Page 12 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide people involves a choice of how to order them, which is not accounted for. Even if in the RHS, the allocation into pools is something inherent to the nature of the pool, we still cannot accept points, since such a preallocation should have been done in the story. For instance, after writing “there are 3n people” in the story, students might have written “now, out of those 3n people, n of them are men, and we pick k from them”. This constraint on the pool of 3n people should have been specified in the story. A subtle mistake that a few students made, was to use 3 pools of n indistinguishable objects, e.g. n oranges, n apples, n pears. If the objects are indistinguishable, the number of ways to pick n objects is not C(3n, n), but is in fact a stars and bars question, with n stars and 2 bars, meaning the answer is C(n+2, 2). For this qn, we generally gave students the benefit of the doubt, unless they explicitly mentioned the items as being indistinguishable. Another mistake, which we were generally lenient with, is mentioning that there are 3 pools of n people. Then, in the RHS, mention that you pick k from the “first pool”. In the story, there is no notion of first pool, so you are technically missing the 3 ways to pick the “first pool”. However, we mostly did not penalize for this lapse. Problem 11: King Arthur’s Round Tables (7 points) After experiencing financial trouble and moving to a smaller castle, King Arthur sold the original round table and found two smaller identical round tables that could each seat 50 knights. Find the number of unique seating arrangements for 150 knights if a seating ar- rangement is considered the same as long as each knight has the same knight seated to his left and the same knight to his right. Note: Since there are 100 seats, King Arthur won’t be able to seat 50 of the knights. EECS 203 Page 13 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Final Answer: Justification: Solution P (150,50)·P (100,50) 2!(502 ) First, order 50 out of the 150 knights in a line and place them in order at one of the tables. There are P (150, 50) possible orderings of these 50 knights. Next, order 50 out of the 100 remaining knights in a line and place them at the other table. There are P (100, 50) possible orderings of these 50 knights. It doesn’t matter which table the knights are seated at, as long as they have the same knights to their left and right. Divide by 2! to account for indistinguishable tables. Rotations around each table are also considered the same seating arrangement, so divide by 502 (one for each table) to account for circular tables. EECS 203 Page 14 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Alternate Solutions: Any solution that is numerically equivalent to the solution above merits full credit. Some examples include:
100
50! 2 1 150 100 50 ( 50 ) ( 2! )
100
50! 2 1 150 100 50 ( 50 ) ( 2! ) P (150, 100)/(502 · 2) Grading Guidelines [7 points] +1.5 Selects 100 out of the 150 knights +1 Assigns 50 knights per table +1.5 Permutes the knights +1.5 Correctly accounts for circular tables +1.5 Correctly accounts for indistinguishable tables -0.5 Extraneous terms in an otherwise correct solution -0.5 Extraneous terms that are unjustified from above rubric item Common Mistakes: Dividing by 3! to account for the circular tables instead of 502. This question is different than the problem from the homework, where in the homework problem, we divided by 3! 4 times to account for each side’s 3 people’s order not mattering. The reason we’re dividing by 50 in this problem is because we have a circular table, and when we say an arrangement is the same when each knight has the same left and right neighbor, there are 50 ways we can rotate all the knights and still have them in the same arrangement, and thus we’re overcounting by a factor of 50 for each table, so 502 for 2 tables. Using sum rule when ordering the knights. Notice that the decisions we’re making in this problem are all being done sequentially in the same case, and thus we should be using product rule. Sum rule applies when we have different non-overlapping cases. Multiplying by 50! only once. We have two tables, and we need to order our knights on both tables. Dividing by 50 only once. Again, we have two tables, and need to account for the overcounting for both tables. Dividing by 50! or 100! to account for circular tables. Consider how we are over- counting. We are overcounting due to the circular nature of the table and how having the same left and right neighbor equates to an equivalent arrangement, thus we overcount by a factor of 50 per table. Overcounting by 50! would mean that the ordering of these knights on the table doesn’t matter, which is incorrect. EECS 203 Page 15 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Using combinations, but not multiplying by 50!. Knights are distinguishable, so the order in which they sit matters too. After choosing the 50 knights for a table, we must also multiply that by 50! since there are 50! possible orderings of these 50 distinct knights. Using the combination formula for permutations, or vice versa. Review the notation for each of these, as they are different and must be used in different situations. EECS 203 Page 16 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Part D: Free Response Instructions There are 5 questions in this section Write your solution in the space provided Write down your answer with care: answers that are unreadable (such as too faint or too messy) will not be graded If you have multiple answers, you must indicate which one you want graded. Otherwise, we will grade your least favorable answer. Show your work and include justification Problem 12: A Colorful Question (10 points) Ian wants to color the vertices of the graph C4 (depicted below) with one restriction: if two vertices are adjacent, then they must have different colors. Ian has 3 colors to choose from: red, yellow, and blue. How many ways can he color the graph? Note: The vertices are distinguishable, and Ian does not have to use all three colors. 1 2 3 4 Remember to justify your answer. Final Answer: EECS 203 Page 17 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Solution 18 There are many valid solutions, here are a few of them: Cases by Number of Colors: Ian must use at least 2 colors, so he can use either 2 or 3 colors. Case 1: He uses 2 colors. First we choose which of the two colors he uses ( 32 options).
Then once he chooses a color for vertex 1 (2 options), the colors for the rest of the vertices are determined, so there are 2 possibilities. Case 2: He uses 3 colors. Then there is one way to choose the three colors: 33 = 1.
Case 2a: 2 and 3 have different colors. Choose a color for 1 (3 choices), then for 2 (2 choices), then for 3 (1 choice). Then vertex 4 must have the same color as 1 (1 choice). So we have 3 · 2 choices. Case 2b: 2 and 3 have the same color. Choose a color for 1 (3 choices), then for 2 and 3 (2 choices). At this point we’ve only used 2 colors, so 4 must use the third color so that we use exactly 3 colors (1 choice). So we have 3 · 2 choices again. Alternatively we can directly count this case by choosing which color to use twice (3 ways), then there are two choices for which pair of vertices receive this color (1 and 4, or 2 and 3), and then two ways to use the remaining two colors, yielding 3 · 2 · 2 ways. So overall our count is 32 · 2 + 33 · (3 · 2 + 3 · 2) = 32 · 2 + 33 · (3 · 2 · 2) = 18.



Cases on Vertices 2 and 3: We can directly compute the number of ways Ian can color the graph using at most 3 colors. Case 1: 2 and 3 have different colors. First choose a color for vertex 1 (3 choices), then for 2 (2 choices), then 3 (1 choice). Then since vertex 4 can’t be the same colors as 2 or 3, we have 1 choice, yielding 3 · 2 · 12 = 3 · 2 choices overall. Case 2: 2 and 3 have the same color. Then first choose a color for vertex 1 (3 choices), then for 2 and 3 (2 choices). Then there are 2 choices for vertex 4, yielding 3 · 22 choices. So overall we have 3 · 2 + 3 · 22 choices. Subtractive Alternate Solution: If we do not account for the restriction, we can color each vertex 3 ways accounting for the 3 different colors, resulting in 34 total colorings. Next, we must subtract the total number of colorings which violate this constraint. We can break these into cases by how many colors are used. Case 1: We only use one color. All colorings using just one color violate the constraint trivially, and we see there are 3 ways to color the graph if we only use one color. Case 2: We can color the graph using 2 colors in a way that violates the constraint in two ways: EECS 203 Page 18 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Case 2a: Two adjacent vertices share the same color, and the remaining two share a different color. There are 2 ways we can group the vertices: either {1, 2} are one color and {3, 4} are both a different color, or {1, 3} are one color and {2, 4} are both a different color. We multiply this by the number of ways to choose a color for the first set of vertices, which is 3, and then by the number of ways to choose a color for the second set of vertices, which is 2 because we cannot choose the color of the first set. This totals 2 · 3 · 2 ways. Case 2b: Three vertices share the same color, and the remaining vertex is a different color. The number of ways to pick a vertex that is a different color from the rest is 4. The number of ways to pick the color for this vertex is 3, and the number of ways to pick the color of the remaining vertices is 2. This results in 4 · 3 · 2 ways. Case 3: Lastly, we must subtract ways to color the graph with 3 different colors in a way that violates the constraint. There are 4 ways to pick a pair of adjacent vertices that will share a color: {1, 2}, {2, 4}, {4, 3}, and {3, 1}. We multiply this by the number of ways to choose the color of these two vertices, which is 3, and then by the number of ways to color the remaining two vertices, which is 2, for 2 possible permutations of the remaining two colors. This results in 4 · 3 · 2. When we subtract the number of ways to color the graph in a way that violates the constraint from the total number of colorings, we get 34 − (3 + 2 · 3 · 2 + 4 · 3 · 2 + 4 · 3 · 2) Subtractive Alternate Solution 2: We can start at vertex 1 and move around the graph clockwise then subtract the number of invalid colorings counted. There are 3 colors to choose from for vertex 1. We multiply this be the 2 ways we can color vertex 2, because it cannot be the same color as vertex 1. Similarly, vertex 4 can be either color other than what vertex 2 is, so it has 2 options. If we ignore the restriction between vertices 1 and 3, there are also 2 ways to color vertex 3, resulting in 3 · 2 · 2 · 2 total colorings. Now we must subtract the number of colorings that violate the restriction between 1 and 3 but satisfy all others. In this case 1 and 3 are the same color but 2 and 4 are each a different color. There are 3 ways to choose a color for 1 and 3. We multiply this by the 2 ways to permute the remaining 2 colors across vertices 2 and 3, resulting in 3 · 2. This yields a final answer of 3 · 2 · 2 · 2 − 3 · 2 Cases on which pairs of vertices share a color: Because there are only 3 colors and 4 vertices, there must always be at least one pair of diagonal vertices which share a color. We can break the problem down into three non-overlapping cases based on which vertices share a color and add them together. Case 1: Vertices 1 and 4 share a color, and the remaining two are different colors. There are 3 ways to pick a color for 1 and 4, and 2 · 1 ways to permute the remaining two colors over the remaining two vertices, yielding 3 · 2 · 1. Case 2: Vertices 2 and 3 share a color, and the remaining two are different colors. Same as in the last case, there are 3 ways to pick a color for 2 and 3, and 2 · 1 ways to permute EECS 203 Page 19 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide the remaining two colors over the remaining two vertices, yielding 3 · 2 · 1. Case 3: Vertices 1 and 4 share a color and vertices 2 and 3 share a color. There are 3 ways to pick a color for the first pair, and 2 ways to pick a color for the second pair so that it is different from the color of the first pair. This results in 3 · 2 ways. Once we add all of the cases together, there are 3 · 2 · 1 + 3 · 2 · 1 + 3 · 2 ways to color it. Direct Solution: First we compute the number of ways to assign colors to vertices 1 and 2. There are 3 ways to assign a color to vertex 1, which is multiplied by 2 ways to choose a color for vertex 2, as it cannot be the same color as vertex 1. For the remaining two vertices there are 3 ways to color them: Vertex 3 is the same color as vertex 2, and vertex 4 is the same color as vertex 1. In this case, only two colors are used. Vertex 3 is the same color as vertex 2, and vertex 4 is the third, previously unused, color. In this case, all three colors are used. Vertex 4 is the same color as vertex 1, and vertex 3 is the third, previously unused, color. In this case, all three colors are used. We multiply by 3 to account for these distinct cases, resulting in 3 · 2 · 3. Grading Guidelines [10 points] Primary rubric (cases) +1.5 At least 1 correct case +2 Case breakdown is fully correct +1.5 At least 1 case is computed correctly +1.5 At most one case is incorrect +2 Counts each case/term correctly with justification +1.5 Correctly combines terms/cases Partial credit rubric (no cases) +3 Uses the adjacency restriction to argue that a particular vertex has fewer than 3 possible colors +3 Mostly correct solution but fails to account for one adjacency restriction Alternate rubric (brute-force) +1.5 Mostly correct list (may be missing only a few possibilities) +1.5 Fully correct list +3.5 Some identification of cases within the list +3.5 Complete justification of exhaustiveness EECS 203 Page 20 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Common Mistakes A common mistake was failing to account for the last edge restriction, and simply walking around the cycle (e.g. clockwise) assigning colors. For example, this might result in (3 colors for Node #1) × (2 colors for Node #2) × (2 colors for Node #4) × (2 colors for Node #3) = 24. This correctly accounts for the edges (1, 2), (2, 4), and (4, 3), but does not consider the edge (1, 3), thus overcounting. Such solutions generally received 6/10 (second rubric). Some solutions correctly counted the cases but then applied the division rule to “account for” different orientations of the cycle. This might be the correct strategy if the vertices were indistinguishable, but in this problem we actually do consider different orientations to be distinct, because the vertices are labeled. Such solutions received a maximum 8.5/10 (incorrectly combining terms). Some students attempted to solve the problem by brute-force enumeration of the possible colorings. These solutions, even when they correctly listed the 18 valid outcomes, generally did not fully justify why this was an exhaustive list. Maximum 3/10 for a correct list of outcomes with no justification. Many solutions by cases included an extra factor of 2. These correctly counted 3 choices for vertex 1 and 2 choices each for vertices 2 and 3, and then noted that the number of options for vertex 4 depends on the outcomes of the previous choices (whether vertex 2 matches vertex 3). However, students overlooked that once we split in cases by the color of vertex 3, we have to take another look at the previous steps: to arrive at the correct answer, we should no longer multiply by 2 to count the possibilities for vertex 3, because that’s already baked into the case breakdown. Maximum typically 7/10. Some solutions attempted to compensate for overcounting at the end by multiplying their result by 4, 4!, etc. For example, to account for rotations of the cycle or choice of the first node. Since the nodes are distinguishable, this is not necessary. Maximum 8.5/10 (incorrectly combines terms). By similar reasoning to the previous item,
some solutions included the choice of the node to look at first, so multiplied by 41 when counting. This typically leads to overcounting, because the temporal order of the coloring doesn’t actually appear in the final outcome. Maximum typically 7/10 (incorrect computation of cases). It was common to misuse “WLOG,” for example to introduce cases. We didn’t automatically deduct points for this if the rest of the reasoning was sound. EECS 203 Page 21 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 13: Parking Tickets (10 points) Ava drives to North Campus every day. She parks in the Orange Lot if there is space, and in the Blue Lot otherwise. The probability that the Orange Lot is full is always 14. If she parks in the Orange Lot, the probability that she gets a parking ticket is 19 , but if she parks in the Blue Lot, the probability that she gets a parking ticket is 23. Remember to justify your answers. (a) On any given day, what is the probability that she gets a parking ticket? Final Answer: (b) Suppose she starts driving to North Campus on day 1. On which day does she expect to get her first parking ticket? Final Answer: (c) The Fall 2023 semester is 84 days long. What is the expected number of parking tickets that Ava will get throughout the whole semester? Final Answer: EECS 203 Page 22 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Solution Let B denote that Ava parks in the Blue lot and O denote that Ava parks in the Orange lot. Note that O = B. Let T denote that Ava gets a parking ticket. From the problem, we have that: P (O) = 1 − 41 = 43 P (B) = 14 P (T |O) = 19 P (T |B) = 23 (a) Law of Total Probability Since parking in the blue and orange lots are disjoint events, we use the law of total probability to find the probability that Ava gets a ticket: P (T ) = P (T |O)P (O) + P (T |B)P (B) = 19 · 34 + 23 · 14 = 14 (b) Geometric Distribution Based on the probability from (a), we see that the act of Ava getting her first ticket follows a geometric distribution with p = 41. The expected value can then be found by using the geometric distribution formula: 1 E(X) = P (T ) = 14 = 4 Thus, Ava expects to get her first parking ticket on the 4th day. (c) Binomial Distribution Now that we have a fixed number of days, the number of tickets Ava receives follows a binomial distribution with p = 14 and n = 84. We can then use this distribution to find the expected number of tickets across this time period: E(number tickets) = n · P (T ) = 84 · 14 = 21 tickets Tree method for part (a) Part (a) can also be solved with the assistance of the tree method. We can interpret the given probabilities with the following tree. Then P (T ) = P (O ∩ T ) + P (B ∩ T ) = 1 12 + 16 = 41. EECS 203 Page 23 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Grading Guidelines [10 points] Part (a) : 4 points +1 Attempts to use law of total probability +1.5 Correct expression of the law of total probability +1.5 Plugs in correct values for probabilities Part (b) : 3 points +1 Correct answer based on their probability from (a) +1 Justification: Recognizes geometric distribution +1 Justification: Applies expected value formula for geometric distribution Part (c) : 3 points +1 Correct answer based on their probability from (a) +1 Justification: Recognizes binomial distribution +1 Justification: Applies expected value formula for binomial distribution -0.25 Mistakenly uses P (O) = 14 rather than P (O) = 3 4 -0.25 Simplification error (any part) Common Mistakes Justifying the answer to part (b) using a binomial distribution. For example, saying that the expected number of parking tickets over 4 days is 4 · P (T ) = 4 · 41 = 1. This is not the same as saying that she expects to get her first parking ticket on the 4th day. Misinterpreting “the probability that the Orange Lot is full is always 14 ” as that the probability of Ava parking in the Orange Lot is 41. If the Orange Lot is full, then Ava does not park in the Orange Lot. Thus, the correct probability of Ava parking in the Orange Lot is 1 − 41 = 34. EECS 203 Page 24 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 14: Happy Meals (10 points) Congratulations! McDonald’s is giving you 10 free Happy Meals. In each Happy Meal, one of the six following toys appear with equal probability: Mickey Mouse, Minnie Mouse, Donald Duck, Daisy Duck, Goofy, and Pluto. Remember to justify your answers. Note: If you can’t solve an earlier part, you can still get credit for later parts by phrasing your answer in terms of the earlier part. For example, in Part (c), you could say “let a be the answer to Part (a) and let b be the answer to Part (b),” and then write your answer to Part (c) in terms of a and/or b. (a) What is the probability that you get at least one Mickey Mouse toy? Final Answer: (b) Eric, a big Disney fan, wants a Mickey Mouse toy. If you get one, he will pay you $3 for it (he will only buy 1, though). How much do you expect to earn? Final Answer: (c) Now suppose instead that Eric is willing to buy one of each type of toy you have. He will pay you $3 for each distinct toy that appears in your Happy Meals. For example, if you get 4 Donald Ducks, 2 Goofys, and 4 Plutos, he will pay you $9, buying 3 total toys from you. What is the expected value of your earnings? Final Answer: EECS 203 Page 25 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Solution (a) Let M be a random variable that represents how many Mickey Mouse toys I get. Note that for any given Happy Meal, there is a 5/6 probability of not getting a Mickey Mouse toy. Using the Complement and Product Rules, P (M ≥ 1) = 1 − P (M = 0) = 1 − (5/6)10. (b) Let D be the number of dollars I earn. Therefore, E(D) = Σs∈S p(s) · D(s) = 0 · (5/6)10 + 3 · (1 − (5/6)10 ) = 3(1 − (5/6)10 ). This can also be written as 3a, where a is the answer to Part (a). (c) Let D be the number of dollars I earn. Number each type of toy 1 through 6. Let Di be the random variable that represents the number of dollars I earn from toy i. Using Linearity of Expectation and the fact that each toy has an equal probability of being received by me, E(D) = E(D1 + D2 + D3 + D4 + D5 + D6 ) = E(D1 ) + E(D2 ) + E(D3 ) + E(D4 ) + E(D5 ) + E(D6 ) = 6E(D1 ) = 6(3(1 − (5/6)10 )). This can also be written as 18a, 6 · 3a, or 6b, where a is the answer to Part (a) and b is the answer to Part (b). Alternate Solution: We also accepted the |E|/|S| solution for part A, which should have evaluated to (610 − 510 )/610. The sample space is 610 , which represents selecting which of the 6 toys you get for each of the 10 toys you are receiving. The event E removes all instances in which there are no Mickeys, or 510 options from the sample space. Grading Guidelines [10 points] Part (a) : 4 points +1 Correctly computed probability of getting zero Mickey Mouse toys (p=5/6) +1.5 Raised p to the 10th power +1.5 Computed 1 - previously computed probability of getting 0 Mickey Mouses as final answer Part (b) : 2 points +2 Correctly multiplies (a)’s answer by 3 Part (c) : 4 points +1.5 Justifies solution with linearity of expectation +1 Uses answer from part (a) or (b) +1.5 Implicitly or explicitly multiplies by correct factor of 6 EECS 203 Page 26 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Common Mistakes Not justifying the use of linearity of expectation in part c. Making an argument such as “It is more likely than not that you will get one Mickey Mouse toy. Thus you expect to get a toy, and expect to get three dollars”. This possibly intuitive notion of expectation is not the mathematical meaning of expectation. (Students making this mistake often chose 3 as the answer to part b and/or 18 as the answer to part c). Part c. Attempting to calculate the expectation directly without using linearity of expectation. This is too unwieldy, because the events of getting at least one of each type of toy are not independent. Fortunately, linearity of expectation holds even for dependent events. Attempting to use formulas for binomial or geometric random variables. Part a. Computing the probability of getting exactly 1 Mickey Mouse toy, or similarly, no Mickey Mouse toys. EECS 203 Page 27 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 15: Preeti’s Coins (10 points) Preeti has 5 coins, two of which are double-headed, two are double-tailed, and one is a standard coin (one side is heads, one side is tails). Notes: For each part, write your answer as a single, fully-simplified number. Each part of this question builds on the previous parts. Remember to justify your answers. (a) She shuts her eyes, picks a coin at random, and tosses it. What is the probability that the lower face of the coin is a head? Final Answer: (b) She opens her eyes and sees that the coin is showing heads. What is the probability that the lower face is a head, i.e., that the coin is double-headed? Final Answer: (c) She shuts her eyes again, and tosses the same coin again. What is the probability that the lower face is a head? Final Answer: (d) She opens her eyes again and sees that the coin is showing heads. What is the probability that the lower face is a head, i.e., that the coin is double-headed? Final Answer: EECS 203 Page 28 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Solution Let DH refer to double-headed coin, DT refer to double-tailed coin, and S refer to stan- dard coin. Further, let H refer to getting a Heads on a flip (by symmetry, this will be the same whether seeking heads face down or heads face up, so we will actually use the two interchangeably) P(DH) = 2/5 P(DT) = 2/5 P(S) = 1/5 a) Trying to find P(H). Using the law of total probability, P (H) = P (H|DH) · P (DH) + P (H|DT ) · P (DT ) + P (H|S) · P (S). This gives us P (H) = 1 · 2/5 + 0 · 2/5 + 1/2 · 1/5 = 2/5 + 0 + 1/10 = 1/2 b) Trying to find P(DH|H). Using Bayes Theorem, we get P (DH|H) = P (H|DH)·P P (H) (DH) = 1·2/5 1/2 = 4/5. For the next two parts, we are using the same coin, so the probabilities that we flip a head or tails are changed based on what we know from part (b). These probabilities are updated to: P(DH) = 4/5 P(DT) = 0 (It’s impossible to flip a head using a double-tailed coin) P(S) = 1−4/5 = 1/5 We will focus on using these probabilities to solve the remaining parts and ignore any probabilites that we found in parts (a) and (b) c) Trying to find the new P(H). Similar to part (a), P (H) = P (H|DH) · P (DH) + P (H|DT ) · P (DT ) + P (H|S) · P (S). This gives us P (H) = 1 · 4/5 + 0 · 0 + 1/2 · 1/5 = 4/5 + 1/10 = 9/10. d) Trying to find P(DH|H). Similar to part (b), we will use Bayes Theorem to solve this. P (DH|H) = P (H|DH)·P P (H) (DH) = 1·4/5 9/10 = 8/9 Alternate Solution a) There are 5 coin sides that are heads and 5 coin sides that are tails. Heads and tails are equally likely (by symmetry), and the probability that the lower face is a head is 1/2. b) Since Preeti sees that the coin is showing heads, she is either seeing one of the 4 sides from the double-headed coins or the 1 heads side from the normal coin. In the first 4 cases, the bottom side will be a heads, while in the 5th, it will be a tails. Thus, the probability that the lower face is a head is 4/5. c) Since Preeti is repeating the experiment, the 5 possible outcomes become 10 (5 that stay the same way and 5 that result in the coin being on the other side). 8 of these outcomes are from double-headed coins, and 2 of these are from standard coins. All 8 outcomes with double-headed coins are guaranteed to have heads on the bottom, while EECS 203 Page 29 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide a standard coin only has one side with a head. Thus, the probability that the lower face is a head is 9/10. d) Since she sees that the coin is showing heads, there are now 9 total outcomes (one outcome is eliminated). As stated in part c, 8 of these outcomes come from double-headed coins. Thus, the probability that the lower face is a head is 8/9. Grading Guidelines [10 points] Part (a) : 2.5 points +1 Correct solution +1.5 Correct justification Part (b) : 2.5 points +1 Correct solution in terms of previous parts +1.5 Correct justification Part (c) : 2.5 points +1 Correct solution in terms of previous parts +1.5 Correct justification Part (d) : 2.5 points +1 Correct solution in terms of previous parts +1.5 Correct justification (must be different from part b for partial credit) Common Mistakes For part b, counting the number of coins with heads rather than the number of heads out of the total number of faces possible. If you only count coins, you don’t consider that it is more likely for a double-headed coin to show a head than a standard coin. This approach gives you 3 total coins to choose from, 2 of which are double-headed, resulting in a probability of 2/3. For part(s) c and/or d not viewing b as providing new information i.e. not updating the probability of the coin being double heads or falling heads down. In part c, approaching the problem as a series of sequential events rather than bayes using the updated probability from part b EECS 203 Page 30 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Problem 16: Brad is Blessing (10 points) Brad is U of M’s favorite dog and he spreads smiles by doing 1 of his favorite 4 activities every day: Dog therapy, Celebrity photo op, Fetching tennis balls, or Resting He has two restrictions: He will never Rest 2 days in a row. He always plays Fetch the day after a Celebrity photo op. (a) Find a recurrence relation representing the number of ways Brad can spend n days. Recurrence Relation: Justify your answer by showing your work below (b) Find the initial conditions for your recurrence relation in part (a). For full credit, you must provide the fewest initial conditions possible to satisfy your recurrence. List your initial conditions below. Show your work. Solution Recurrence: an = 2an−1 + 3an−2 + an−3 Base Cases: a0 = 1, a1 = 3, a2 = 9 Forward solution: On day 1, Brad can perform any of the 4 actions. Case 1: Dog Therapy There are no further requirements, so on day 2, he can again do anything. This means the number of ways to select activities for the remaining n − 1 days is an−1. EECS 203 Page 31 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide Case 2: Fetch Similarly, there are no further requirements, so there are an−1 ways to select the remaining days. Case 3: Celebrity Photo Op In this case, Brad will play fetch on day 2. After that, though, we are back to being able to do anything, so there are an−2 ways to select for the remaining n − 2 days. Case 4: Rest In this case, Brad will not be able rest on day 2, so we can’t just use use an−1. Instead, we need subcases for the other options: Case 4a: Rest, Dog Therapy. an−2 Case 4b: Rest, Fetch. an−2 Case 4c: Rest, Celebrity Photo Op, Fetch. an−3 For these subcases, reference the corresponding case above. Each case is a separate option, so we add them together and combine like terms to get the final reccurence relation: an = 2an−1 + 3an−2 + an−3 Backward solution: On day n, Brad cannot do a celebrity photo opt as he would have to fetch the follow- ing day, but there is no following day. However, he can perform any of the remaining activities. It is noteworthy that due to the special case that a sequence cannot end on a celebrity photo opt, we will not be working back to an unconstrained state but rather, an identical state compared to day n. In other words we will work backwards, until he performed dog therapy, played fetch, or rested on the previous day. Case 1: Dog Therapy There are no restrictions on dog therapy, therefore on the previous day, he could’ve performed dog therapy, played fetch, or rested (and not celebrity photo opt as it needs to be followed by fetch). We have worked back to our initial conditions for day n − 1 and therefore this case produces an−1. Case 2: Fetch This case is identical to dog therapy with the notable exception that a celebrity photo opt could’ve also happened on day n − 1. However, this couldn’t have been a terminal state of a previous sequence so we must reason about the day before it. Case 2a: Day n − 1 Brad could’ve performed dog therapy, played fetch, or rested on the previous day identically to our terminal state, an−1. Case 2b: Day n − 1 Brad hosted a celebrity photo opt. Previous to that day, on day n − 2, he could’ve performed dog therapy, played fetch, or rested. Therefore this subcase yields an−2. Case 3: Rest In this case, Brad will not be able to do a celebrity photo opt or rest on the previous EECS 203 Page 32 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide days. This leaves dog therapy and fetch. Case 3a: Day n − 1 Brad performed dog therapy. This case is identical to Case 1, how- ever, this case works backwards for day n − 1 instead of day n. Therefore we get an−2 for this subcase. Case 3b. Day n − 1 Brad played fetch. This case mirrors that of case 2 but again, we start from day n − 1 instead of day n. Therefore we get an−2 + an−3 from this subcase. For those that prefer a visual solution: Exams/Exam 2/images/Exam2_Question16_VisualSol.jpg Each case is a separate option, so we add them together and combine like terms to get the final recurrence relation: an = 2an−1 + 3an−2 + an−3 Part (b) Our recurrence goes back to an−3 , so we must have 3 initial conditions. a0 = 1 because there is 1 way to do 0 activities across 0 days. a1 = 3 because Brad can fetch, rest, or do dog therapy the first day. However, he cannot do a celebrity photo op because that would violate the restriction that it must be followed by fetch. For a3 , we can count using cases based on the first activity. If Brad played fetch or did dog therapy, he can do any of the activities on day 2 besides celebrity photo op for the same reason as above, accounting for 6 total possible combinations. If Brad rested on day 1, he cannot rest on day 2 but can do fetch or dog therapy, accounting for 2 possible combinations. We also need to consider the case where Brad did celebrity photo op on day 1 and fetch on day 2. This gives us a2 = 6 + 1 + 2 = 9. Only 3 base cases necessary, but if starting at 1, then a3 = 28 Grading Guidelines [10 points] Part a (Working Forwards): +1 split into correct cases based on approach +1 correct term for Dog Therapy case +1 correct term for Fetch case +1 correct term for Celebrity Photo Op case +0.5 splits Rest case into subcases +1 correct term for Dog Therapy and Fetch subcase +1 correct term for Celebrity Photo Op subcase +1 Adds cases together to get recurrence relation Part a (Working Backwards): +1 split into correct cases based on approach EECS 203 Page 33 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide +1 correct term for Dog Therapy case +1.5 correct term for Fetch case +0.5 splits Rest case into subcases +1 correct term for Dog Therapy subcase +1.5 correct term for Fetch subcase +1 Adds cases together to get recurrence relation Part b: +1 correct number of initial conditions (based on final recurrence relation) +1.5 correct values for initial conditions (-0.5 for each incorrect) Common Mistakes Going backwards and considering the option of ending on a celebrity photo op. If Brad always plays fetch the day after a photo op, he cannot have a photo op on the last day, else he will not be able to play fetch the day after. These solutions were not awarded the ”split into correct cases” rubric item for going backwards. There was therefore no viable solution for this problem if one considers the possibility of a celeb photo op on day n. Stemming from the previous mistake, many had the initial conditions of a0 = 1, a1 = 4, and a2 = 12. Again, a celebrity photo op cannot be the last activity done by Brad, which eliminates one option from a1 and three options from a2. Associating Brad fetching as only possible after a celebrity photo op. Brad’s option to fetch is not restricted, so it can be done at any time. This led to an an−1 term missing and an an−2 term missing within the context of resting. Going forwards and backwards at the same time. (i.e. stating that the solution is backwards and forward solving) Stating the sequence of [rest → photo op → fetch] (forwards)/ [photo op → fetch → rest] (backwards) at an−2 , when it should be an−3 Giving unnecessary coefficients to each particular case (i.e. considering the ”dog therapy” case to be associated with the term 3an−1 instead of an−1 ) Including more base cases than the minimum needed (i.e. if the recurrence went as far back as an−3 , including a0 , a1 , a2 , and a3 EECS 203 Page 34 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide This is a space for scratch work. DO NOT DETACH THIS PAPER FROM YOUR EXAM. EECS 203 Page 35 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide This is a space for scratch work. DO NOT DETACH THIS PAPER FROM YOUR EXAM. EECS 203 Page 36 of 37 PRACTICE Exam 1, Fall 2024  Fall 2024 PRACTICE Exam 1 Solutions Guide This is a space for scratch work. DO NOT DETACH THIS PAPER FROM YOUR EXAM. EECS 203 Page 37 of 37 PRACTICE Exam 1, Fall 2024