Problem Solving and Algorithms
Day 3, Session 1
Welcome back!
We are here
Thank you!
useful ~ on my computer !
"Algorithm" ?
"Algorithm" ?
Algorithms are what computer scientists "do" ...
Algorithm... ?
An algorithm is a step-by-step process for solving problems
enough detail that a even a computer could do it!
not solving just one problem -- but a whole set of problems
Problem-solving processes
Here's a familiar problem.
How would you solve it?
A problem-solving processes
(1) experiment
(2) describe a plan
(3) test the plan (execute it)
(4) reflect/evaluate
A process is much more useful than one solution!
solving one vs. solving many
A problem-solving process
(1) experiment
(2) describe a plan
(3) test the plan (execute it)
(4) reflect / evaluate
A new problem-solving process
What is the path from the ring to the G?
"rook-jumping maze"
A problem-solving process
What is the path?
What is the process?
(1) experiment
(2) describe a plan
(3) test the plan (execute it)
(4) reflect/evaluate
Mazes ~ problem-solving
What is the path from start to finish?
Travel is only allowed along the arrows ~ no u-turns allowed!
No-left-turn maze
How about here?
Travel is only allowed going straight or taking right turns!
No left turns!
"Tilt" maze
Try to "roll" the circle to the star, but it can only roll...
Once you choose a direction, the circle must "roll" that way until it is stopped by a wall!
"Tilt" maze, part 2
Try to "roll" the circle to the star.
However, once you choose a direction, the circle must roll that way until it is stopped by a wall!
Rolling die maze
Try to "roll" a die from start to finish.
At each move, the die's upward side must match the maze square!
"Tilt" maze, part 3
Try to "roll" the circle to the star.
However, once you choose a direction, the circle must roll that way until it is stopped by a wall!
Algorithm... ?
An algorithm is a step-by-step process for solving problems
enough detail that a even a computer could do it!
not solving just one problem -- but a whole set of problems
Let's create an algorithm...
Let's create an algorithm...
(1) ________________
(2) ________________
Below, write an algorithm - a step-by-step process - for making a peanut butter and jelly sandwich.
How to make a PB&J sandwich...
You have...
(3) ________________
(4) ________________
(5) ________________
(6) ________________
(7) ________________
(8) ________________
(9) ________________
(10) ________________
(11) ________________
(12) ________________
Thought experiment: three algorithms
How does Netflix predict how much you'll like a movie/show?
How does your brain know if it's seeing a face? How does it know how far away things are?
How do you put a set of objects in order (sort them)
42
17
25
Thought experiment: three algorithms
How do you put a set of objects in order (sort them)
42
17
25
This seems pretty easy!
Netflix Algorithm
predicting movie ratings
How does Netflix predict how much you'll like a movie/show?
Mary Elise's Ratings:
The Hobbit:
Dexter:
Zach's Ratings:
The Hobbit:
Dexter:
SUGGESTED FOR
VIEWING
Bob Bell, winner of the "Netflix prize"
Napoleon Dynamite =
Batman Begins =
The Netflix Prize
Finding Nemo =
Lord of the Rings =
(I don't know this guy)
??
??
??
??
Some films are difficult to predict… and others are easier!
Bob Bell, winner of the "Netflix prize"
Prediction errors...
(I don't know this guy)
Napoleon Dynamite =
Batman Begins =
Finding Nemo =
Lord of the Rings =
1.22
.75
.67
.42
These scores are the average error (in units of stars) for each film
How does your brain know if it's seeing a face?
And, how does it know how far away things are?
How does your brain know if it's seeing a face?
And, how does it know how far away things are?
We don't fully know!
but it is doing a lot of computing...
Problem-solving patterns
Brick-breaking challenge
The first thing computer scientists do to create an algorithm is explore -- and look for patterns...
Problem-solving patterns
Brick-breaking challenge
Q: How many breaks are needed to fully separate these pieces?
Break it up...
# of breaks
# of pieces
1
2
3
12
B
N
4
Q: How many handshakes do you need in order to greet everyone?
# in group
# of h.shakes needed
You are at a party with a total of 2, 3, 4, 10, or N people (including you)...
Q: How many handshakes are needed so everyone greets everyone?
2
3
10
N
# in group
# of h.shakes needed
2
3
10
N
Take-home message
Understanding problems is the key to solving them -- and it's much more important than solving a particular one!
Computer Science is the science of understanding information-based problems, i.e., those based on data.
could these puzzles work with middle-schoolers?
Sorting and Searching
Day 3, Session 2
"Algorithm"
An algorithm is a process for solving problems.
Simply put, algorithms are what CS is about.
"Algorithm"
An algorithm is a process for solving problems.
The Nine Algorithms/Chapters:
(1) Ideas Computers Use Every Day
(2) Search Engine Indexing: Finding Needles in the World's Biggest Haystack
(3) PageRank: The algorithm that made Google
(4) Public Key Cryptography: Secrets on a Postcard
(5) Error-Correcting Codes: Mistakes That Fix Themselves
(6) Pattern Recognition: Learning from Experience
(7) Data Compression: Something for Nothing
(8) Databases: The Quest for Consistency
(9) Digital Signatures: Who Really Wrote This Software?
(10) What Is Computable?
(11) Conclusion: More Genius at Your Fingertips?
"Algorithm"
An algorithm is a process for solving problems.
The Nine Algorithms/Chapters:
(1) Ideas Computers Use Every Day
(2) Search Engine Indexing: Finding Needles in the World's Biggest Haystack
(3) PageRank: The algorithm that made Google
(4) Public Key Cryptography: Secrets on a Postcard
(5) Error-Correcting Codes: Mistakes That Fix Themselves
(6) Pattern Recognition: Learning from Experience
(7) Data Compression: Something for Nothing
(8) Databases: The Quest for Consistency
(9) Digital Signatures: Who Really Wrote This Software?
(10) What Is Computable?
(11) Conclusion: More Genius at Your Fingertips?
Searching
Sorting
Searching...
Webster's dictionary - in order
Wubster's dictionary - not in order!
Seeking "spam"
What algorithms can we use to find "spam"?
Linear Search (unsorted data)
In the worst-case scenario, how many unsorted words would we have to look at before we get to the right one?
the algorithm
An example of a linear search in Scratch can be found here!
Binary Search (sorted data)
Can we find words faster if they're sorted?
If so, how?!?
Webster's Dictionary
Binary Search (sorted book)
the algorithm
mixplate
Seeking "spam" ...
must be in here some-where
Binary Search (sorted book)
mixplate
wasabi
here some-where
the algorithm
Seeking "spam" ...
Binary Search (sorted book)
mixplate
wasabi
here some-where
soy sauce
the algorithm
Seeking "spam" ...
Binary Search (sorted book)
If our book has 32 words in it, how many do we look at before we definitely find the right one? 64? 1,000,000?
swordfish
the algorithm
Seeking "spam" ...
An example of a binary search in Scratch can be found here!
Linear vs. Binary Search
With a large amount of sorted data, binary search is almost always more efficient.
But how do we get our data sorted?
Comparisons
The basic building-block of sorting is
comparing two items.
Consider these two numbers:
and
Which number is larger?
How can you tell?
110111001100100100010100111110101
110111001100100100010101111110101
Let's sort!
milk
chocolate
sugar
latte
caffeine
coffee
Create 6 cards with these words, one per note...
Let's sort!
Goal: Sort your items (in pairs)!
Note: Computers can compare only two items at a time! The students will help by saying what's smaller/larger...
Then: Sort again, counting the number of pairwise comparisons you make in order to ensure your items are sorted.
Challenge: describe a sorting algorithm that works for all possible cases!
Trial #1 tally
Trial #2 tally
Your sorting algorithms:
Lego Sorting
http://www.youtube.com/watch?v=MtcrEhrt_K0
Watch this sorting algorithm... can you describe how it works?
We've made this same method of sorting in Scratch
Linear vs. Binary Sorting!
How do they compare?
1) "Min Sort"
2) "Merge Sort"
How does this relate to dictionary-searching?
Sorting out sorting
Let's race three sorting algorithms
1) Act out minsort - count our comparisons: _____
2) Act out mergesort - count comparisons: _____
3) Outside, try a parallel sort - count: _____
Which one wins?
Min Sort
"Linear Sorting"
Idea: Search for the smallest element, then the second smallest, and so on...
More detail: Compare pairs of elements to find the smallest. Remove the smallest and place it at the end of the sorted list. Repeat until all elements are in the sorted list.
Merge Sort
"Binary Sorting"
Idea: Split repeatedly, then merge back!
More detail: Split in half repeatedly; when there are only two elements per list, they are easy to sort: just swap if needed!
Then, repeatedly merge two sorted lists by (1) comparing the first elements, and (2) placing the smaller element,
~ until all of the elements are sorted!
Parallel Sorting
Follow the arrows...
At each merge point,
the higher # goes right
the lower # goes left
Which group can sort themselves more quickly?
Is MergeSort for real? Let's see...
Is MergeSort for real? Let's see...
10 piles of 16
5 piles of 32
Is MergeSort for real? Let's see...
5 piles of 32
2 piles of 80
Is MergeSort for real? Let's see...
2 piles of 80
1 pile of 158
158?
Is MergeSort for real? Yes!
2 piles of 80
1 pile of 158
158?
Not sure who these people were....
Mergesort, in dance
look this up to see the many options...
Sorting Activities from
The purpose of computing is insight, not numbers.
Algorithms are how we represent those problem-solving insights.
Lunch!
Scratch for ________
or
Python for ________
Day 3, Session 3
Scratch ~ tool for exploration...
(computation)
Scene ideas:
Shakepeare: Romeo + Juliet
Justin Carvalho: Farewell to Manzanar
Robin Herbig: Name animation
Drawing with Scratch
Another type of problem...
Recognize this game show?
Choose... Reveal... Switch or stay?
Let's Make a Deal...
Let's Make a Deal is in Scratch too!
Let's Make a bigger Deal...
A
B
C
D
E
F
G
1
2
3
4
5
6
7
8
9
10
Let's Make a bigger Deal...
A
B
C
D
E
F
G
1
2
3
4
5
6
7
8
9
10
Let's Make a bigger Deal...
A
B
C
D
E
F
G
1
2
3
4
5
6
7
8
9
10
Let's Make a bigger Deal...
A
B
C
D
E
F
G
1
2
3
4
5
6
7
8
9
10
Scratch ~ tool for exploration...
(computation)
Directing with Scratch
Scene ideas:
Shakepeare: Romeo + Juliet
Justin Carvalho: Farewell to Manzanar
Robin Herbig: Name animation
Drawing with Scratch
Binary activity
Flash cards / math practice
(computation)
Scene ideas:
Shakepeare: Romeo + Juliet
Justin Carvalho: Farewell to Manzanar
Robin Herbig: Name animation
Drawing with Scratch
An Infamous Equation
Algorithmic Scratch
(1) Create a Square
Algorithmic Scratch
(1) Create a Square
Algorithmic Scratch
(2) Create a Triangle
Algorithmic Scratch
(3) Create a Hexagon
Algorithmic Scratch
(4) Create a Square Algorithm
Algorithmic Scratch
(4) Create a Square Algorithm
Algorithmic Scratch
(5) Create a Square Algorithm
with side length as a variable
Algorithmic Scratch
(5) Create a Square Algorithm
with side length as a variable
Algorithmic Scratch
(7) Create a Wall with
Length and Width as
variables
Algorithmic Scratch
(7) Create a Wall with
Length and Width as
variables
Algorithmic Scratch
(8) Create Squares within
Squares
Algorithmic Scratch
(8) Create Squares within
Squares
Algorithmic Scratch
(9) Create Square-spiral,
a.k.a. "squiral"
Algorithmic Scratch
(9) Create Square-spiral,
a.k.a. "squiral"
Algorithmic Scratch
(10) Petal
Algorithmic Scratch
(10) Petal
Algorithmic Scratch
(11) Flower
Algorithmic Scratch
(11) Flower
(3pm today ~ Mike)
Planning for getting to Google...
Tomorrow
Rolling block maze
Try to "roll" a 2x1 block from start to finish.
As you solve the maze, the block may not overlap one of the "wall" squares
oos.moxiecode.com/flash8/rolling_blocks.html
www.hoodamath.com/games/bloxorz.html
Online versions:
Our game: Up, up, and away!
First, let's pair up -- so that each pair has both a teacher and an HMC student...
Our game: Up, up, and away!
(1) Choose a main character...
(something that you want to fly)
(2) Add (four) blocks like these so that you can move around with the arrows:
Our game: Up, up, and away!
(3) Make sure your "hero" can wrap around from right to left:
add other wrapping as you see fit!
Our game: Up, up, and away!
(4) Create a second sprite ~ the goal!
(something you want to reach)
(5) Create a third sprite ~ an "enemy"
(something to avoid)
(6) Have the enemy move continuously:
Our game: Up, up, and away!
(7) When the enemy hits the hero, teleport the hero back to the start:
it's good to start there at the beginning, too
Our game: Up, up, and away!
Now, add at least two of these features:
(a) Add a changing score variable
(b) Have the enemy move randomly
(c) Add more enemies
(d) Add "power-up" sprites that change your hero's size, score, or speed
(e) Add portals that teleport your hero randomly
(f) Have the game end when a timer runs out.
And... at least two of your own ideas... !
Game demonstrations...
...and code reviews
Our game: Fly, fly again...
Use these blocks to write a script that makes it so that if you press the UP arrow, the helicopter goes up, but if you DON'T press the up arrow, the helicopter goes down (like gravity!)
Make sure to save when done!
Butterfly Game
Create a two-toned background with a butterfly or a sprite of your choice "flying" in it. Use Scratch to change the costume of your sprite when it touches one of the colors.
Helicopter Game
Open Scratch and add the helicopter sprite.
It can be found in the "transportation" folder of sprites.
Helicopter Game
Change the background to have a start, an end, and some obstacles (color is key!).
Then, make sure that if the helicopter hits an obstacle, it resets back to the start.
You now have a playable game!
Scratch: Position
Day 3, Session 4
Want smooth motion?
Coordinate Practice
Review...
New...
Choose Your Challenges
Pick a challenge from the worksheets and implement it.
Scratch: Ifs and Elses
If Block
The "if" block can be found in the control tab.
The if block means, "IF this happens, THEN do this."
You can put blocks ON the if block and IN the if block.
Sensing Blocks
Most of the blocks that fit ON the if block are sensing blocks, which can be found in the sensing tab.
Different sensing blocks can detect if a key is pressed, if the sprite is touching something, or if the sprite moves to a certain position.
Forever If
Usually, you don't want to just run the if block once, you want it to always be running.
To make it run forever you can either put it in a forever block or use the forever if block.
Operators
In Scratch, operators let you connect other ideas together.
Many of these operators do things you have seen in math.
Common Operators
Some operators let you compare values (like numbers).
Other operators let you combine other blocks.
Will the sprite say "Hello!" when you run this script?
What will the variable "X" be after you run this script?
Predict and Test
To get comfortable with operators, partner with the person sitting next to you and go through the worksheet.
Broadcast Block
The broadcast block has a sprite send a signal.
You have to give each signal a name.
When another sprite hears that signal, it can start running a new script.
This can be helpful when you don't want one script to start until another script is finished.
Receiving a Broadcast Signal
To make a sprite listen for a signal, use the receive block, and choose which message to have it wait for.
Congratulations!
You've gone through an abridged version of the Scratch curriculum!
In the time remaining, team up with a partner and create a small project to show off your Scratch skills to everyone else.
Two envelopes...
Both envelopes have some money in them. You know that one envelope has double the amount in the other envelope.
Suppose you choose an envelope and you find M money in it. Say, $20.
Now you have the opportunity to trade. Should you?
More 1990's versions...