Have we been here before?

Algorithms + Loops

Have we been here before?

Algorithms + Loops

Where're the algorithms here?

Where're the loops here?

Have we been here before?

Algorithms + Loops

algorithm ~ step-by-step instruction(s)

loop ~ repeated action

Have we been here before?

Algorithms + Loops

most famous infinite loop?

loop ~ repeated action

scratch

scratch

Infinite loop?

HMC's "awesome things" competition

Infinite loop?

Computer Science

​

is applying algorithms…

​

to data…

​

in loops!

Data = information

Data: big example

Google Glass

100 years of HD: 60,000,000 GB

= 60 Petabytes

video: Google glass

C:\Users\Owner\Desktop\to_sort_more_recent\desktop_to_sort\desktop_to_sort_fall_15_in_pusd_workshop\WKauaiDay2

Data = information

There's lots of it to work with!

Data: the big picture

Data: a big example

Google Glass concerns

5/16/13

Is Google Glass dead or hibernating?

To work with data, it is always encoded: converted into a specific form by a set of rules.

​

Later, it can be decoded: changed back into its original form.

CS Data: encoding and decoding

To work with data, it is always encoded: converted into a specific form by a set of rules.

​

Later, it can be decoded: changed back into its original form.

CS Data: encoding and decoding

This is the essence of CS:

communication!

Yesterday we noted two things computers do:

(1) process data (arithmetic) (2) store/retrieve data

Amazingly, this is all that computers do!

Is this all that computers do?

(1) process data (arithmetic) (2) store/retrieve data

Let's see… Try listing some things we use computers for…

Is this all that computers do?

Which is the LARGER subset?

Data: it's what computers do!

And this is the vast majority of computer work!

We noted two things computers do:

(1) process data (arithmetic) (2) store/retrieve data

Rather than computers, they should be called datadogs.

One method of encoding a sentence is by having every letter correspond to a number.

​

​

​

​

For example:

​

AND 1 - 14 - 4

​

​

BUG .

​

​

19 - 09 - 07 - 14

Decoded data

Encoded data

Encoding + Decoding!

One method of encoding a sentence is by having every letter correspond to a number.

​

​

​

​

For example:

​

AND 1 - 14 - 4

​

​

BUG 2 – 21 - 7

​

​

SIGN 19 - 09 - 07 - 14

Decoded data

Encoded data

Encoding + Decoding!

Where's the algorithm here?

Where's the loop here?

One method of encoding a sentence is by having every letter correspond to a number.

​

​

​

​

For example:

​

AND 1 - 14 - 4

​

​

BUG 2 – 21 - 7

​

​

SIGN 19 - 09 - 07 - 14

Decoded data

Encoded data

Encoding + Decoding!

Algorithm

Loop

Loop output

Or, we could shift every letter by one spot

​

A B, B C, C D, .....

​

​

For example:

ZOO APP

​

END

​

​

NVEE

Decoded data

Encoded data

Encoding + Decoding!

Where's the algorithm here?

Where's the loop here?

Or, we could shift every letter by one spot

​

A B, B C, C D, .....

​

​

For example:

ZOO APP

​

END FOE

​

​

MUDD NVEE

Decoded data

Encoded data

Encoding + Decoding!

Algorithm

Loop

Loop output

Another encoding algorithm

Morse code encodes letters as dots and dashes

short sound: "dit"

long sound: "dah"

R

How does this chart represent Morse code?

What is the letter A in Morse code? What about the letter

?

Another encoding algorithm

Morse code encodes letters as dots and dashes

What is the encoding of SOS in Morse code? How about FOG?

short sound: "dit"

long sound: "dah"

orange = dash

white = dot

What is this word?

Encoding + Decoding

Challenges

The following slides contain encoded words.

• Find the rules or pattern for each one!
• This is the Algorithm
• Decode each phrase: This is the Loop

​

For some, you will encode, instead of decode.

• We will provide one example.
• Then, you'll create your own encoding…

​

Decoding = Algorithm + Loop

�25-15-21 19-15-12-22-5-4 20-8-5 6-9-18-19-20 15-14-5

Every letter corresponds to a number.

​

A = 1, B = 2, C = 3, ...

​

See the table below:

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

�KVTU LFFQ TXJNNJOH

