EECE 352: Final Exam

Fall 1999


Name:________________________________ SSN:_____________
USC Academic Integrity Statement

I understand that it is the responsibility of every member of the Carolina community to uphold an maintain the academic standards and integrity of the University of South Carolina. Any member of the University community, who has reasonable grounds to believe that an infraction of the Code of Student Academic Responsibility has occurred, has an obligation to report the alleged violation.

I certify that I have neither given nor received unauthorized aid on this exam.





_____________________________________________________
student's signature
  1. (5%) For each one of the member functions (including the constructor) of the class below, write next to it whether the function will compile or not. If it does not compile, state what is the problem. 
    #include<iostream>

using namespace std;

class C{
  int x;
public:
  C(int y) x(y) {}; 

No. It is missing : 




  void f(const C &a) { 
    x = a.x;}

Yes




  void g(C & a) const { 
    x = 10;}


No. It is a const function so it cannot change any data member.


  int h(int & y){
    return y * 0.5;}


No. It returns a double.

  int j(const int * y) const{
    *y = 10;}

No, it must return an int. (But I gave everyone credit
since some compilers would let this go).




  int k(const int & y) const{
    y = 10;}


}


No. It is a const function so it cannot change any data member. Also,
it needs to return an int.
  2. (10%) Write a templated container class which stores only one object whose type is given by the template variable. The constructor takes the object as an argument and stores a copy of this object. The class must also have a get and a put member functions which return and set the value of the object. You can assume that the templated class has a copy constructor defined for it.

    This is the first question where I could tell which students know how to program and which do not. Several students simply copied the code for a Stack or a Queue from the book, that answer received zero credit. On the other hand, if you knew how to get rid of the array in the stack (easy) then you had your answer: 

    #include<iostream>

using namespace std;

template<class Etype>

class C {
  Etype element;
public:
  C(Etype e) : element(e) {};
  void put (Etype e) { //pass by value assures copy constructor was called
    element = e; }
  Etype get(){
    return element; } //again, return by value.
}
  3. (5%) What is the big-O running time and space for each of the following functions.

    I only graded for time in this question: 

    void f(int n) {
  vector<int>v;
  int count;
  for (int i=0; i < n; ++i){
    v.push_back(i);
    for (int j=0; j<i; ++j){
      count++;
    };
  };
}

Time = O(n2), Space= O(n)

int john(int n){
  if (n <= 0) return 0;
  return john(n-1) + john(n-2);
}


Time = O(2n), Space = O(1) 
                         or O(2n) if you take into
                         account call stack.

int paul(int n){
  int count =0;
  if (n <=0)
    return 1;
  for(int i=0; i< 50*paul(n/2); i++){
    for(int j=0;j<30;j++)
      count++;
  };
  return count;
}
Time = T(N) = 30*50*T(N/2) + O(1), to which we apply Thm. 7.5 to get
Time = O(Nlog2150), Space = O(1) or O(n) with call stack.

void george(int n){
  map<int> m; //assume its implemented as a red-black tree
  int x;
  for (int i=0;i<n:i++){
    cin>>x;
    m[i]=x;
  }
}

Since the map is a red-black tree, adding stuff to it takes
O(log n) time.

Time= O(n log n), Space = O(1),

void ringo(int n){
  ifstream ifile("file"); //assume its big enough
  vector<int> v;
  int x;
  for (int i=0; i<n; i++){
    ifile >> x;
    v.push_back(x);
    v.sort();
  }
}

Sort, as we all know, takes O(n log n) so:
Time = O(n2log n), Space = O(n)
  4. (5%)When can you use a wraparound queue implementation? That is, what needs to be true for you to successfully use it? Why would you want to use this implementation? 
    We use a wraparound queue when we know that we will never have more
than N items in the queue, where N is the size of the array. This
implementation conserves memory.
  5. (10%)Implement a stack, including the push, pop, and top operators, by using the STL queue container.

    Some students chose to implement pop the "hard way" using a for loop, that is fine since they might not have brought with them printouts of the class handouts about the STL. Other students simply copied the stack class from the book; they received no credit. 

    #include<queue>
