High School Presentation Options

(Some of the material here adapted from: http://www.mathmaniacs.org/lessons/02-textcomp/index.html)

Historical Hardware

punch cards, vacuum tubes, paper tape, electronic tape, hard drives
core memory, IC card, microprocessors

Binary Number Fun

• Assuming you're familiar with binary numbers
• How many ways can Cinda go to school? How many different ways are there to create a pizza with 6 toppings?
• Sorting cards in O(log n)
• Number from 0..63
• How many ways can Cinda go to school? (local copy)
       Related to this, how many different ways are there to create a pizza with 6 toppings?
  Binary Numbers magic card trick, color print sheet (MS Word)
  Mind Reader: guessing a number between 1 and 50,000 in 16 guesses
       (binary search) On guess 16 subtract 2^15, etc.
       - Once this is understood (always half the remaining search space), do Cinda's trick of searching for a number between 0 and 63, for each place writing a 0 or 1 as part of the word for Yes (1) or No (0), resulting in a binary number.

How to add Numbers using Logic

Binary Numbers: counting in decimal, counting in binary to 10
Logic gates, truth tables: and, or, xor, not
A sample circuit for automobile buzzer (see example)
Half-Adder: 4 combinations of two inputs
        - then rewrite as a truth table
        - What logic gates give these outputs?
        - The circuit diagram

Encoding Characters in Binary

Why do .mp3's take less space than the original .WAV files?

1. How can we store letters using only 0's and 1's? Do the best you can at decoding the First Code.
   What is the problem? What approaches can we take to solve this?
2. If I give several phone numbers, can you separate them?
        31241394787734915860
   Why? Can we use this approach?
   Now try the simple code worksheet. (We can do better....)
3. See the histogram of letter usage in Alice in Wonderland, and Morse Code.
        "RSTLN E" from Wheel-Of-Fortune
        ETAOIN SHRDLU
   Why are Morse Code letters chosen the way they are? How about telephone area codes?
   This applies to saving space in encoding characters.
4. Problem with original approach: same prefix to characters. A "prefix" code does not have this problem.
   See a wonderful code, which is an example of a Huffman code, using occurance probabilities to optimally assign variable-length codes.
5. This can still be a pain to decode, so we can use a decision tree.
6. Practice using the decision tree to decode a longer message.
   Consider the savings on this message:
   1. How many bits are required to encode the message using the wonderful Huffman Code?
   2. How many bits would have been required using the simple fixed length coding?
   3. What sort of savings do we get?
7. Alice in Wonderland contains exactly 107717 letters.
   1. How many bits are necessary to store the text using the simple coding scheme of 5 bits per letter?
      (Answer: 5 x 107717 = 538585.)
   2. How many bits are necessary to store the text using the Huffman Code?
      (Answer: Multiply each letter frequency by the length of the corresponding codeword, then add up these values, giving the total number of characters. E.g. we know that there are 13572 'e's (subject to rounding error), since 12.6% of the 107717 characters are 'e's.
   3. After doing all this, you should find that Alice in Wonderland can be stored in 456225 bits using the Huffman code.
   4. How much improvement is this? (Answer: (538585-456225)/538585 * 100 = 15.3%)

Random Writer Example

Base generated text on the frequency of known text.

PowerPoint

• CS Dept., Current Job possibilities
• EVL Lab

PedalPlane Video Game