2. (30 pts.) Amortized Shuffling Suppose you are playing a card game using a deck of n cards. At the beginning of your turn, you draw a card, and at the end, you put it in the discard pile (assume these are constant-time operations). If the deck is empty when you need to draw a card, you first reshuffle the discard pile to make a new deck; assume shuffling n cards takes sn logn time for some constant s. 1 This isn't a completely made-up runtime. Doing a single shuffle of n cards arguably takes (n) time, and (logn) shuffles of the type usually used by human players are enough to randomize the deck: see Bayer & Diaconis, Trailing the Dovetail Shuffle to its Lair, Annals of Applied Probability 2(2), 1992 (online here; this paper is what led to the popular heuristic that 7 shuffles are enough for a standard 52-card deck). CSE 102, Winter 2021, HW3 1 (a) (10 pts.) What is the asymptotic worst-case time to draw a single card, and what is the amortized time over a long sequence of draws? (b) (20 pts.) Suppose every other card you draw is removed from the game instead of put in the discard pile, so that the total number of cards decreases until none are left (and the game ends). Does this affect the amortized time of drawing a card? Justify your answer. 2. (30 pts.) Amortized Shuffling Suppose you are playing a card game using a deck of n cards. At the beginning of your turn, you draw a card, and at the end, you put it in the discard pile (assume these are constant-time operations). If the deck is empty when you need to draw a card, you first reshuffle the discard pile to make a new deck; assume shuffling n cards takes sn logn time for some constant s. 1 This isn't a completely made-up runtime. Doing a single shuffle of n cards arguably takes (n) time, and (logn) shuffles of the type usually used by human players are enough to randomize the deck: see Bayer & Diaconis, Trailing the Dovetail Shuffle to its Lair, Annals of Applied Probability 2(2), 1992 (online here; this paper is what led to the popular heuristic that 7 shuffles are enough for a standard 52-card deck). CSE 102, Winter 2021, HW3 1 (a) (10 pts.) What is the asymptotic worst-case time to draw a single card, and what is the amortized time over a long sequence of draws? (b) (20 pts.) Suppose every other card you draw is removed from the game instead of put in the discard pile, so that the total number of cards decreases until none are left (and the game ends). Does this affect the amortized time of drawing a card? Justify your