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

Will require some searching.

Block cryptograms

INSTRUCTIONS: These sentences are first sentences of famous books. Find the titles of the books, and write them on the exam.

Oliver Twist

Call Me Ishmael

Cold bright morning striking thirteen

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