CS 509 Test 5

CS 509, Advanced Programming II

Spring 2002 - Test 5

Provide an asymptotic analysis of the following code:
```
string str
map<string, int> wds
std::copy(istream_iterator<string>(cin), istream_iterator<string>(), 
          inserter(wds, wds.end()))
std::copy(wds.begin(), wds.end(), ostream_iterator<string>(cout, "\n"))
```
Be sure to clearly state your accurate assumptions.
First, given the nature of string extraction, the input measure n is the number of words in the input stream.
The two definitions take constant time because there's no data involved. The three instantiations in the first copy all take constant time, again because there's no data involved; a similar argument holds for the second copy.
```
O(1)
O(1)
std::copy(O(1), O(1), O(1))
std::copy(O(1), O(1), O(1))
```
The first copy is going to copy n words from cin to the map. Each word takes constant time to read (it actually takes time proportional to the number of characters involved, but that's not our input measure), as does the comparison to eof. Inserting a word into a map takes time logarithmic in the number of words already in the map. Because we're interested in upper bounds, assuming each insertion takes log n is reasonable.
A similar analysis holds for the second copy. Moving from element to element in the map takes constant time because the iterators are bidirectional; outputting a word takes constant time. Using the loop rule on the copys and the sequence rule gives
```
O(1) + O(1) = O(1)
O(n)*(O(1) + O(1) + O(log n)) = O(n)*O(log n) = O(n log n)
O(n)*(O(1) + O(1) + O(1)) = O(n)*O(1) = O(n)
```
A final application of the sequence rule gives
```
O(1) + O(n log n) + O(n) = O(n log n)
```
Most people got at least close to the right answer. A number of people mis-estimated the time to insert a word into a map, and I don't think anybody gave a detailed justification of the estimates for the two copy calls.
The typename keyword has two uses. What are they?
typename can be used as a keyword in template prefixes, as in and to indicate that an entity from a template parameter is a type. For example
```
template <typename ContainerType>
typename ContainerType::value_type front(const ContainerType & c) { 
  return c.front();
  }
```
Without the second typename the poor, dumb c++ compiler can't figure out that ContainerType::value_type specifies a type. We talked about the first use in class; for the second use, see page 181 in the Koenig and Moo.
Describe a test to determine if pair-picking code returns the subset with minimal difference sum. Be sure to describe the complete data set for the test, as well as the expected correct answer.
A simple test case is to pick one pair from the vector
```
[<2, 1>, <2, 2>]
```
The first pair has difference sum 1 and the second pair has difference pair 0. A correctly working subroutine should return the (index of the) second pair. This is a simple question, but many people did way too much work in answering it.
A colleague of yours is always forgetting whether the test for eof on istream iterators is
```
isi != istream_iterator<InType>()
```
or
```
isi != isi.end()
```
Give a simple explanation that will help your colleague remember the correct test.
While the end() member function returns an iterator, it is not defined for iterators, but rather for containers. isi.end() makes no sense because isi is an iterator and not a container.
Only one or two people got this fully correct. Types are an important part of most modern programming languages. If you ignore types when you deal with programs, you are missing a lot of information that could be useful to you.

This page last modified on 9 April 2002.