Sample Problems

that Draw on

Mathematical Thinking

Contents

 

Pedagogy Ideas

(Contributed by Peter B. Henderson, Butler University)

  1. Use "real" problems and games early. Real problems students relate easily to, and games are both entertaining and easily understood.
  2. Emphasize rigorous, logical thinking - always !!
  3. Give several "simple" examples first; and interweave these "simple examples" with problems.
  4. Have students thinking about at most two problems at one time, but at different stages (see below). Encourage students to discuss problems with each other and with friends.
  5. Discuss problem stages in class to ensure all students understand before attempting the next "stage."
  6. Use quizes/exams to introduce new problem aspects and reinforce what they have learned.
  7. Multi stage problem solving pedagogy spread over several weeks/months.
    1. Understand the problem - identify special cases, etc.
    2. Identify patterns in the problem - iterations, case analysis, generalizations, etc.
    3. Ask students to identify invariants and other general properties - iteration, etc.
    4. Give students high level problem primitives initially - they are too immature to abstract to identify these primitives. Keep It Simple Scholar!!
    5. In later problems students can learn to identify objects and/or primitives.
    6. Once students understand the problem, the objects and the primitives, have them develop an algorithmic solution (expressed in pseudo code or graphical language). These should include: pre and post conditions and invariants where appropriate. Require students to provide a brief, informal argument that this algorithmic solution is correct.
    7. Algorithm inspections (very important): Several ways:
      • Before submission each student in class has several other students in class inspect/review their algorithm. Each of these students writes a one paragraph statement about algorithm which is submitted with the assignment.
      • Each student has a friend, who is NOT a CS major, use the algorithm to solve a few instances of the problem. This works best with games.
      • Peer evaluation after submission: remove student's name and ask one/two other students in the class to inspect/review/evaluate the algorithm. Either write a few paragraphs, or provide an evaluation form.
      The objective is to express the algorithm so it tells a story of the solution strategy. We don't want students writing mystery stories (algorithms)!!!
    8. Software development : Translate this algorithmic solution to a program. Give the students the high level primitive functions/objects.
    9. Validation (testing) - have students create test cases to convince us that their program works correctly. To demonstrate correctness, request that they annotate each test output (hard copy : write with a different color, or electronic : annotate output with a different color). These annotations must demonstrate that the correct output was derived from the specified input; potentially by showing the actual calculation if appropriate.

WARM UP I - Intuitive, Informal, Easy

(Contributed by Peter B. Henderson, Butler University)

An Algorithm Hunt

An algorithm is a well defined sequence of activities for achieving a specified task. Algorithms are an integral part of our daily lives; they are everywhere; for example, instructions for assembling a doll house. Your task is to find an algorithm. It must be a published/printed algorithm. You are to submit a photocopy of the algorithm, specify where you found the algorithm, and briefly explain its purpose and why you believe it is an algorithm. Computer based algorithms are not permitted. Let's see how many different algorithms the class can find.

English language algorithms for simple everyday tasks

Consider the task of making a peanut butter and jelly sandwich. Write an algorithm to achieve this task. Your algorithm should be written in English and expressed so that anyone can easily follow the steps to achieve the specified task.

Consider the task of brushing one's teeth. Write an algorithm to achieve this task. Your algorithm should be written in English and expressed so that anyone can easily follow the steps to achieve the specified task

WARM UP II - Intuitive Everyday, More formal

(Contributed by Peter B. Henderson, Butler University)

Consider the everyday task of making a phone call using a touch tone phone. To make a phone call some conditions need to be met. One such precondition is that a phone is available to you. The desired result is successful completion of the call and conducting the conversation. This is the post condition; that is, the desired state after the task is complete

Using pictures (boxes with labels, decision boxes, and lines with arrows) illustrate an algorithm for making a local phone call. For example, one box may have the label "dial specified phone number" and a decision box have the label "busy signal" with two lines leaving, one labeled "yes" and the other labeled "no".

WARM UP III - Counter Intuitive Invariants

(Contributed by Peter B. Henderson, Butler University)

[This is a nice problem to illustrate the concept of invariants. Use on homework or exam. Answer is counter intuitive at first, but after "playing" for a while students see the invariant pattern; especially if we give it to them, as below.]

There are two jars. Jar 1 contains a large number of blue beads and Jar 2 contains the same number of red beads. Say you take any five beads from Jar 2 and dump them into Jar 1. Then you take any five beads from Jar 1 and dump them into Jar 2. Are there the same number of red beads in Jar 2 as there are blue beads in Jar 1? Briefly explain how you derived your answer.

If you continually repeat this process, what can you say about the relationship between the number of red beads in Jar 2 and the number of blue beads in Jar 1.

Here is an algorithmic view:

