CS 509 Test 3

CS 509, Advanced Programming II

Spring 2002 - Test 3

Write a complete turtle program to test whether or not patterns are replaced in left-to-right or right-to-left order. Describe the expected output from your test turtle program.
Perhaps the simplest program is
```
F + F + F
F + F -> f
draw 1
```
If the pattern is replaced left-to-right, the start string becomes f + F after one generation, which draws line tilting 20 degress to the right off vertical. A right-to-left replacement would result in F + f after one generation, which draws a vertical line.
Describe the STL code for determining if a string is a palindrome.
See Section 6.1.2 of the text.
Provide an asymptotic estimate for the amount of time taken by the code
```
f(a[], n)
  i = 0
  while (i < n)
    m = i
    j = i + 1
    while (j < n)
      if a[i] < a[j]
	m = j
    std::swap(a[i], a[m])
```
assuming a has n elements. Make sure you clearly state your assumptions.
Start by replacing all simple statements by their upper-bound estimates:
```
f(a[], n)
  O(1)
  while O(1)
    O(1)
    O(1)
    while O(1)
      if O(1)
	O(1)
    O(1)
```
The only tricky part was determining the estimate for std::swap(). Although we can't be sure unless we look at the code, it seems reasonable to assume that std::swap() has the usual, straight-forward implementation, which takes constant time.
Now reduce adjacent estimates using the sequence rule and the if by using the if-else rule.
```
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)
```
The innermost while is next. Looking at the code an upper-bound estimate of O(n) on the number of iterations seems reasonable, giving
```
f(a[], n)
  O(1)
  while O(1)
    O(1) + O(1) = O(1)
    O(n)*(O(1) + O(1)) = O(n)*O(1) = O(n)
    O(1)
```
Another statement sequence to reduce.
```
f(a[], n)
  O(1)
  while O(1)
    O(1) + O(n) + O(1) = O(n)
```
Another while loop, this one also with an O(n) upper-bound on iterations.
```
f(a[], n)
  O(1)
  O(n)*(O(1) + O(n)) = O(n)*O(n) = O(n²)
```
And one final statement-sequence reduction.
```
f(a[], n)
  O(1) + O(n²) = O(n²)
```
Suppose the following code always works correctly:
```
clear(C & c) 

  C::iterator e = c.end()
  while c.begin() != e
    c.erase(c.begin())
```
What is the type C of the container c? Explain.
In general, remembering the end iterator for a container is dangerous because any change in the number of elements in the container invalidates the end iterator. However, this isn't true for lists; the only time a list iterator gets invalidated is when the associated element is erased. C is an STL list type.

This page last modified on 10 March 2002.