#
CMU 15-110: Principles of Computing

Unit 1: Optional/Advanced Topics

**The 110 Card Trick**- Use red (or black) cards from Ace through Ten (no face cards).
- Shuffle and choose one. Keep it hidden.
- Quickly show all other cards and identify the value (not suit) of the hidden card. Magic!

**The Fitch Cheney Card Trick**- Select 5 cards at random.
- Flip one over. Keep it hidden.
- Place the other 4 face up.
- Magician's Assistant identifies the face-down card!.

**Two's Complement****Python Bits-and-Bytes Functions**- bin(n), oct(n), hex(n)
- int(s, base)
- '%o'%n, '%x'%n
def rgbString(red, green, blue): return '#%02x%02x%02x' % (red, green, blue)

**How to Draw a Star**# generalized drawStar function from tkinter import * import math def drawStar(canvas, sides, cx, cy, R, innerR=None, color='black'): points = [ ] theta = math.pi/2 dtheta = 2*math.pi/sides if (innerR == None): # set r*math.sin(theta + dtheta/2) = R*math.sin(theta + dtheta) innerR = R*math.sin(theta + dtheta)/math.sin(theta + dtheta/2) for i in range(sides): points.append((cx + R*math.cos(theta), cy - R*math.sin(theta))) theta += dtheta/2 points.append((cx + innerR*math.cos(theta), cy - innerR*math.sin(theta))) theta += dtheta/2 canvas.create_polygon(points, fill=color) def draw(canvas, width, height): drawStar(canvas, 5, 100, 100, 80, color='blue') drawStar(canvas, 14, 200, 250, 100, color='red') drawStar(canvas, 6, 200, 250, 40, color='black') drawStar(canvas, 14, 400, 150, 100, innerR=20, color='lime') def runDrawing(width, height): root = Tk() canvas = Canvas(root, width=width, height=height) canvas.pack() draw(canvas, width, height) root.mainloop() print('bye!') runDrawing(500, 350)**Better N-Person Coin Flip**import random def nPersonCoinToss(people, coins): tosses = 0 coinsPerPerson = (2**coins) // people winner = -1 while winner == -1: outcome = 0 for coin in range(coins): outcome = 2*outcome + random.randint(0, 1) tosses += 1 if (outcome < people * coinsPerPerson): winner = outcome // coinsPerPerson return (winner, tosses) def expectedTosses(people, coins, trials=10**4): totalTosses = 0 for trial in range(trials): winner, tosses = nPersonCoinToss(people, coins) totalTosses += tosses return totalTosses / trials print(expectedTosses(5, 3)) print(expectedTosses(5, 4))**The Missing Half-Pair Trick**- Make a list of
**pairs**of positive integers. - Randomly remove one value.
- Shuffle the list.
- Then we quickly identify the removed value. Woohoo!
- Python example:
# The Missing Half-Pair Trick def findMissingHalfPairTrick(L): answer = 0 for value in L: answer ^= value print('The missing value is:', answer) findMissingHalfPairTrick([ 2, 3, 2, 7, 5, 3, 5]) input('Press enter to do the trick on a larger list...') findMissingHalfPairTrick([ 0, 10, 16, 5, 47, 9, 10, 23, 8, 34, 47, 15, 13, 6, 24, 39, 30, 9, 42, 33, 6, 1, 38, 45, 48, 26, 13, 25, 7, 16, 12, 4, 2, 19, 31, 2, 49, 12, 11, 36, 20, 38, 21, 33, 32, 35, 42, 44, 37, 28, 49, 27, 15, 48, 29, 46, 22, 18, 0, 31, 36, 40, 20, 46, 37, 27, 23, 18, 4, 21, 24, 7, 22, 3, 26, 45, 29, 39, 17, 19, 41, 40, 43, 35, 41, 5, 30, 14, 32, 25, 34, 44, 14, 1, 11, 43, 8, 3, 17])

- Make a list of