REPEAT
    Move any 5 beads from Jar 2 to Jar 1
    Move any 5 beads from Jar 1 to Jar 2
FOREVER

The Real Thing - Intuitive Games with nice Structure

(Contributed by Peter B. Henderson, Butler University)

The coin flipping game

[Easy to learn rules. Nice single iteration invariant structure. Good for identifying sub-problems, specifying pre and post conditions. Run-time analysis.]

You are given a random row of one or more coins. Each coin has either heads or tails facing up. There are two actions for changing the state of a row of coins:

  1. 'flip adjacent' turns over (flips) any two adjacent coins provided the two coins have different orientations (eg, heads up on one, tails up on the other).
  2. 'flip end coins' turns over (flips) the two coins at each end of the row provided these two coins have the same orientation.

The objective is to get tails facing up on all coins in the row.

Stage 1: [Understand] Take some coins (hint: start small) and create a random row of coins. Now use the two actions to try to get all coins facing up. Repeat for different random rows of coins, with different numbers of coins. Do you understand the game? Write a paragraph or two describing what you have learned about this game.

Stage 2 (week 2): [Generalization, Patterns] Ask students to experiment with the game again and to explain in more detail what they have discovered. In particular, have students find the general condition for which this problem can't be solved.

Stage 3 (week 3): [Invariants] Using the discovery from Stage 2, students can identify/specify a precondition and iteration invariant. Ask them to build the skeleton of the iteration and fill in the pre and post conditions and the invariant. Recommendation: use red to specify pre and post conditions, and invariants. For example,

{ even number of heads up }
WHILE NOT all tails up DO
    { even number of heads up AND number of heads up > 1 }
    < body of iteration >
    { even number of heads up }
{ even number of heads up AND all tails up }

Stage 4 (week 3 or 4): [Algorithmic Problem Solving] The essence of the body of the iteration can be expressed in Pseudo Code in two simple statements. See if the students can discover these. The first requires a bit of abstraction. The second, is much easier. Hint: work/think backwards. Submit your "structured algorithm" and give a brief but convincing argument that your algorithm is correct.

Stage 5 (week 3, 4 or 5): [Inspections] See item (7.7) above. Example: Explain this game to a friend (who is not a CS major) and ask them to use your algorithm to try to solve a few simple coin flipping games. Have your friend write a brief note expressing their opinion of the understandability of your algorithm, and sign and date it. Include this note with your assignment.

Stage 6: [software development] Provide students with the basic primitive functions, abstractions and objects. For example, "all tails up," "flip adjacent coins", "flip end coins", etc. Actually, this is a simplification, for students must still develop the procedure "get heads to ends."

Validation (testing) - have students create test cases to convince you that their program works correctly. To demonstrate correctness, request that they annotate each test output.

Comment 1: This is a very nice OO problem. Coins and row of coins as object classes are very simple and illustrate these ideas very clearly.

Comment 2: Here are some questions I often ask on an exam/quiz once students are familiar with this game.

The card stacking game

[Easy to learn rules, hard for students to generalize to a algorithmic solution (many different correct solutions). Emphasizes identifying sub-problems and case analysis strategies. Main iteration invariant is fairly easy to identify/explain.]

This is a simple game consisting of three stacks of cards (labeled stacks A, B and C). Initially, cards numbered 1,2,3,4 through N (where N is between 1 and 10) are placed bottom-to-top on stack A, and stacks B and C are empty. Cards may be moved from one stack to another using only the following three moves:

The objective is to determine a sequence of moves (eg, A-B, A-C, B-C) which achieves a specified ordering of these N cards on stack C. This is the desired goal stack C.

(NOTE: You can provide a visual picture of the stacks, goal stack here)

Stage 1: [Understand] Create some cards and put numbers 1-10 on them. Create labels for Stacks A, B and C. Select an value of N (hint: start small) and a write down a desired goal stack. Create Stack A and play the game. Repeat for different values of N from 1 to 10, and random goal stacks. Do you understand the game? Write a paragraph or two describing what you have learned about this game.

Stage 2 (week 2): [Case Analysis, Patterns] Ask students to experiment with the game again and to explain in more detail what they have discovered. For example, discovering sub-problems (eg, moving only one desired card to Stack C) and explaining under what conditions is a card moved from one stack to another? Also, to explain why is a solution not always possible? Etc.

Stage 3 (week 3): [Iteration Invariants] Ask students to express, either formally or informally the invariant of the main iteration. If doing OO, ask students to identify the natural objects of the problem (eg, Numbered Cards, Stacks of Cards, Goal Stack, Solution Sequence, and The Game Itself).

Stage 4 (week 3 or 4): [Algorithmic Problem Solving] Give students basic primitives and have them compose an algorithmic solution.

