CSC 142/Chapter 5

Chapter 5: Program Logic and Indefinite Loops

Sections:

5.1 The while loop

5.2 Fencepost algorithm

5.3 The boolean type

5.4 User errors

5.5 Assertions and Program Logic

5.6 Case study: NumberGuess

We begin this chapter with a new construct: the while loop, which executes an indefinite number of times.

We discuss the fencepost algorithm, which is a loop "template".

Then we discuss the all-important Boolean types.

Section 5.1: The While Loop

Definitions

Definitions:

• Pseudorandom numbers
• Printing a loop

Material

While loops:

• While loops run indefinitely until a condition is met
• Be careful about variable scope

Example: loop to find smallest divisor

• Loop through all numbers until one is found

Infinite loops:

• Avoid infinite loops that never end
• Give more careful consideration to how while loop will finish
• for loops - didn't have to worry about this condition, knew loop would finish eventually

Random numbers:

• Random numbers, uniformly distributed
• 0 <= x < 1
• [0,1)
• Other functionality:
• Random integer between -2^31 and 2^31-1
• Random integer etween 0 and (max-1)
• Random TF value

Example program: your number is up

• Ask user for a number from 1-10
• Run simulation of random numbers
• Count how many times before the user's number comes up

Do while:

• Execute the loop at least once
• Grammar follows form: do { } while ( )

Section 5.2: Fencepost Algorithm

Definitions

Definitions:

• Fencepost algorithm
• Sentinel

Material

How to split up an interval?

If I'm constructing 10 rectangles on an interval, 10 separate intervals, how many points do I need?

• 11 points
• (Endpoints each have own point)

Off-by-one problem:

• That one extra - that's a classic problem in computer science
• Quote: "Only 2 major problems in computer science"
• Fencepost algorithms/loop and a half problems

Thinking through pseudocode, swap order?

for (length of fence) {
  attach wire
  plant post
}

Same problem.

Better approach:

plant post
for (length of fence) {
  attach wire
  plant post
}

Another example: printing a comma-separated variable list "1,2,3,4,5" (5 numbers, 4 commas)

Sentinel algorithm:

• Related to fencepost algorithm
• Idea is, we want to listen for a particular input from the user that is a special "flag"
• Application of loop and a half problem to processing user input

Pseudocode for taking input from user and checking if it is the sentinel:

sum = 0
while (input is not sentinel) {
  get next user input
  add to sum
}

Problem? This will add the sentinel to the sum! Want each step to look like this:

• Take user input
• Check for sentinel
• If not sentinel, add to sum
• This creates a start problem - need to get one value to start with (like fencepost needing one fencepost to start with)

Switch order:

while (input is not sentinel) {
  add to sum
  prompt for next user input
}

Then, add a user prompt once prior to the loop:

prompt for first user input
while (input is not sentinel) {
  add to sum
  prompt for next user input
}

Forecasting with if:

• Another option is to put an "if" in there
• If this is the last fencepost...

Example: Strings

• String

  [please,please,please,please]

• String

  [Beetlejuice,Bettlejuice,Bettlejuice]

• Naive first pass assumption will end up with A,A,A,A,
• adjust to use for loop, with half a loop at the beginning

Section 5.3: Boolean Type

Definitions

Definitions:

• Short circuited evaluation
• Robust

Material

+-------------------------------------------+
|               |               |           |
|  Programming  |  Mathematics  |  Science  |
|               |               |           |
+-------------------------------------------+
|                                           |
|                 L O G I C                 |
|                                           |
+-------------------------------------------+
|       True          |       False         |
+-------------------------------------------+

Logical operations: True = 1, False = 0

Logical operators: AND, OR, NOT

Truth tables: p, q, p and q, p or q

Short-circuited evaluations

