Transcript Keynote talk - People

A Puzzle to Entertain You
I have a bag that holds one marble, with
equal probability that it is white or black.
I add a second marble to the bag, that is
white. I then shake the bag, and take one
marble out. It is white.
What is the probability that the remaining
marble is black?
A Puzzle to Entertain You
I have three cards. The first card is blue on
both sides. The second card is red on one
side and blue on the other. The third card
is red on both sides.
Now, I show you one side of a card, and it
is red. What is the probability that the
color on the other side is red?
How Can We Teach
Problem Solving?
Clifford A. Shaffer
Department of Computer Science
Virginia Tech
[email protected]
Talk Overview
Problem Solving
1.
◦
◦
2.
What it means to teach PS
How I teach PS, and variants
Computational Thinking and the CS
Principles initiative
NOT Problem-Based Learning

PBL is about a way to present content
◦ Students learn content in the context of
addressing “real-world” (or at least bigger)
problems.

By “Problem Solving” I mean fundamental
skills/strategies that people apply to solve
problems of any type.
Motivation: Why We Care

Many students are not good at debugging
◦ Deduction vs. Random Walk
Many students are not good at design
 Many students are not good at analysis

◦ Algorithm Analysis, systems analysis

These deficiencies motivated the course,
and overcoming them is therefore the
goal.
How CAN we teach PS?
An old problem for teachers.
 Polya: 1940s

◦ Heuristics
What Does It Mean to Teach
Problem Solving?

Fundamental Hypothesis:
◦ Problem Solving is a skill, not an ability.
◦ Otherwise, we cannot do anything.

Secondary Hypothesis:
◦ Being good at problem solving correlates to
being good at Computer Science.
◦ Skill(PS) ~ Skill(CS)
◦ Otherwise, why bother?
A Student Comment
“We are already good at this.”
 Implied hypothesis:

◦ If you are good at Computer Science, you are
good at PS.
◦ Skill(PS) => Skill(CS)
◦ There does appear to be a lot of truth to this.
◦ Correlated? PS is a prereq for CS capability?
Fundamental Challenge
We want to improve the capability of the
weaker students to do CS
 The hypothesis:

◦ We can do that by improving their PS skills
◦ Increased Skill(PS) => Increased Capability (CS)
Observation

Many people enjoy doing puzzles.
◦ Maybe an interest in puzzles correlates to an
interest in CS?
◦ Irony: When a student tunes out my lecture
on PS because they are working on a Sodoku!
History of our PS Course
~2006, our Undergraduate Program
Committee developed major changes in
undergraduate curriculum
 Teaching PS: not my idea, but I ended up
developing the course
 I found textbooks to make a course

Pedagogical Approach

Weekly homeworks
◦ Wide variety including self assessment tests,
problem sets (individual or in pairs)

Key Pedagogical Technique
◦ Many classes involve students working
problems (come to board and demonstrate)
◦ Goal is to “make visible” the problem-solving
process
◦ Failure illustrates more than success
What I Actually Teach (1)
PS diagnostic, self understanding tests
1.
◦
2.
3.
Myers-Briggs, Learning Styles Inventory,
Conflict resolution
Technique: Thinking aloud, working in
pairs, engaging a problem
Verbal reasoning/”logic”, Analogy
problems
Jack is slower than Phil but faster than Val.Val is
slower than Jack but faster than Pete. Write the
names in order of speed.
What I Actually Teach (2)
Heuristics: (about 1/3 of the course)
4.
◦
◦
◦
◦
◦
◦
◦
◦
◦
Externalize
Visualize
Special Features
Look at Extremes
Simplify
Sleep on It
Penultimate Step
Symmetry
Invariants
What I Actually Teach (3)
5.
6.
Lateral Thinking
Deductive and Hypothetical Reasoning
Today is Saturday. What is the day after 4 days before
tomorrow? [These are hard!]
5.
6.
7.
Making an argument: proof styles
Problem Solving and Programming
Succeeding as a student
What I Actually Teach (4)
10.
Problem Solving in-the-large:
◦
◦
◦
◦
◦
Problem Definition
Generating Potential Solutions
Deciding Course of Action
Implementing Solution
Evaluation
11.
◦
12.
Computational Thinking
Simulation, Optimization, and Statistics
Interpersonal Problem Solving
Sources