Now develop an algorithm, expressed in pseudo code, for playing this game. Develop your algorithm so that it will be easy for anyone, even a non-computer person, to understand it. Your pseudo code algorithm must use structured statements such as: IF condition THEN, IF condition THEN-ELSE, WHILE condition DO, and REPEAT --- UNTIL condition (do-while). Ensure your algorithm reads like a story by using natural terms from the problem domain to express conditions and statements. For example, "not all cards have been moved", "top card of Stack A = next desired goal card", "Stack B is empty", "move( A, B )" which means move the top card from Stack A to top of Stack B, "output( A - B )" which means a move( A, B) was made, "input desiredGoalStack", etc. Submit your "structured algorithm" and give a brief but convincing argument that your algorithm is correct.

Stage 5 (week 3, 4 or 5): [Inspections] See item (7.7) above. Example: Explain this game to a friend(who is not a CS major) and ask them to use your algorithm to try to solve a few simple card stacking games. Have your friend write a brief note expressing their opinion of the understandability of your algorithm, and sign and date it. Include this note with your assignment.

Stage 6: [software development] : Provide students with the basic primitive functions, abstractions and objects. For example, move( stack1, stack2 ), "all cards moves," "Stack A is empty," "top of Stack A", "next desired goal card," etc.

Patterns Again; It's Always About Patterns

A polynomial P(x) = anxn + an-1xn-1 + . . . + a1x1 + a0x0 may be evaluated by repeatedly factoring out x (Horner's rule) as shown below:

P(x) = x( x( x( . . . ( anx + an-1) + . . . + a2) + a1) + a0

Express the polynomial P(x) = a4x4 + a3x3 + a2x2 + a1x1 + a0x0 in this factored form.

Using this factored form, show in detail the steps you would use to compute the value of the polynomial P(x) = 3x4 + (-4)x3 + 7x2 + 10x + 12 for x = 4.

Say you want to compute P(x) using an iterative algorithm to implement Horner's Rule. Just as the iterative algorithms for finding the maximum, minimum or sum of a sequence of values have well defined patterns, so does this problem. For example, finding the maximum has the pattern maxValue ( max( maxValue, valuej ) for the sequence of n values, value1, value2, ..., valuen When computing P(x) the sequence is an, an-1, an-2, ..., a1, a0. Complete the expression for the pattern: P(expression). Here expression uses x, P (the previously computed value of P) and ai for i = n, n-1, n-2, ..., 1, 0.

Compose an algorithm, expressed in pseudo code for computing the value of any polynomial given the value of x and the sequence an, an-1, an-2, ..., a1, a0

Algorithms : Important "LOOK FOR PATTERNS"

Debugging with "Proof Thinking"

(Contributed by Doug Baldwin, SUNY Geneseo)

[Often, a program doesn't work even 'though the algorithm on which it is based is correct -- typos, mistranslations to programming language, etc. can always happen. Debugging these cases is greatly simplified by understanding why the algorithm is believed to be correct (i.e., understanding its proof), and then matching elements in that proof to observable behaviors of the program -- for example, do preconditions hold prior to entering a subprogram, do postconditions hold upon exiting it, do induction hypotheses or loop invariants hold during recursion or iteration, respectively, etc. Here are some examples of buggy programs that I challenge students to debug using these strategies.]

Euclid's Algorithm

[Students see this embedded in a larger "fractions" module, which they can quickly see is buggy. They then have to isolate the bug(s). Noting that the correctness of the algorithm depends on the inductive relationship GCD( x, y ) = GCD( y, x mod y ), but that this relationship does not hold across recursive invocations, leads them to the bug -- the first parameter to the recursive call should be y, not x.]

Euclid( X, Y )
    if Y = 0
        return X
    else
        return Euclid( X, X mod Y )


Spiral

[This code uses a software robot to draw a spiral. The robot moves on a grid of "tiles", drawing a square-cornered spiral such as this:

Square-cornered spiral

Two subprograms, "Spiral" and "DrawLine", cooperate to draw the spiral: "DrawLine" draws a line whose length, in tiles, is specified by its parameter; it has a postcondition that the robot is standing on the tile after the line. "Spiral" uses "DrawLine" to draw an n-tile first side for the spiral, an n-1-tile second side perpendicular to the first, and n-2-tile third side perpendicular to the second, and so forth. It has a precondition that the robot is standing on the first tile of the first side. Careful inspection of the program's output reveals that the spiral's first side is actually n+1 tiles long, not n. The reason is that the postcondition of "DrawLine" does not match the precondition for the recursive "Spiral" in a way that allows the beginning of the second side to overlap the end of the first.]

Spiral( n )
    if n > 0
        DrawLine(n)
        TurnLeft
        Spiral( n-1 )

DrawLine( n )
    if n > 0
        Paint(green)
        Move
        DrawLine( n-1 )