CS 509 Test 5

CS 509, Advanced Programming II

Spring 2002 - Test 5

Describe a test to determine if pair-picking code handles the case where subsets have identical minimal difference sums. Be sure to describe the complete data set for the test, as well as the expected correct answer.
When two or more candidate subsets have identical minimal difference sums, the subset with the largest total sum should be returned. The simplest test for largest total sum involves selecting a single pair from the vector
```
[<1, 1>, <2, 2>]
```
Both pairs have minimal difference sum (which is 0), but the pair <2,2> has a total sum of 4, while the pair <1,1> has a total sum of 2.
Many, many people wrote test cases that were much more complicated than they needed to be, but almost everybody got this right.
Explain why operator [] can't be applied to constant maps.
Map operator [] may change the map to which it is applied. If key k doesn't exist in map m, then m[k] inserts <k,v> into m, where v is the default value for the associated type. This occurs even if operator [] is used in a read-only context, such as on the right-hand side of an assignment statement.
Far too many people got this wrong. A number of people tried to argue that bidirectional iterators can't support operator [] - and that's true - but that has nothing to do with constant maps (or with how operator [] is implemented for maps). Some people tried to argue that operator [] can be used to write values into a map, and so shouldn't be used on constant maps. That's also true, but no reason to prohibit their use at all; just think of the analogy with vectors.
Provide an asymptotic analysis of the following code:
```
 string str map<string, int> wds

while cin >> str 
  wds[str]++

map<string, int>::iterator i = wds.begin() 
const map<string, int>::iterator e = wds.end()

while i != e 
  cout << i-> first << " " << i->second << "\n"; 
  i++; 
```
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 first two initializations take constant time because there's no data involved. It takes constant time to extract a word from cin, log n time to find it in the map (this assumes there are already n words in the map, which is a legitimate assumption given that we're looking for an upper bound), and constant time to increase the associated value by one.
The two iterator declarations take constant time because the ends of a container can be found in constant time. Iterator inequality takes constant time, as does output (it actually takes time proportional to the number of characters to be output, but that's not our input parameter n) and increasing the iterator by one takes constant time (the iterator's bidirectional).
```
O(1)
O(1)

while O(1)
  O(log n)

O(1)
O(1)

while O(1)
  O(1)
  O(1)
```
The first loop iterates once for each word from cin for a total of n; the second loop iterators once for each word in the map, which may be smaller than n (if words are repeated) but will never be larger than n, making n an acceptable upper bound. Applications of the sequence and loop rule gives
```
O(1)

O(n)*(O(1) + O(log n)) = O(n)*O(log n) = O(n log n)

O(1)

O(n)*(O(1) + O(1)) = O(n)*O(1) = O(n)
```
One final application of the sequence rule gives
```
O(1) + O(n log n) + O(1) +O(n) = o(n log n)
```
Most people got this right. The most common mistake was to underestimate the cost of inserting into a map, which takes O(log n) time.
Explain the idea behind Koenig and Moo's scheme for generating a random number in the range [0, n).
Use n buckets, each one RAND_MAX/n wide and use the random number generated to select a bucket; return the selected bucket's number. See Section 7.4.4 in the text.
I think one or two people got this completely right. A few more people clearly read it, but didn't really understand what was going on.

This page last modified on 9 April 2002.