EE 322CSpring 2006 (Chase)Final
READ THIS FIRST. Please use the back side of each page for scratch paper. I will not give credit for illegible answers (and I reserve sole judgment for what is “legible”). The exam is out of 100 points, not all questions are equally hard or take equally long to complete. Good luck!
- (25 pts) A Bag is a data structure that stores a collection of objects. The collection is not really a set, because the Bag can have duplicates. The collection is not really a sequence, because there is no ordering defined for the Bag. Implement a template class BagT>. Please use inheritance to make the implementation as simple as possible. Your base class should be a vectorT>. In other words, your Bag should be built using a vector to provide the basic storage (no trees, hash tables, or linked lists please). Credit will be awarded for each of the following parts. READ THE ENTIRE QUESTION (at least skim it) BEFORE STARTING ANY OF THE PARTS!!!
- (4 pts) Give a template definition for BagT>. You must show the inheritance that you intend to use, and include all data members. Be sure to save some space, as you may think of some new data members once you’ve answered parts b through d. Please do not show any member functions in part a (we’re saving member functions for the subsequent parts).
- (4 pts) Write a function insert that takes an argument of type T and adds that to the collection. This function must run in amortized constant time.
- (5 pts) Write a member function find that takes an argument of type T and returns an iterator. If the argument exists inside the Bag then find returns an iterator pointing to any one of the positions where that object can be found (remember, a Bag can have duplicates). If the argument cannot be found, then find should return end(). This function must run in no worse than linear (O(N)) time.
- (5 pts) Write a member function called remove that takes an argument of type iterator. If the iterator points to a position other than end(), the object at that position is removed from the container. If the iterator points at end(), then remove does nothing. Note that once the object has been removed, the iterator will (obviously) no longer point to that object. After remove, the iterator should point to some successor object in the Bag (or to end, if there are no successor objects). To make this requirement more concrete, the following example must run in O(N) time for a Bag<int> with N elements and it must remove all the odd values from x.
void removeOdds(Bag<int& x) {
Bag<int>::iterator p = x.begin();
while (p != x.end()) {
if (*p % 2 == 0) { ++p; } // an even value, skip it
else { x.remove(p); } // an odd value, delete it (don’t increment p)
}
}
- (4 pts) Our Bag requires several other member functions not listed above. For each of the following functions, indicate if the function would be inherited, trivial, or complex (i.e., this is a multiple choice problem, and those are your three choices). A function counts as “trivial” if either it has no statements (i.e., it’s just “{}”), or if it is not required because the compiler will generate an acceptable function for you. Any other function (even if it has just one line) counts as “complex”. Note that vector<T> has a member function defined for each item in this list.
- A no-argument constructor
- A destructor
- begin()
- end()
- (3 pts) vector<T> provides an operator[] that really does not make sense for a Bag (bags are not sequences, and anything that suggests that the values are ordered would be misleading). I’d like to make sure that my Bag does not inherit []. What can I do about this? (note, I’m specifically excluding private inheritance, for two reasons – first, we agreed that private inheritance was not a topic I’d test you on, and second, I don’t think that’s the best way to do this at all) What should I do to prevent people from creating a Bag<T> named x and then calling x[42]? Please be as specific as possible, if there’s code that you can write to solve this problem, write the code!
- (6 pts) When we talked about hash tables, we always assumed that the hash function could be computed in O(1) time. However, our hash function for strings was clearly linear in the length of the strings (i.e., Θ(s) where s is the number of letters in the string)). What is the actual worst casse time complexity for the find function in a hash table under the following assumptions?
- N elements in the hash table, the load factor is < 1 and the hash function takes O(s) time to run (your answer may depend on both N and s).
- Same assumptions as part a but in addition, the hash function provides simple uniform hashing.
- (12 pts) Consider the remove function. Every data structure can have a remove function (of course, each data structure’s function will be different). Imagine a remove function that takes an iterator as an argument. The remove function should remove from the data structure the object that is pointed to by the iterator. The ordering properties (if any) of the data structure should be preserved – in other words, if we were to remove an object, and then iterate over the entire data, then we’d see the same sequence of values as we did before, except the removed value would be missing from the sequence. What would the worst case time complexity of remove be for each of the following data structures (please assume that remove is implemented as efficiently as possible given the limitations of the data structure).
- Red/Black tree
- Hash table
- Doubly-linked list
- Vector (also known as ”expandable array”)
- (8 pts) Assume I have a template class of the form HashTable<typename K, typename H>, where type K is the type of data stored in the hash table (the key type) and H is a function object that will serve as a hash function. Assume that I wasn to instantiate this template with K equal to double. Write a function object that I can use for H. Half of the credit for this problem is awarded for creating any kind of reasonable function object, and half will be awarded for creating a good hash function. Of course, you can only write one answer, so try to write a function object that is a good hash function for type double. You may assume that double is a 64-bit type, and that int is a 32-bit type if that proves relevant to your answer.
- (8 pts) Yes/No questions relating to inheritance
- Could it make sense for an abstract class to have data members?
- Could it make sense for an abstract class to have a constructor?
- Should static functions be virtual?
- If I have 6 int data members in my base class, and 2 int data members in my derived class, should I expect that my Base class objects will take up three times as much memory as a derived class object?
- (10 pts) Although we don’t normally think of integers as being data structures, they can act a bit like them. Each integer is actually the product of one or more prime numbers. Hence, an integer (like the number 60) is actually a data structure containing a sequence of primes (in the case of 60, the primes are 2, 2, 3, and 5 – note that the prime number 2 is stored in 60 twice). Write a class PrimeBox and an iterator. A PrimeBox is a data structure that is created from an integer, and contains the sequence of primes for that integer. The iterator “points” at each of the primes inside the prime box.. For full credit, your solution must have O(1) space for both the PrimeBox object and the iterator object. Here’s an example of how a PrimeBox and its iterator might be used.
int main(void) {
PrimeBox x(60);
PrimeBox::iterator p = x.begin();
while (p != x.end()) {
cout < *p;
++p;
}
}
- (4 pts) Consider the following. On the left, I have an object-oriented solution, and on the right I have a traditional solution. Review the two examples and answer the following questions. Please recognize that I can only give you credit if you explain your answer.
- (2 pts) Which version (the “normal” or the “object-oriented”) will use less memory? Assume that there will be millions of Foo and Bar objects created when the application is run.
- (2 pts) Which version (the “normal” or the object-oriented”) of “fun” will run faster?.
class Base {
public
virtual void doit(void) = 0;
};
class Foo : public Base {
public:
virtual void doit(void) {
cout < “Foo!”;
}
};
class Bar : public Base {
public:
virtual void doit(void) {
cout < “Bar.”;
}
};
void fun(Base* b) {
b->doit();
}
- (15 pts) Design a class that supports “saturating arithmetic”. With saturating arithmetic, overflow is handled by setting the result equal to the maximum value. So, if we establish that 100 is the maximum value and we want to add x and y, then if the sum is greater than 100, we return 100 as the result (i.e., all arithmetic “saturates” at the defined maximum). Here’s what I’d like you to do. I’m going to divide the work into parts to make it easier to assign partial credit for this problem (5 pts for each part).
- Define a class SatInt including a constructor and whatever operator(s) you need to make the following program work. The following program should print 42.
int main(void) {
SatInt x(42);
cout < x < endl;
}
- Write a function so that the class maximum value can be set to 100 using the following statement. Note that I would prefer that you did not use any global variables in your solution, although you can use static data members or ordinary (non-static) data members as you see fit. This program should print 100.
int main(void) {
SatInt::setMax(100);
SatInt x(412);
cout < x < endl;
}
- Write the code that allows me to perform addition on two SatInts. The following program should print 42 and then 100
int main(void) {
SatInt::setMax(100);
SatInt x(21);
cout < x + x < endl;
cout < x + x + x < endl;
}
Show your complete solution below. Each of the parts above is worth 5 points.
- (4 pts) Consider the following class, and then indicate for each of the following if the function call is legal
class Cake { };
class ChocolateCake : public Cake;
void eat(Cake x) { cout < “burp”; }
void love(ChocolateCake y) { cout < “yummy!”; }
Cake cake;
ChocoateCake choc;
- love(cake)
- eat(choc)
- (8 pts) Consider the following class and indicate the result of each of the following expressions
class B {
public:
virtual void vf(void) { cout < “B::vf”; }
void f(void) { cout < “B::f”; }
};
class D : public B {
public:
virtual void vf(void) { cout < “D::vf”; }
void f(void) { cout < “D::f”; }
}
int main(void)
B bob;
D dob;
B* ptr = &dob;
B& roob = dob;
}
- bob.vf();
- ptr->f();
- ptr->vf();
- roob.vf();