CMU 15-110: Principles of Computing
Data Representation and Algorithms

• What is Data Representation?
• How to store and transmit data
• Digital: using only 0's and 1's (bits) (real!)
• Abstraction: Everything else must be represented with 0's and 1's
• Type: the class or kind of a data value, such as integer (42), string ('hello'), image (...), video (...), etc.
• Data Abstraction Hierarchy: Represent complex types using simpler types
  For example:
  


• Ways to Represent Some Types
• integers
• unsigned (not negative) integers
• binary (base 2)
• word size (and overflow)
• signed (possibly-negative) integers
• simple way: sign-magnitude
• "real" way: Two's complement (see 10's complement in algorithms section below)
• characters
• ascii
• unicode
• strings
• 0-terminated
• length-prefixed
• floats
• simple way: variant of mantissa + exponent (1.02 -> (102, 2))
• "real" way (IEEE 754)
• issue: roundoff error
• colors
• rgb values
• images
• simple way: (dimensions + rgb's)
• "real" ways: png, jpg, gif,...
• everything else!
• lists, 2d lists, audio, video, maps, music, art, math, even ideas, ...
• Big Idea: to store, transmit, or compute over any data, you first must represent it! And then, only using 1's and 0's!

• What is an Algorithm?
• A precise way to solve a problem
• Input (bits) → Computation (precise steps) → Output (bits)
• a "step" is defined by the language and desired level of abstraction
• Pseudocode: an informal English-like code-like language
• Abstraction: all algorithms must be reduced to these basic steps (or primitives)
• Hierarchy: Build complex algorithms out of simpler algorithms (using Top-Down Design)
• Analysis: how correct, how fast, how clear, how general,...?


• Arithmetic
• counting on fingers!
  • in base 1
  • in base 2
• subtraction by addition
  • 10's complement
  • 2's complement
• multiplication
  • standard multiplication (as taught in most schools)
  • lattice multiplication
  • Egyptian multiplication
  • Repeated addition


• Card Tricks
• The Parity Card Trick
  • See here.
• 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!


• Coin Flips
  
• N-Person Coin Flips
  • Note: Try this random coin flipper
• Unfair Coin Flips
• Von Neumann Coin Flip (Note: Manuel Blum lectured on this in class on Friday!)


• Game Playing
  • Nim
  • The 100 Game