Every letter is shifted by one.

• A = B
• B = C
• C = D, ...

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

�REVELC SI SECNETNES GNISREVER

(Use this space to work it out)

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

�SENTENCE WIT MISSIN LETTER AR CONFUSIN

(Use this space to work it out)

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

�UOY ERA YAWFLAH ENOD

(Use this space to work it out)

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

�VEREOYEN OLEVS OCPMTURE CSEICNE

(Use this space to work it out)

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

�VOWOLS ORO OMPORTONT ON SONTONCOS

Every vowel is now an “O” !

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

�IS IT CATS RAINING DOGS AND

(Use this space to work it out)

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

You will use these Morse Code rules to decode the next two secret messages.

Morse Code

Another algorithm ~ morse code

Morse code encodes letters as dots and dashes

orange = dash

white = dot

Morse Code

_ _ _ _ _ . _ . . . . .

_ . _ . _ _ _ _ . . . . . . . .

_ . _ . _ _ _ _ _ _ . _ . .

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

�Morse Code

_ . _ . _ _ _ _ . _ _ . . _ .

. _ _ . . _ . _ . . . _ _ . .

_ _ _ _ . . . . _ . _ _

_ _ _ . . _ . . _ . . . _ .

. . . . . . . . . . _ . .

(Use this space to work it out)

​

Encoded Sentence:

Algorithm

Loop to decode

Optional!

��PUPPIES ARE CUTE

Pig Latin

• If a word begins with a consonant:
• the consonant is moved to the end
• and an “ay” is added.
• If not:
• only “ay” is added.

Note: This time you are encoding the sentence.

​

Algorithm

Loop to ENCODE

Decoded sentence

Conditionals!

�

Now, invent your own code. Write your algorithm here:

Next, write your encoded secret message here:

​

​

​

​

​

Then, put it on the top of the next page + TRADE!

Algorithm

Loop to Encode:

Original (decoded) sentence

something not too difficult…

We'll use the board…

�

(Use this space to work it out)

(Use this space to work it out)

​

Algorithm

… from the previous page

Encoded Sentence:

Loop to Decode

Trade this page with another team and try to decode each other's sentences!

Scratch coding challenges…

The "digital age" ...

For computers, all data is ultimately represented as a set of numbers.

​

With binary, all numbers can be represented as a series 1's and 0's.

Binary is just another code!

0

1

2

3

4

5

6

7

8

9

10

…

decimal

Binary is just another code!

000

001

010

011

​

101

110

111

0

1

2

3

4

5

6

7

8

9

10

…

decimal

binary

Consider this much spam:

​

Why do we use 37 to encode this amount?

The 7 means "seven ones"

​

The 3 means "three tens"

​

Together, they represent the total amount (what we call thirty-seven)

3 7

3*10

7*1

tens

ones

37

Our numbers...

Decimal is based on the number 10.

ones

tens

hun- dreds

4 3 7

How is each column value getting larger?

In binary, the columns increase x 2

In decimal, the columns increase x 10

3 7

tens

ones

1 0

twos

ones

That's the difference!

in binary

In binary, the columns increase x 2

In decimal, the columns increase x 10

3 7

tens

ones

1 0

twos

ones

That's the difference!

in binary

2

ones

in decimal

=

Computers' numbers

Binary is based on the number 2.

​

​

ones

twos

fours

1 0 1 0

How is each column value getting larger?

What should this column value be?

Decoding binary decimal

Suppose the computer holds this binary number:

​

​

ones

twos

fours

1 1 0 1

eights

Let's decode it into decimal:

Practice

From binary to decimal:

​

​

From decimal to binary:

​

​

101

​

​

1011

​

​

10000

​

101010

​

Binary

Decimal

1

2

4

14

​

33

​

1

2

4

8

16

32

Try these!

From binary to decimal:

​

​

From decimal to binary:

​

​

1001

​

​

110

​

​

11010

​

10101

​

3

​

14

​

25

​

52

​

Binary

Decimal

Acting out in binary…

We need 110 volunteers...

Don't worry -- you'll only have bit parts in this.

Acting out in binary…

(1) Challenge the class!

have the "bits" create any number and the class has to figure out what it is

(2) Challenge the bits!

have the class suggest a number and challenge the "bits" to create it in binary

