CS 509 Test 3

CS 509, Advanced Programming II

Spring 2002 - Test 3

Write a complete turtle program that tests whether or not the turtle is properly reset before executing a turtle string in response to a draw command. Describe the correct output from your turtle test program.
Perhaps the simplest test program is
```
F +
F -> F
draw 0
draw 0
```
The first draw command should draw a vertical line and then tilt the turtle 20 degrees to the right. The second draw command should re-set the turtle back to the origin pointing up the Y axis and draw another vertical line. If the turtle isn't reset properly, the second command will draw a line tilted 20 degrees to the right.
One of these two loops is correct, the other is incorrect:
```
a) for (C::iterator i = c.begin(); i != c.end(); i++)
     c.erase(i)

b) while (c.begin() != c.end())
     c.erase(c.begin());
```
Which loop is which? Explain.
Loop a is incorrect independent of the container type C. The one case where you can depend on an iterator being invalidated is when it's associated element is erased; the iterator is also invalidated.
Loop b is correct; in containers where it matters (vectors, for example) erasing any element invalidates the end iterator, but the loop regenerates the end iterator at after each erasure, which insures validity.
If i is a random-access iterator, what does i[-1] mean? Explain.
See page 109 of the text.
Many people pointed out that i[-1] is an invalid access because it is accessing something to the left of the first element of the vector. However, this is only true if i is equal to begin().
Provide an asymptotic estimate for the amount of time taken by the code
```
f(a[], n)
  i = 1
  while (i < n)
    v = a[i]
    j = i
    while (j > 0 && a[j - 1] > v)
      a[j] = a[j - 1]
      j--
    a[j] = v
    i++
```
assuming a has n elements. Make sure you clearly state your assumptions.
Replacing the basic statements with their asymptotic estimates gives
```
f(a[], n)
  O(1)
  while O(1)
    O(1)
    O(1)
    while O(1)
      O(1)
      O(1)
    O(1)
    O(1)
```
under a reasonable set of assumptions. Applying the sequential statement rule to collapse adjacent estimates gives
```
f(a[], n)
  O(1)
  while O(1)
    O(1) + O(1) = O(1)
    while O(1)
      O(1) + O(1) = O(1)
    O(1) + O(1) = O(1)
```
Before we can reduce the innermost while, we need an upper bound on the number of iterations. Threading back through the code, O(n) seems like a reasonable estimate, which leads to
```
f(a[], n)
  O(1)
  while O(1)
    O(1)
    O(n)*(O(1) + O(1)) = O(n)O(1) = O(n)
    O(1)
```
Collapsing the sequence of loop-body statements gives
```
f(a[], n)
  O(1)
  while O(1)
    O(1) + O(n) + O(1) = O(n)
```
Estimating the final while loop, this time with a more obvious upper bound of O(n) iterations gives
```
f(a[], n)
  O(1)
  O(n)*(O(1) + O(n)) = O(n)*O(n) = O(n²))
```
A final sequential-statement reduction leaves
```
f(a[], n)
  O(1) + O(n²)) = O(n²))
```

This page last modified on 10 March 2002.