using namespace std;

template <class T>
class Stack {
  queue<T> q;
private:
  Stack(){};
  void push(const T & e) {
    q.push_front(e);};

  T top() {
    return q.front();};

  void pop(){ //or you can use the iterator to get there.
    q.pop_front();}; 
}
  6. (5%)Given a Quicksort function as implemented in the book, with a cutoff of 2 and a "median of three" pivot picking function (note: if the number of elements is even, the middle element is the floor(last-first)), write the pivot(s) that are picked at each recursive level of the Quicksort function as it is applied to the list below. Write the pivot(s) in the table below, where level 0 corresponds to the first call to Quicksort. Note that the table might have more levels than you need.

    8 4 1 9 2 7 6 3 5 10

    Level                    Pivot(s)                   
    0 8
    1 5
    2 3
    3 
    4 
  7. (5%)In what order should you insert the numbers 1 thru 10 (inclusive) into a Binary Search Tree such that a Find(5) operation done after all the numbers are inserted will take the maximum amount of time? 
    One solution, among many, is:
 1 9 2 8 3 7 4 6 5
  8. (10%)Write a class that implements a family tree. That is, each node represents a person. Each person has a mother, a father, and some number of children. Your family tree must implement a member function isIn (const string & n) which returns true if the person whose name is n is in the family tree and false otherwise. You can use all the STL containers you need, but you need to implement a tree structure (i.e. the relationships must be preserved by your data structure).

    Everyone received full credit for this question. It was a very bad question. What I was trying to do was to make sure they understood how to implement a tree, with a node class and a tree class. Of course, I could not ask them to implement a binary tree since they would just copy from the book, so I had to modify the problem a bit. Unfortunately, the family tree has too much "baggage", some of the students tried to implement a lot more functionality than what I was looking for, some did not understand the question. I will need to find a better way to ask this question. 

    #include<string>
using namespace std;

class FamilyTree{
  class FamilyTreeNode{
    string name;
    FamilyTreeNode * mother;
    FamilyTreeNode * father;
    vector<FamilyTreeNode> children;
  public:
    FamilyTreeNode(): father(0), mother(0) {};

    bool isDescendant(string & n){
      if (name == n)
	return true;
      for (vector<FamilyTreeNode>::iterator i = children.begin();
	   i != children.end(); ++i) {
	if ((*i).isDescendant(n))
	  return true;
      }
      return false;
  }

  FamilyTreeNode *headMother;
  FamilyTreeNode *headFather;
  bool isIn(const string & n){
    if (headMother->isDescendant(n))
      return true;
    return headFather->isDescendant(n);
  }
}
  9. (5%)Show the top-down Red-Black Tree that is generated after each one of the following numbers are inserted into an empty tree.
    5 4 3 2 1 6 7 8 9 
    
The final answer looks like:


               9 
             8
               7
          6
             5
        4
             3
           2
             1


Where 1, 3, 6, 7, 9, are red.
  10. (5%)The table below represents an empty Linear-Hashing Hash table. The hashing funtion is F(X) = X % 10, that is, X modulo 10. Show where the numbers below end up in the hash table if we insert them in the order (left to right) shown below:
    25 35 13 3 33 21 11 2 10 100
    Index      Value     
    0  10
    1  21
    2  11
    3  13
    4  3
    5  25
    6  35
    7  33
    8  2
    9  100
  11. (5%)(a)What is re-hashing? (b) When is it needed? (c) If we have a linear-hashing hashing table of intial size 10 and insert 55 elements into it, how many times will we need to rehash assuming we double the size each time? (d) Answer (c) but using quadratic-probing. (e) Answer (c) but using separate chaining. 
    a-  Re-placing all the elements of a hash table into a new one

b-  When it fills up

With lambda=.5, or 1:

c-  4 

d-  4 

e-  0, with separate chaining there is no need to rehash. Some
students did explain that they wanted to keep lambda below 1 so they
needed to reshash 4 times. That is OK.
  12. (10%)Given the implementation of a priority queue shown below, implement a function called getBiggest() which returns a copy of the biggest element. You function cannot check more than N/2 elements. 
    #include<vector>
#include<iostream>
using namespace std;

template <class Object>
class pqueue  
{
public:
  pqueue() : size(0) {
    Object dummy;
    array.push_back(dummy); //element at 0 is dummy
  };
  
