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

While loops and fencepost algorithm

• Walk through constructing a fencepost algorithm program
• Sentinel program

Assertions and program logic:

• Use an example requiring more complex logic
• Use a debugger to explore the program during lecture

Worksheet Code

Checking for prime numbers: isPrime

Sieve of Arasnosthenes:

• Background
• Why are prime numbers important?
• Describe the concept behind the algorithm.
• Finding prime numbers and factoring numbers - one of the most important uses of computers today - cryptography

Homework Code

(Homework problems?)

Chapter 5 Goodies

Chapter 5 Puzzle

Modular arithmetic

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