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:

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.

    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.