(3) Patterns in counting

have the cards count up + down and have the class find the patterns

(4) Even / Odd / More!

have everyone determine patterns in binary #s

but why do computers use binary… ?

How many different symbols can occupy each digit location in a number?

37

The problem is the number of digits!

How many different symbols can occupy each digit location in a number?

37

There can be ten different digits!

07 17 27 37 47 57 67 77 87 97

The problem is the number of digits!

A computer has to differentiate physically among all its possibilities.

Ten symbols is too many!

ten symbols ~ ten different voltages

This is too difficult to replicate billions of times

What digits are these?

engineering!

0

1

2

3

4

5

6

7

8

9

Ouch!

A computer has to differentiate physically among all its possibilities.

Easy!

Two symbols is easier!

What digits are these?

two symbols ~ two different voltages

ten symbols ~ ten different voltages

0

1

2

3

4

5

6

7

8

9

0

1

The "digital age" ...

​

For computers, all data is ultimately represented as 0s and 1s, in binary.

Could you encode a lego tower in binary... ?

​

Then, have someone else decode it back into the same Lego tower?

Imagine – Decompose – Specify – Binarize – Execute – Compare – Debug!

Codes and Data

Lego towers

… in binary

Secret Fortress Construction Challenge

64

You should have two identical LEGO block kits.

Set the extra kit aside, and use one kit to build a LEGO fortress:

​

1. Find a secluded spot to build your secret fortress. Don’t let anyone else see it!
2. Place your Lego baseplate on top of the template on page 2. Note the x and y axes are 0, as usual.
3. [First-timer advice] Keep your tower to the lower-left corner, where x and y are 7 or less
4. Write the English instructions for building your tower… (page 3)
5. Create a binary encoding (the legend) for each type and color of your Legos. (page 3)
6. Translate the English instructions to binary instructions for your tower! (page 4)
7. Be sure to copy over the legend, as well!
8. [Optional] Create a single line of 0s and 1s that you will send to the other team.
9. [Optional] Text or email that single line of 0s and 1s to the other team.
10. [Optional] Reassemble the other team's single line of 0s and 1s into binary instructions:
11. Swap! Make sure you have the chart of the other team's binary instructions…
12. Make sure you copy the other team's legend with their binary encoding
13. Convert their binary instructions back to English instructions using the legend.
14. Try to build their secret fortress!
15. When both teams are done, compare the fortresses you’ve created.
16. Were you successful? Why or why not?
17. Debug! If something went wrong, find where it went wrong -- which step of the process was it?!

There are lots of background materials…

