Teaching Programming
http://www.vincehuston.org/teaching
Vince Huston
Is there a crisis in recruiting and retaining programming students?
click
Ideas:


1 2 14 3
12 4 8
9 11 6 7
15 5 10 13
move: 8
1 2 14 3
12 4 8
9 11 6 7
15 5 10 13



Links:
 Scratch ... a visual,
draganddrop, programming language from MIT designed to help young
people (ages 8 and up) develop 21st century learning skills
 Alice ... a visual programming
environment from CMU designed to provide the best possible first
exposure to programming for students ranging from middle schoolers to
college students
 IPRE ... (Institute for Personal
Robots in Education) applies and evaluates robots as a context for
computer science education ... alleviate the "prime number syndrome"
 Alfred Thompson's blog
about teaching computer science at the K12 level
 Problets
... little coding problems for beginning programmers
 SIGCSE nifty assignment ideas
and their materials
Fifteen Puzzle
Introductory opportunities  
Data structure opportunities  
Algorithm opportunities 
cout and a loop to print a row
2 loops to print the "board"
std::setw() to rightjustify numbers
conditional expression and a single loop to print board
ternary operator, integer arithmetic, and a single loop to print board
array to hold board "state"
 
2D [4][4] array or 1D 16element array
mapping numbers to positions
supporting the "never disturb any previously positioned number" strategy
 
move number
mix up the numbers
move several numbers at once (recursion)
support userdefined width and height
compute edge conditions instead of using lots of logical expressions
..... puzzle solver .....
move numbers or move blank space?
handle last number on each row
handle last row 
Mastermind
Introductory opportunities  
Data structure opportunities  
Algorithm opportunities 
cout and cin to prompt for and receive
input
loop until puzzle is complete
encapsulate "evaluate guess" as a function
 
beside the answer array, are there auxiliary
data structures that are necessary
 
compute the "black" response
compute the "white" response

Grid Puzzle
Introductory opportunities  
Data structure opportunities  
Algorithm opportunities 
cout and loops to print the board
std::setw() to rightjustify
sprintf to perform integertostring conversion
stringstream to perform integertostring conversion
introduce vector to replace arrays
use class to encapsulate the puzzle engine
 
how to represent the state of the board
 
how to calculate "delta X plus delta Y"
rollyourown rightjustification

Peg Puzzle
Introductory opportunities  
Data structure opportunities  
Algorithm opportunities 
cout and a loop to print the board
cout and cin to prompt for and receive
input
 
is "validate a requested move" a data structure issue?
 
is "validate a requested move" an algorithm issue?
how to evaluate if requested move is illadvised (e.g. search a table
of winning puzzles, try thousands of random moves, build an exhaustive puzzle
tree)
recursion – depth first search

Set Puzzle
Introductory opportunities  
Data structure opportunities  
Algorithm opportunities 
use a loop and random numbers to shuffle the cards
decomposition into many functions (i.e. methods)
practice the encapsulation and decoupling of "ModelView"
collaboration between objects
 
how to represent the color/number/shape/fill value of each card
 
how to decide whether 3 cards constitute a set
how to compute all the sets present in an array of 12 cards
how to enumerate "all combinations of X things taken Y at a time"

Alphametics Puzzle
Introductory opportunities  
Data structure opportunities  
Algorithm opportunities 
not an easy problem
arrays (in spades)
map
new
next_permutation()
C command line arguments
use of an "off the shelf" object
 
multiple levels of indirection
a map that holds the association between a character and its
corresponding position in an integer array that represents the current
guess
 
support a variable number of terms
implement "all permutations of all combinations of 10 digits taken N at a time"
is_guess_valid()
get_value_for_word()
print_word()

Two States puzzle
Introductory opportunities  
Data structure opportunities  
Algorithm opportunities 
loops within loops
string
vector
sort()
map and multimap
iterator
 
array of array of characters
 
solve with brute force or insight?
how to enumerate all combinations of 50 states taken 2 at a time
how to compare each combination with every other combination
"perfection is achieved when there is nothing left to take away"

Towers of Hanoi
Introductory opportunities  
Data structure opportunities  
Algorithm opportunities 
not an easy problem
implement each "peg" as an instance of a class
 
implement each "peg" as a stack
 
recursion
how to represent the behavior of the solution
with a "DOS command line" user interface

Is there a crisis?
There are growing numbers of articles in magazines and newspapers
trumpeting the death of computer science enrollments.
 Fact: enrollment in U.S. computer science programs is falling.
 Perception: programming is hard and no fun.
 Perception: the assignments are boring ... e.g. the "prime number
syndrome" (computing mathematical sequences).
 Reporting: programming jobs are being offshored.
 History: the industry has a reputation as an unreliable employer.
 Proposal: we need to use robots to stimulate interest.
 Proposal: we need to use draganddrop, GUI eye candy, multimedia
rich, programming environments to stimulate interest.
According to the Chronicle of Higher Education, as enrollment numbers
in college computer science departments continue to dwindle –
especially among women – "professors are contemplating
evermoreelaborate strategies to keep the United States from slipping
further in the international engineering sweepstakes." More than a
dozen universities have created "media computation" programs, which
hope to introduce students to computer science through digital art and
Web design, not traditional programming, according to the Associated
Press. Georgia Tech robotics students teach robots to draw shapes, to
chirp on command, and to navigate obstacle courses. Many computer
science departments are rebranding themselves with emphases like:
multimedia, robotics, computational biology, gaming. [ article
]
Perhaps the software industry will experience a famineandfeast cycle
similar to that of the oil industry. After the U.S. oilfield employment
peaked at 860,000 in 1982, companies slashed more than 500,000 jobs over
the next 18 years. Texas A&M's petroleum engineering school had 1,422
undergraduates in 1982, 191 majors in 2001, and 507 majors in 2006.
Demand for geologists, geophysicists, and petroleum engineers now far
outstrips supply. Worldwide energy demand continues to escalate.
Waves of baby boomers are beginning to retire. Starting salaries are
$70,000 or higher.
[ article ]
Very modest proposal: using puzzles is an excellent
vehicle for stimulating interest, demonstrating, and practicing
programming.
 They require no special hardware or graphics/video performance.
 There is no ambiguity or arguing about requirements  you
implement the puzzle ... period.
 They are compelling (i.e. selfmotivating).
 Any programming language can be used.