EECE 352: Exam 1

Fall 1999

Name:________________________________ SSN:_____________

(20%) The program below defines four classes, some of which inherit from others. There is also a main() which calls the print() member function on some objects. After each call to the print() function you should write the output that appears as a result of that call. HINT: The program has no compiler or runtime errors.


#include<iostream>
using namespace std;

class A { //class A
  int val;
public:
  A(int x) : val(x) {};
  A() : val(1) {};
  virtual void print() { 
    cout << "Class A:" << val << endl;}
};
 
class B : public A { //class B
public:
  B(int x) : A(x) {};
  B() : A(2) {};
  virtual void print() {
    cout << "Class B:";
    A::print();
  }
};

class C : public B { //class C
  int bval;
public:
  C(int x, int y) : bval(x), B(y){};
  C() : bval(3), B(7) {};
  virtual void print() { 
    cout << "Class C: " << bval << " ";
    B::print();
  }
}; 

class D : public A { //class D, it inherits from A
  int dval;
public:
  D(int x) : dval(x), A(4){};
  D() : dval(9), A(2) {};
  void print() { 
    cout << "Class D:" << dval << " ";
    A::print();
  }
};

//After each print() statement, write what gets printed out.
//This program compiles and runs without any errors.

int main() {
  A a1;
  a1.print();



  A a2(77);
  a2.print();



  B b1;
  b1.print();


    
  C c1(11, 22);
  c1.print();



  C c2;
  c2.print();



  D d1;
  d1.print();
  return 0;
}

Answer:
Class A:1
Class A:77
Class B:Class A:2
Class C: 11 Class B:Class A:22
Class C: 3 Class B:Class A:7
Class D:9 Class A:2

(10%) Given the classes defined in Problem 1 have been included, will the following code compile? If yes, then what will it print when it runs. If not, then why does it fail to compile?

  A aa;
  B bb;
  C cc;

  A *all[3];
  all[0] = &aa;
  all[1] = &bb;
  all[2] = &cc;

  for (int i = 0; i<3;++i){
    all[i]->print();
  };

 

It works. You will notice that its the SAME code you used on PS1. It
prints:

Class A:1
Class B:Class A:2
Class C: 3 Class B:Class A:7

(5%) In the class A, as shown in Problem 1, you can see that the print() function is defined as virtual. (A)What does the virtual keyword do? (B)If the virtual keywords from Problem 1 were taken out, would the output from Problem 1 sitll be the same? would the output from Problem 2 still be the same? (Yes or No).



A The virtual keyword states that the function can be overidden by a
similar function defined by a class that inherites from this one.
It declares that we should use dynamic binding with this function.

B If we removed it the program would still compile, however, the for
loop from problem 2 would have output of:

Class A:1
Class A:2
Class A:7

since we would be using static binding.

(5%) What is an abstract class? Implement a simple abstract class with one member function.


An abstract class is one that cannot be instantiated. They are defined
by including one pure abstract member function, as shown here:

class Abstract {
public:
  Abstract(){};
  virtual print() = 0;
};

(15%) For each one of the functions below give the big-O running time in terms of N.

void foo(int N){
  int c=0;
  for (int i=0; i<5*N; i++)
    c++;
  return c;
}

O(N)

void bar(int N){
  int c=0;
  for (int i=0; i<N*N; i++)
    for (int j= i; j< N; j++)
      c++;
}

O(N³)

void spaz(int N){
  int c=0;
  for (int i = 5*N; i > 1; i = i/2)
    c++;
}

O(log N)

void google(int N){
  int c=0;
  for (int i = 0; i<N; i++)
    for (int j=0; j<N*i; j++)
      c++;
}

O(N³)

void dilbert(int N){
  int c=0;
  for (int i =0; i< N; i+= N/5)
    c++;
}

O(1)

(10%) If a program that executes in O(n²) time, takes 5 seconds to process an input of size n=10. How many seconds will it take to process an input of size n=100? Show your work.
```
5 = c * 10²
c = 5/100 = .05

T(100) = .05 * 100² = .05 * 10000 = 500
```

(10%) Determine how long, in big-O notation, the program below will take to execute.

int recursive(int N) {
  if (N < 1)
    return N;
  int r=0;
  for (int j=0 ; j<N*N; j++)
    r += j;
  for (int i = 0; i< 10; i++)
    r += recursive(N/5);
   return N;
}


T(N) = O(N²) + 10*T(N/5)
Using Theorem 7.5 from the book.
 where A=10, B=5, k=2
T(N) = O(N²)

(10%) You have been given the task of writing a database server. Your server should take requests and then handle them on a first-come first-serve basis.(A) What STL container would you use to store requests (explain)? What are the basic operations that we can perform on this container? show some code. (B) If the requests had to be handled based on the rank (in the company), of the person who submitted it, what containter would you use?
```
A You would use a queue, of course, which implements the push and
pop operations. You use it because you can push requests as they
come in and pop the one that came in first. That is, it implements
a FIFO order. You can find code examples in the STL-queue.cc file in the
handouts.

B You would use a priority queue where the actual priority of the
request would be a function of the person's rank.
```

(10%) The table below shows the original order of elements in an array. You are to apply shell sort to these elements and show the resulting values after each of the k-sorts has executed. This table is similar to Figure 8.4 from the book.

Original	34	11	22	98	1	41	83	20	14	85	21	64	30	3	4
After 7-sort	4	11	22	21	1	30	3	20	14	85	98	64	41	83	34
After 3-sort	3	1	14	4	11	22	21	20	30	41	83	34	85	98	64
After 1-sort	1	3	4	11	14	20	21	22	30	34	41	64	83	85	98

(5%) Write a program that asks the user for a series of words. Your program should continue to ask for another word until the user types in the word "END". After the user types "END" your program should print the first three words, in alphabetical order, from the set of all words the user entered. You should use the appropiate STL containers and algorithms. Do not forget the #includes!
```
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
  vector<string> names;
  for (;;){
    string n;
    cin >> n;
    if (n == "END")
      break;
    names.push_back(n);
  }

  sort(names.begin(), names.end());
  for (int i=0; i < 3; i++)
    cout << names[i] << endl;
  return 0;
}
```

(Not Used) You are about to start writing a program for a big software company. In various places in the program you will need to sort data. Give two reasons why you might prefer to use the STL sort, and two reasons why you might want to implement your own sort function.


Use STL sort:

1- Because its already implemented so I don't have to waste time.

2- Because its a standard, so it will be easier for others to
understand my program.

3- Because it goes well with pretzels.

Use my own sort:

1- Because the data is almost sorted, therefore I should use insertion
sort. Because of peculiarities in the order of the data, sorting
method X is better.

2- Because of backwards compatability, I cannot use the STL
algorithms. Because I cannot place the elements to be sorted in a
container.

3- Because I like to make life difficult for myself.