Class Notes Week 7

Announcements

• Quiz 3 this week
• Lab 6 is out and due Saturday (or before you go on break)
• You will likely need to work on lab 6 in the CS labs (not remotely)

Week 7 Topics

Monday Wednesday Friday

• Top-Down Design
• Bottom-Up Implementation
• File Input/Output
• List of Lists

Top Down Design

Top Down Design (TDD) is a problem solving technique where:

• Start with general description of problem
• Break it into several high-level steps
• Iteratively break the steps into smaller steps until you have steps that are easier to solve

Top-down design is a lot like creating a paper outline for a large paper where you start with the main sections, and iteratively refine each part with more and more detail until you are ready to start writing the paper.

When you use top-down design, your resulting program's structure will match the above idea of an outline: the main function should have calls to a few high-level functions, one for each high-level step; high-level functions have calls to unctions that implement sub-steps of the high-level step; and so on.

Iterative Refinement

When writing a large program, programmers use Iterative Refinement: do some top-down design, write function stubs for this part of code and maybe some implementation, then test. Iteratively, add more functions to accomplish subproblems, and perhaps refine some of the steps using Top-Down design, and test, and so on. The idea is to write some code, test it, then write a little more code, and test it before writing even more. Usually, I write a function, then test it, write another function, test it, ... This way if I'm careful about testing, I know that if there is a bug in my program it is with the new code I've just added.

Function Prototyping

We often use prototyping to just put in function stubs so we can test the whole program's flow of control without having to have a full implementation. For example, here is a stub for a function to compute square root (it doesn't actually do anything related to the task, but we can call it from other parts of our program to see if the program's flow matches the design):

def squareRoot(num):
  """
  This function computes the square root of a number.
    num: the number
    returns: the square root of num
  """

  print("inside squareRoot")

  # TODO: implement this function

  return 1  # a bogus return value, but it let's me run the program
            # and make calls to this function stub to "see" program flow

Let's try it out...

We are going to walk through the process of designing a computer game to simulate the dice game Craps. The rules for a single game are as follows:

1. A player rolls a pair of six-sided dice
2. If the initial roll in step 1. is a 2, 3, or 12, the player loses.
3. If the initial roll in step 1. is a 7 or an 11, the player wins.
4. Otherwise, the player must roll for point. In this case, the player keeps rolling until she re-rolls the initial roll in step 1. (a winning game), or rolls a 7 (a losing game).

What are the chances of winning a single game of craps? Instead of heading to the casino, let's use our Computer Science Top Down Design skills to see if this is a good game to play. Our program should ask the user for the number of craps games to simulate and then output the percentage of games won.

Working with a partner, think about how you can design main to be very short, maybe 5-10 lines with calls to 2-3 helper functions. How would you design main? What would the input parameters and return values of your helper functions be? Do not worry about the implementation of the helper functions at this point. Your discussion should focus on the high level concepts, not the low level python details.