(we'll go light on these for now)

Imagine – Decompose – Specify – Binarize – Execute – Compare – Debug!

from ideas to binary – and back

Imagine – Decompose – Specify – Binarize – Execute – Compare – Debug!

Codes and Data

67

68

How could you tell someone how to build this tower – if they could not SEE it!

69

Secret Fortress Base Template

x

y

We definitely need to be able to describe positions of Legos!

70

Your Legend

Fill in the chart below with English and numeric instructions for your fortress.

​

Follow the sample line, which says “put the sample block, which is a red 2x4 block, horizontally, with its bottom left corner at the position given by the x-coordinate 6 and the y-coordinate 4.”

​

Then, fill in the legend to create an encoding for all the bricks you used.

​

For example, a 2x4 block might be represented with 010100, since 010 is 2 in binary, and 100 is 4 in binary.

Chart A. Your team's English Instructions

Let's go!

71

Copy the legend you created on the last page to this page.

​

Then, translate the instructions in Chart A to binary.

​

Converting information into binary allows a computer to store it and communicate it. Computers use an electric signal to represent the 1s and no signal to represent the 0s.

Your Legend

Chart B. Your team's binary Instructions

& convert to binary…

Now, we fill the legend…

72

Copy the legend you created on the last page to this page.

​

Then, translate the instructions in Chart A to binary.

​

Converting information into binary allows a computer to store it and communicate it. Computers use an electric signal to represent the 1s and no signal to represent the 0s.

Your Legend

Chart B. Your team's binary Instructions

My answer…

73

Copy the legend you created on the last page to this page.

​

Then, translate the instructions in Chart A to binary.

​

Converting information into binary allows a computer to store it and communicate it. Computers use an electric signal to represent the 1s and no signal to represent the 0s.

Your Legend

Chart B. Your team's binary Instructions

just the bits!

74

Copy the legend you created on the last page to this page.

​

Then, translate the instructions in Chart A to binary.

​

Converting information into binary allows a computer to store it and communicate it. Computers use an electric signal to represent the 1s and no signal to represent the 0s.

Your Legend

Chart B. Your team's binary Instructions

Differentiating delivery

​

Extra challenge: text the lines of bits

Usual: just swap binary pages (this one)

Simpler: just swap English pages (previous)

- swap bits -

75

Their Legend

Transferring the bits!

Try it!

​

Take a picture of your binary instructions of 0s and 1s

​

Next, send a text or email with the bits of your tower.

​

Then, decode the instructions & build the same tower!

​

Finally, compare the original tower with the new one – and debug any differences!

76

Translate the other team's instructions to English instructions.

Chart D. Other team's English Instructions

Their Legend

Decode…

77

DECODED Fortress!

x

y

See if they match!

DECODED Fortress!

See if they match!

79

Bug tracker…

How many differences were they between the original and DECODED towers?

Find where the differences happened and make a mark for each location of these "bugs"

If you want to actually draw bugs, even better!

Translating from tower to English

Translating from English to binary

Transferring the bits

Translating from binary to English

Translating from English to tower

Secret Fortress Construction Challenge

80

You should have two identical LEGO block kits.

Set the extra kit aside, and use one kit to build a LEGO fortress:

​

1. Find a secluded spot to build your secret fortress. Don’t let anyone else see it!
2. Place your Lego baseplate on top of the template on page 2. Note the x and y axes are 0, as usual.
3. [First-timer advice] Keep your tower to the lower-left corner, where x and y are 7 or less
4. Write the English instructions for building your tower… (page 3)
5. Create a binary encoding (the legend) for each type and color of your Legos. (page 3)
6. Translate the English instructions to binary instructions for your tower! (page 4)
7. Be sure to copy over the legend, as well!
8. [Optional] Create a single line of 0s and 1s that you will send to the other team.
9. [Optional] Text or email that single line of 0s and 1s to the other team.
10. [Optional] Reassemble the other team's single line of 0s and 1s into binary instructions:
11. Swap! Make sure you have the chart of the other team's binary instructions…
12. Make sure you copy the other team's legend with their binary encoding
13. Convert their binary instructions back to English instructions using the legend.
14. Try to build their secret fortress!
15. When both teams are done, compare the fortresses you’ve created.
16. Were you successful? Why or why not?
17. Debug! If something went wrong, find where it went wrong -- which step of the process was it?!

Now, the real thing…

Pairs, pair up!

81

Secret Fortress Base Template

x

y

Don't show the other team your tower!

82

Your Legend

Fill in the chart below with English instructions for your fortress.

​

The sample line is ONLY an example. Don't use that brick!

​

Also, fill in the legend to create an encoding for all the bricks you used.

​

For example, a 2x4 block might be represented with 010100,

since 010 is 2 in binary, and 100 is 4 in binary.

Chart A. Your team's English Instructions

83

Copy the legend from the prior page to this page.

​

Then, translate the instructions in Chart A to binary.

​

Your Legend

Chart B. Your team's binary Instructions

84

Extra -- Transferring the bits!

Try it!

​

Take a picture of your binary instructions of 0s and 1s

​

Next, send a text or email with the bits of your tower.

​

Then, decode the instructions & build the same tower!

​

Finally, compare the original tower with the new one – and debug any differences!

Their Legend

Differentiating delivery:

Spicy: actually text the bits!

Medium: just swap binary pages (images).

Mild: just swap English pages (images)

85

Translate the other team's instructions to English instructions.

​

And… build the tower!

Chart D. Other team's English Instructions

Their Legend

86

DECODED Fortress!

x

y

See if they match!

87

Bug tracker…

How many differences were they between the original and DECODED towers?

Find where the differences happened and make a mark for each location of these "bugs"

If you want to actually draw bugs, even better!

Translating from tower to English

Translating from English to binary

Transferring the bits

Translating from binary to English

Translating from English to tower

Imagine – Decompose – Specify – Binarize – Execute – Compare – Debug!

Codes and Data