• Tokenizing a string
• character by character
• If no space at end, crashes when trying to access index N
• Short circuited evaluation:
  • And and or only evaluate the second argument when absolutely necessary (and it won't raise an exception if is not evaluated)
  • Two different short-circuited examples
• Boolean variables nad flags:
  • Boolean variables enhance readability
  • Boolean flags enhance testing different conditions

Boolean zen:

• isTwoUniqueDigits
• Don't need to return boolean variables, can return the results directly
• Don't need to compare to bare boolean type, can just use condition directly

Example:

Bad: if(test==true)
Good: if(test)

Bad: if(test==false)
Good: if(!test)

Negation:

• DeMorgan's Laws for negating boolean expressions
• Original (p and q, p or q)
• Negated (!(p and q), !(p or q))
• Simplified (not p and not q, not p or not q)

Life Skills

Java debugger - NOT LIKE ECLIPSE, INTRODUCE SOONER

Section 5.4: User Errors

Material

Bring full circle: why are exceptions important?

• Deal with user input
• Robust programs

Scanner look-ahead:

• had prefix to check whether we can get next item

Handling user error:

• Algorithmic thinking, loop, fencepost algorithm
• Static method to get int with error handling
• Abstraction: don't have to worry about whether we are getting an int, or implementing error checking, we just use the getInt() function and we just expect an int

Section 5.5: Assertions and Program Logic

Definitions

Definitions:

• Assertion
• Provable assertion
• Formal verification

Material

Assertions are declarative statements

Not "it should be negative" but "it will be negative"

Formal verification:

• Understanding code flow, and when certain conditions are/are not met
• Not just where a program is going, but what we know about its state

Example: assertions

• point A/B/C/D/E/F/G
• enter the program

This program checks for longest common prefix for two numbers

printCommonPrefix() {
  while (x!=y) {
    z++ //discard digit
    if (x>y) { 
      x = x / 10
    } else {
      y = y / 10
    }
  }
}

Old school method: pencil and paper table

Important analysis skill

But debuggers are also an essential tool, so use them to construct your table.

Quote: "Coding is 90% debugging, and 10% creating new bugs." @bramcohen, 3/26/2011

Section 5.6: NumberGuess Case Study

Material

Creating a gudessing game that combines indefinite loops, ability to check user input, and generation of random numbers

Computer picks numbers 0-99, user guesses, computer indicates matching digits. Program should be robust.

Iterative enhancement:

• No error checking, fixed number choice, focus on hints.
• Next step: fencepost design pattern, get user input, check, etc.

Pseudocode:

• Metaphorical thinking: fencepost algorithm
• Incorrect guesses = fenceposts
• This helps formulate the problem

No hints:

// specific number guess pseudocode
pick a number
ask for user guess
while (guess not correct) {
  print incorrect
  give hint
  get next guess
}

with hints:

...

Version of code - sequential, only 1 method

Robust version:

• main()
• giveIntro()
• matches()
• getGuess()
• getInt()

Chapter 5 Summary

Deliverables

While loops: do while loops:

• How they work, syntax
• Avoiding infinite loops, spotting infinite loops
• Situations requiring indefinite vs definite loops

Fencepost algorithms:

• Splitting up interval
• Sentinel algorithm/pattern

Boolean types:

• Truth tables
• DeMorgan's Law
• and/or, advanced conditionals
• Negation

User error:

• Exception throwing
• Abstraction

Assertions:

• Formal verification
• Deeper debugging
• Knowing what's true when, seeing/thinking about complexity of program

Chapter 5 Code

Lecture Code

Topics?

• While loops
• Fencepost/sentinel algorithm
• Assertions
• Complex program logic

isPrime function:

• Checking for prime numbers
• Walk through construction process for dealing with more complex logic

Worksheet Code

Euler's algorithm for GCD:

• Background
• Why prime numbers are important
• Why GCD is important - how it relates to prime numbers

Chapter 5 Homework

HW Questions

(Recommended) Self-check problems: #1, #5, #12, #14, #21, #27, #28

(Required) Exercises: #1, #4, #11, #18

(Required) Projects: #5

HW Details

Self-check:

• 1 - how many times will the while loop run
• 5 - Random code
• 12 - fencepost algorithm
• 14 - boolean expressions
• 21 - zune music lpayer, while loops
• 27, 28 - assertions and program logic

Exercises:

• 1 - show factors of 2
• 4 - random number of x's
• 11 - random coin flips until 3 heads in a row
• 18 - sum of digits (bonus: sum of squares, repeatedly applied, is either 89 or 1)

Projects:

• 5 - rock paper scissors, 3 items, games can tie

Chapter 5 Goodies

Puzzle 5

Blocks of 8 integers, numbers -> letters -> ROT 13 encoded message, filled with DDDs again

Puzzles/Crypto Level 1/Puzzle 5

Quotes

There are only 2 truly difficult problems in computer science:

• Naming things
• Cache invalidation
• Off by one errors

"Programming is 90% debugging and 10% creating new bugs."

- @bramcohen 3/26/2011

Elephant in Cairo (sentinel values) [1]

How to Hunt Elephants Mathematicians hunt elephants by going to Africa, throwing out everything that is not an elephant, and catching one of whatever is left. Professors of mathematics prove the existence of at least one elephant and leave the capture of an actual elephant as an exercise for one of their graduate students. Computer scientists hunt elephants using algorithm A: 1. Go to Africa 2. Start at the Cape of Good Hope 3. Work northward in an orderly manner, traversing the continent alternately East and West. 4. During each traverse a. Catch each animal seen b. Compare each animal caught to a known elephant c. Stop when a match is detected. Experienced computer programmers modify Algorithm A by placing a known elephant in Cairo to ensure that the algorithm will terminate: 1. Go to Africa. 2. Put an elephant in Cairo. 3. Start at the Cape of Good Hope. 4. Work northward in an orderly manner, traversing the continent alternately east and west, 5. During each traverse pass: a. Catch each animal seen. b. Compare each animal caught to a known elephant. c. Stop when a match is detected. 6. If you are in Cairo, then there are no elephants in Africa (other than the one you placed there). Engineers hunt elephants by going to Africa, catching gray animals at random, and stopping when any one of them weighs within plus or minus 15 percent of any previously observed elephant. Economists don't hunt elephants, but they believe that if elephants are paid enough they will hunt themselves. Statisticians hunt the first animal they see N times and call it an elephant. Consultants don't hunt elephants, but they can be hired by the hour to advise those who do. Operations research consultants can measure the correlation of hat size and bullet color to the efficiency of elephant hunting strategies, if someone else will identify the elephants. Politicians don't hunt elephants, but they will share the elephants you catch with the people who voted for them. Lawyers don't hunt elephants, but they do follow the herds around arguing about who owns the droppings. Software lawyers will claim that they own an entire herd based on the look and feel of one dropping. When the Vice President of R&D tries to hunt elephants, his staff will try to ensure that all elephants are completely prehunted before he sees them. If the VP sees a nonprehunted elephant, the staff will (1) Compliment the vice president's keen eyesight and (2) enlarge itself to prevent any recurrence. Senior managers set broad elephant hunting policy based on the assumption that elephants are just like field mice, but with deeper voices. Quality assurance inspectors ignore the elephants and look for mistakes the other hunters made when they were packing the jeep. Salespeople don't hunt elephants but spend their time selling elephants they haven't caught, for delivery two days before the season opens. Software salespeople ship the first thing they catch and write up an invoice for an elephant. Hardware salespeople catch rabbits, paint them gray and sell them as "desktop elephants." source: "Pachydermic Personnel Prediction" by Peter Olsen in the September 1989 edition of BYTE.