CS 509 Test 3

CS 509, Advanced Programming II

Fall 2003 - Test 3

Here are two loops:
```
while (lst.size() > 0)
  lst.erase(lst.begin())

while (vtr.size() > 0)
  vtr.erase(vtr.begin())
```
Provide an asymptotic analysis to determine which of these two loops are faster. You may assume the containers have the suggested types.
The atomic parts of the first loop are begin(), erase(), and size(). For lists, begin() and erase() have constant estimates, while size() has a linear estimate.
```
while O(n)
  O(1) + O(1) = O(1)
```
The loop iterates until all list elements are deleted, for a linear estimate.
```
O(n)*(O(n) + O(1)) = O(n)*(O(max(n, 1))) = O(n)*(O(n)) = O(2ⁿ)
```
The atomic parts of the second loop are the same as for the first loop, but the estimates are different. For vectors, begin() and size() have constant estimates, while erase() from the beginning has a linear estimate.
```
while O(1)
  O(n) + O(1) = O(max(n, 1) = O(n)
```
The loop estimate is the same, for the same reason.
```
O(n)*(O(n) + O(1)) = O(n)*(O(max(n, 1))) = O(n)*(O(n)) = O(2ⁿ)
```
Both loops have the same asymptotic behavior.
Most people got this wrong by not providing a asymptotic estimate; instead they tried to talk their way though both loops. Among those that provided an analysis, the most common mistake was to estimate lst.size() as constant, which is not too terrible a mistake to make.
The std::inserter(c, i) iterator adaptor creates an iterator that inserts each new value before (that is, to the left of) the value referenced by i. Explain why, if container c is a vector, you don't have to worry about iterator invalidation.
The c.insert(i, v) insert member function returns an iterator to the inserted value. That being the case, given that ip is the iterator specifying the insertion point, the inserter can be implemented as
```
ip = ++c.insert(ip, v);
```
The possibly invalidated iterator ip is regenerated after each insertion.
Many answers assumed that c was a vector and then asserted that vectors don't suffer from iterator invalidation; both the assumption and assertion are wrong.
Explain why the indexing operator [] cannot be used on constant maps.
Using m[k] to look up key k in map m has the side-effect of inserting k (and the associated default a-value) into m if k isn't there already. If m is constant, then it can't be changed and the look-up is illegal because it's generally impossible for the compiler to tell which uses of indexing may try to insert a new value into the map.
There were many ambiguous answers to the effect that because the map was constant, the index operator couldn't change the map and so it was illegal. This answer is ambiguous because it doesn't indicate why indexing may try to change the map. Other answers were just flat wrong, claiming that indexing was only valid for vectors.
Describe a test case that establishes the maximum number of plots for an n x m community garden. Make sure you justify why your test case results in the maximum.
Looking at one community-garden border of length m, it's not too hard to see that there are m - 2 possible points at which an irrigation ditch can end. Extending that observation to all for borders leads to the test case
```
n m
1 1 2 1 3 1 ... n - 1 1
1 2 n - 1 2
     .
     .
     .
1 m - 2 n - 1 m - 2
1 m - 1 2 m - 1 ... n - 1 m - 1
```
Most answers were correct, although several didn't include a test case.

This page last modified on 1 November 2003.