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

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

Chapter 5 Goodies

Quotes

There are only 2 major problems in computer science:

• Naming things
• Cache invalidation
• Off-by-one errors