  void push(Object e) {
    Object e2;
    array.push_back(e2);
    size++;
    int hole = size;
    for ( ; e < array[hole/2] && (hole > 1) ; hole /= 2)
      array[hole] = array[hole/2];
    array[hole] = e;
  };
  
  Object top() {
    return array[1]; 
  };
  
  void pop() {
    array[1] = array[size--];
    if (size <= 0) {
      size = 0;
      return;
    }
    percolateDown(1);
  }
  void percolateDown(int hole){
    //assume this works
  };
  
  bool empty(){
    if (size == 0)
      return true;
    return false;
  };

  Object getBiggest(){ //we only need to check the last n/2
    Object biggest = array[size-1];
    for (int i=size -1; i >= size/2; i--){
      if (array[i] > biggest)
	biggest = array[i];
    };
    return biggest;
  };
  
private:
  vector<Object> array;
  int size;
};
  13. (5%)Under what conditions are Splay Trees faster than Red-Black Trees? 
     When the user frequently asks for to find() the same elements. That
is, when the 90/10 rule is in effect.
  14. (5%)Show the top-down Splay tree that results after each of the following operations are performed on it, in the order shown. 
    Insert(12)
Insert(10)
Insert(8)
Insert(5)
Insert(3)
Insert(7)
Insert(1)
Find(1)
Find(2)
Find(3)
Find(1)
Delete(3)
Delete(1)
Delete(2)

Most students got this right.
  15. (10%)Write a program that reads a file named "file" containing a number of words, each in a separate line, and then prints: (1) the number of repeated words it saw, (2) the word that was repeated most often, and (3) the 10nth word in alphabetical order. Your program must run in O(n log n) time, and your C++ must compile. Hint: use the STL.

The purpose of this question was to find out which students had arrived at an understanding of which data structures to use to solve a particular problem, the sign of a well-educated software engineer. A precious few realized that hash tables (or maps) where what was needed to solve part (1). Many used sort() or a priority_queue() to get part (3). Unfortunately, many still solved problem (1) using a brute-force double-loop method, which runs in O(n2), they received generous credit for their effort but I still need to get them to appreciate how much simpler life can be when you use the right tool for the job. After all, that is what this class is all about, learning about all the tools available to a software engineer so he can choose the right one for the job. 

#include<iostream>
#include<fstream>
#include<string>
#include<map> //if you did'nt use a map, you probably had O(n^2) time.
#include<vector>
#include<algorithm>

using namespace std;

int main() {
  const string filename("index.html");
  ifstream ifs(filename.c_str());
  map<string, int> m;
  vector<string> v;
  string s;
  while (ifs >> s)
    m[s] = 0; //set everything to 0
  ifs.close();

  string mostRepeated;
  int mostRepetitions = 0;
  int repeatedWords = 0;
  ifstream ifs2(filename.c_str());

  while (ifs2 >> s){
    if (m[s] == 1)
      repeatedWords++;
    m[s] += 1;
    if (m[s] > mostRepetitions) {
      mostRepeated = s;
      mostRepetitions = m[s];
    }
    v.push_back(s);
  }
  ifs2.close();

  sort(v.begin(), v.end());
  cout << "Number of repeated words = " << repeatedWords << endl;
  cout << "Most repeated word = " << mostRepeated << endl;
  cout << "10nth word = " << v[9] << endl;

  return(0);
}