Effective Problem Solving, Second Edition, Marvin
Levine – Heuristics
Problem Solving & Comprehension, Sixth Edition,
Whimbey and Lochhead – careful deductive
reasoning
The Art and Craft of Problem Solving, Paul Zeitz –
Proofs, Math problems (sparingly)
Strategies for Creative Problem Solving, Second
Edition, Fogler and LeBlanc– PS in-the-large
I also actively collect sample problems
Michalewicz: Puzzle Based Learning
Variant: Math Olympiad Approach
Could make the class more math
oriented
 I don't want to make my class too math
heavy.

◦ Exactly the people that I want to reach
(weaker CS students) have less capability at
math (or are even math-phobic)

I don’t need math to find hard problems!
Other Variants

CS topics vs. CS relevant examples
◦ Finite state and other machines
◦ Algorithms
◦ Big project for group to work on (or PBL)
Computational Thinking
 Puzzle-based Learning

Challenges

Student reaction is not strongly positive
◦ Our students tend to focus on programming
and “obvious” CS content
◦ “CS == Programming”
◦ Can mitigate by tying more closely to CS
content. Debugging?

Need to maintain faculty support
◦ If viewed as “non-critical”, lower division
courses get pushed out.
Major Positive (to Students)

Gives students a framework and a
terminology for discussing the process of
problem solving.
The state of Computer Science
Education in the US

Boom and Bust cycle (~15-year cycle)
◦ We are coming out of a bust
◦ NSF reports 70% reduction in CS majors
(80% drop among women)
◦ We are starting to recover numbers

Predictions are for a huge deficit in CSrelated workers
◦ Claims of “all the new jobs” related to CS
Computation Thinking
Proposed Solution: Teach CS in K12!
 NSF
◦ Jeanette Wing
◦ CE21 program
CS Principles initiative
 Google
 Alice, Scratch, etc.
 Universities giving summer workshops for
middle/high school teachers

Harsh Realities in US K12 Education
CS is not part of the core
 Few K12 teachers trained to teach CS
 Lowered interest among students for
taking high school CS
 Recently lost our advanced AP exam

NSF’s CE21 Program

Goals:
◦ Train more teachers to teach CS (10,000?)
◦ Teach K12 students to “think
computationally”
◦ (We already teach “computer literacy” in
primary school)

Includes a push to teach CS topics in
middle schools (6-8)
◦ This is where most kids decide their career
CS Principles (csprinciples.org)
NSF Funded Project; College Board
 PI: Owen Astrachan at Duke
 Goal: Define a new AP course
 Teach it at High School and College Intro

CS Principles (csprinciples.org)
NSF Funded Project; College Board
 PI: Owen Astrachan at Duke
 Goal: Define a new AP course
 Teach it at High School and College Intro
 Not a classic programming course
 Teach a broader introduction to the
concepts of CS

CS Principles (csprinciples.org)
NSF Funded Project; College Board
 PI: Owen Astrachan at Duke
 Goal: Define a new AP course
 Teach it at High School and College Intro
 Not a classic programming course
 Teach a broader introduction to the
concepts of CS
 Computational Thinking!

CS Principles (csprinciples.org)
NSF Funded Project; College Board
 PI: Owen Astrachan at Duke
 Goal: Define a new AP course
 Teach it at High School and College Intro
 Not a classic programming course
 Teach a broader introduction to the
concepts of CS
 Computational Thinking!
 Pilot Sites

CS Principles Big Ideas
1.
2.
3.
4.
5.
6.
7.
Computing is a creative human activity that
engenders innovation and promotes exploration
Abstraction reduces information & detail to focus on
concepts relevant to understanding and solving problems
Data and information facilitate the creation of
knowledge
Algorithms are tools for developing and expressing
solutions to computational problems
Programming is a creative process that produces
computational artifacts
Digital devices, systems, & networks enable and foster
computational approaches to solving problems
Computing enables innovation in other fields
Computational Thinking Practices
1.
2.
3.
4.
5.
6.
Analyzing effects of computation
Creating computational artifacts
Using abstractions and models
Analyzing problems and artifacts
Communicating processes and results
Working effectively in teams
(Almost) The End
Thank you for listening!
 What are your experiences with teaching

◦ Problem Solving?
◦ Computational Thinking?
A Closing Puzzle
A man is driving his car on a shopping trip
around town. Shortly after he starts out,
he notices that his odometer (which has
six digits) is showing a palindrome. An
hour or so later, as he is nearly finished
with his shopping trip, he looks at his
odometer again. He notices that it is
showing a different palindrome.
How far did he drive?
A Closing Puzzle
On 24 January 1993, Ms. Green celebrated
her birthday. This was a special day
because the number of years she had now
completed was equal to the sum of the
digits for the year when she was born.
How old was Mrs. Green that day?