Introduction; Review and Reinforcement: Repetition Structures

Tom Kelliher, CS18

Feb. 5, 1996

Introduction

Syllabus

1. Contract between students and instructor

2. Keys: Responsibility, Commitment, Discipline

3. Late assignments accepted only with prior approval

4. Unannounced quizzes to encourage keeping up on reading

5. Use of WWW --- abuse of WWW

6. Perspective on collaboration --- useful aid, poor crutch

7. Tentativeness of schedule

What I Expect

1. Demonstration of reasoning, problem solving and decomposition skills

2. Communication, correctness demonstration skills

3. Ability to detect, resolve ambiguity; exercise decision skills

4. ``Fluency'' in basic computing and C/C++:
   1. Basic control structures and abstractions
   2. Basic data types and abstractions
   3. Multi-module programs
   4. interactive and disk I/O
   5. ability to correct syntactic and most logical errors
   6. OS concerns

Repetition Structures

Use:

1. Execute a given block of code for each of a set of data items, whose number may or may not be known in advance:

   sum = 0.0;   // note style
   count = 0;
   cin >> data;
   while (data != 0.0) {
      sum += data;
      count++;
      cin >> data;
   }
   if (count != 0)
      average = sum / count;
   

2. Execute block until some condition is satisfied, e.g., a given degree of precision is attained in estimating the square root of x:

   guess = x / 2.0;   // good example of a sequence:
   do {               // x_0, x_1, ..., x_i
      oldGuess = guess;
      guess = oldGuess / 2.0 + x / (2.0 * oldGuess);
   } while (fabs(guess - oldGuess) > EPSILON);
   

Pretest, posttest structures

Sentinel, counter, computation controlled repetition

while

Syntax:

while (<condition>)  // note "style"
   stmt;

while (<condition>) {   // stmt replaced with compound block
   stmt1;               // while structure considered a single
   ...                  // "statement"
   stmtn;
}

Fairly simple semantics

1, 0 conditions

for

Somewhat more complex syntax:

for (<initializer>; <condition>; <post-processing>)
   stmt;

Semantics, list items optional

Post-processing quite flexible:

for (i = 1; i <= 1024; i *= 2)
   cout << i << endl;

Watch out:

for (i = 1; i != 10; i += 2)
   <stmt>;

Efficiency issues

Equivalence of for, while

Equivalent in C, orthogonal in Pascal

continue, break

continue: skip to next iteration

for (i = 0; i < 100; i++) {
   if (i % 2 == 1)   // other ways of doing the same thing?
      continue;

   cout << i << endl;
}

break: cease iterating

found = FALSE;
for i = 0; i < numElements; i++) {
   if (data[i] == targetValue) {
      found = TRUE;
      break;
   }
}

do while

At least one iteration (compare while)

Nested Loops

Arbitrary nesting possible

Example:

i = j = 0;
for (i = 0; i < 10; i++) {
   cout << setw(10) << i << j << endl;   // first 12 values printed?

   for (j = 9; j >= 0; j--)
      cout << setw(10) << i << j << endl;
}

goto Considered Bad

How could we break out of both loops in last example?