Teaching Programming
http://www.vincehuston.org/teaching
Vince Huston

## 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

```

• Scratch ... a visual, drag-and-drop, 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 K-12 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 right-justify 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 16-element 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 user-defined 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 right-justify `sprintf` to perform integer-to-string conversion `stringstream` to perform integer-to-string 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" roll-your-own right-justification

## 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 ill-advised (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 "Model-View" 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 off-shored.
• History: the industry has a reputation as an unreliable employer.
• Proposal: we need to use robots to stimulate interest.
• Proposal: we need to use drag-and-drop, GUI eye candy, multi-media 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 ever-more-elaborate 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: multi-media, robotics, computational biology, gaming.   [
article ]

Perhaps the software industry will experience a famine-and-feast 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. self-motivating).
• Any programming language can be used.