CMU 15-110: Principles of Computing
Unit 1: Optional/Advanced Topics

1. 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!


2. 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!.


3. Two's Complement
   • Like 10's Complement, but in Base 2 (binary).
   • How subtraction really works in most computers!
   • Examples in Python and C


4. 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)


5. 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)


6. 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))


7. 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])