# Counting and chance in Python Indexing, recursion, and the matching and birthday problems, in the CS61A style. ### What would Python display? Indexing *Fill in the blank · en* What would Python display? ```python >>> v = [3, 1, 4, 1, 5, 9] >>> v[1] ``` Your answer: 1 (Accepted absolute error: 0) #### Hints 1. Python numbers positions from 0, not from 1. 2. `v[0]` is `3`. Which entry comes next? #### Reference solution `1`. Python positions start at 0, so `v[1]` is the **second** entry. In R, `v[1]` would be the first entry, `3`. Source: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied ### What would Python display? No recycling *Single choice · en* What happens here? ```python >>> v = [3, 1, 4] >>> v + 3 ``` - [ ] added: `[6, 4, 7]` - [ ] appended: `[3, 1, 4, 3]` - [ ] error: A `TypeError` Your answer: error #### Hints 1. `+` between two lists joins them. Is `3` a list? 2. Python does not repeat a shorter value to fit a longer one. #### Reference solution Python raises `TypeError: can only concatenate list (not "int") to list`. For lists, `+` means concatenation, and it needs a list on both sides. Write `[x + 3 for x in v]` to add 3 to each entry, which gives `[6, 4, 7]`. Source: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied ### Binomial coefficients by recursion *Python · en* Complete `choose(n, k)` **recursively**, using Pascal's rule $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$. Do not use `math.comb` or factorials. Return 0 when $k<0$ or $k>n$. ```python def choose(n, k): """Return the number of ways to choose K items from N, using Pascal's rule. >>> choose(5, 2) 10 """ pass ``` #### Public tests Small case ```pycon >>> choose(5, 2) 10 ``` Middle of a row ```pycon >>> choose(10, 5) 252 ``` Choose none or all ```pycon >>> choose(4, 0) 1 >>> choose(4, 4) 1 ``` Too many ```pycon >>> choose(3, 5) 0 ``` #### Hints 1. There are two base cases: impossible choices, and choosing none or all. 2. If $k$ is 0 or equal to $n$, there is exactly one way. 3. Otherwise, return the sum of two smaller `choose` calls. #### Reference solution ```python def choose(n, k): if k < 0 or k > n: return 0 if k == 0 or k == n: return 1 return choose(n - 1, k - 1) + choose(n - 1, k) ``` The first base case handles impossible requests; the second is the edge of Pascal's triangle. Each recursive call lowers $n$, so the recursion ends. It makes many repeated calls, which is fine for small $n$ and a good reason to meet memoization later. Source: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied ### What would Python display? Adding truth values *Fill in the blank · en* What would Python display? ```python >>> deck = [2, 1, 3, 4] >>> sum([card == position for position, card in enumerate(deck, start=1)]) ``` Your answer: 2 (Accepted absolute error: 0) #### Hints 1. The list inside is `[False, False, True, True]`. 2. In arithmetic, `True` counts as `1` and `False` as `0`. #### Reference solution `2`. Cards 3 and 4 are in their own positions, so the list is `[False, False, True, True]`, and its sum counts the `True` values. Source: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied ### Count the matches *Python · en* Complete `count_fixed_points(deck)`. `deck` lists the cards in the order they are turned over; card $i$ matches when it is turned over $i$th. Return the number of matches. ```python def count_fixed_points(deck): """Return how many cards in DECK sit in their own position. Positions are numbered from 1, like the cards. >>> count_fixed_points([1, 2, 3]) 3 >>> count_fixed_points([2, 1, 3]) 1 """ pass ``` #### Public tests Every card matches ```pycon >>> count_fixed_points([1, 2, 3]) 3 ``` One match ```pycon >>> count_fixed_points([2, 1, 3]) 1 ``` No matches ```pycon >>> count_fixed_points([3, 1, 2]) 0 >>> count_fixed_points([2, 1]) 0 ``` Empty deck ```pycon >>> count_fixed_points([]) 0 ``` #### Hints 1. `enumerate(deck, start=1)` gives each position together with its card. 2. Compare each card with its position, then add up the results. #### Reference solution ```python def count_fixed_points(deck): return sum(card == position for position, card in enumerate(deck, start=1)) ``` Each comparison is `True` or `False`, which `sum` counts as 1 or 0. An empty deck has no matches, so the sum is 0. Source: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied ### How many people are needed? *Python · en* `birthday_match(k, days)` is provided. Complete `people_needed(p, days)`: return the smallest number of people $k\ge1$ for which `birthday_match(k, days)` is at least `p`. This is what R's `qbirthday` computes. Assume $0>> people_needed(0.5) 23 """ pass ``` #### Public tests Even odds ```pycon >>> people_needed(0.5) 23 ``` Ninety percent ```pycon >>> people_needed(0.9) 41 ``` Ninety-nine percent ```pycon >>> people_needed(0.99) 57 ``` A shorter year ```pycon >>> people_needed(0.5, days=2) 2 ``` #### Hints 1. Start with one person and add people until the probability is large enough. 2. A `while` loop fits: keep going while `birthday_match(k, days) < p`. #### Reference solution ```python def people_needed(p, days=365): k = 1 while birthday_match(k, days) < p: k += 1 return k ``` The loop always stops: with `days + 1` people a shared birthday is certain, so the probability reaches 1. Source: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied