Transcript Computational Thinking and CS Unplugged

Computational
Thinking
What is it?
Computer Science Unplugged
1
Computational Thinking (CT)
(from Jeannette Wing’s website)
• Computational thinking will be a fundamental
skill used by everyone in the world by the middle
of the 21st Century.
• J.M. Wing, “Computational Thinking,” CACM
Viewpoint, March 2006, pp. 33-35.
http://www.cs.cmu.edu/~wing/
2
Examples of CT
(from Jeannette Wing’s website)
• Determining how difficult a problem is to solve.
Thinking recursively.
• Choosing an appropriate representation for data
to simplify the solution to problems.
• Reformulating a seemingly difficult problem into
one which we know how to solve.
• Using abstraction and decomposition in tackling a
large complex task.
• Using the difficulty of solving hard AI problems to
foil computing agents.
3
Examples of CT in daily life
(from Jeannette Wing’s website)
• Sorting important documents.
• Choosing a line at the supermarket. (queuing and
scheduling)
• Putting things in your child’s knapsack for the
day. (caching)
• Running errands (Traveling salesperson)
• Cooking dinner or washing loads of laundry
(parallel processing/pipelining)
4
CT in STEM
(from Jeannette Wing’s website)
• Biology
• Shotgun algorithm expedites sequencing of human
genome
• DNA sequences are strings in a language
• Brain Science
• Analyzing fMRI data with machine learning algorithms
• Chemistry
• Optimization and searching algorithms identify best
chemicals for improving reaction conditions to improve
yields
5
CT in STEM
(from Jeannette Wing’s website)
• Earth Science
• Modeling the earth or the sun: inner core, surface,
atmosphere
• Astronomy
• Sloan Digital Sky Server brings a telescope to every child
• Mathematics
• Discovering E8 Lie Group: Profound implications for
physics (string theory)
• Engineering
• Boeing 777 tested via computer simulation alone,
not in a wind tunnel
6
Computational Thinking
An Operational Definition for K-12
Computational thinking (CT) is a problem-solving process that
includes (but is not limited to) the following characteristics:






Formulating problems in a way that enables us to use a computer and
other tools to help solve them.
Logically organizing and analyzing data
Representing data through abstractions such as models and simulations
Automating solutions through algorithmic thinking (a series of ordered
steps)
Identifying, analyzing, and implementing possible solutions with the goal
of achieving the most efficient and effective combination of steps and
resources
Generalizing and transferring this problem solving process to a wide
variety of problems
7
Computational Thinking
An Operational Definition for K-12
These skills are supported and enhanced by a number of
dispositions or attitudes that are essential dimensions of
CT. These dispositions or attitudes include:





Confidence in dealing with complexity
Persistence in working with difficult problems
Tolerance for ambiguity
The ability to deal with open ended problems
The ability to communicate and work with others to achieve a
common goal or solution
8
Computer Science Unplugged
9
Count The Dots

Data in computers is
stored and transmitted
as a series of zeros and
ones.

How can we represent
words and numbers using
just these two symbols?
Count The Dots

Letters are represented in computers in
binary also.

Blank
A
B
C
...
Z
0
1
2
3
000002
000012
000102
000112
26
110102
Count The Dots
blank
A
B
C
D
E
F
G
H
I
J
K
L
M
0
1
2
3
4
5
6
7
8
9
10
11
12
13
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
14
15
16
17
18
19
20
21
22
23
24
25
26
01001
00011
00101
00000
00011
10010
00101
00001
01101
I
C
E
_
C
R
E
A
M
Color By Numbers



Computer screens are divided up into a grid of
small dots called pixels (picture elements). In a
black and white picture, each pixel is either
black or white.
Computers store drawings, photographs and
other pictures using only numbers.
The following activity demonstrates how a
computer image can be stored efficiently.
Color By Numbers

The letter a has
been magnified to
show the pixels.
When a computer
stores a picture, all
that it needs to
store is which dots
are black and
which are white.
1,3
4,1
1,4
0,1,3,1
0,1,3,1
1,4
Color By Numbers
6,5,2,3
4,2,5,2,3,1
3,1,9,1,2,1
3,1,9,1,1,1
2,1,11,1
2,1,10,2
2,1,9,1,1,1
2,1,8,1,2,1
2,1,7,1,3,1
1,1,1,1,4,2,3,1
0,1,2,1,2,2,5,1
0,1,3,2,5,2
1,3,2,5
Color By Numbers

This technique is called run-length encoding.



Fax transmission
Compression of images
Color encoding

Use two numbers per run


First number is how many pixels as before
Second number is what color (1=red, 2=green, ...)
Information Theory

How much information is there in a book? Is
there more information in a telephone book, or in
Harry Potter and the Deathly Hallows?


If we can measure this, we can estimate how much
space is needed to store the information.
Can you read the following sentence?
Ths sntnc hs th vwls mssng.
Twenty Guesses




I am thinking of a number between
0 and 127.
You may only ask questions that have a "yes"
or "no" answer.
For each question, you will lose one piece of
candy.
Once you guess the number correctly, you
can keep whatever candy remains.
Twenty Guesses

To pick a number between 0 and 127, you only
need 7 guesses.




Always shoot for the middle number of the range and
eliminate half the possibilities!
This concept is called binary search.
If the number was between 0 and 1,023,
you would only need 3 additional guesses.
You can guess a number between 0 and
1,048,575 in only 20 guesses!
Beat The Clock