Test 1: CPS 100, Review Spring 2004

February 9-10, 2004

struct ListNode
{
  string info;
  ListNode * next;

  ListNode(const string& s, ListNode * ptr)
    : info(s), next(ptr)
  { }
};

PROBLEM 1 :   (O-O-Ohno (20 points))
Part A (3 points) Consider the function addup below. The call addup(40) returns the value 785.

int addup(int n)
// post: return value based on n    
{
    int sum = 5;
    for(int k=0; k < n; k++) {
        sum += k;
    }
    return sum;
}

What is the complexity (in terms of runtime) of the call addup(N). Use big-Oh notation and justify your answer briefly.

Part B (3 points)

Consider the function counter below. The call counter(2,1025) returns the value 11.

int counter(int n, int limit)
{
    int count = 0;
    int value = 1;
    while (value <= limit) {
        value *= n;
        count++;
    }
    return count;
}

What is the complexity (in terms of runtime) of the call counter(k,N). Use big-Oh notation and justify your answer briefly. Your answer should use k and/or N.

Part C (4 points)

What is the complexity of the call calculate(N) for the function shown below. Use big-Oh notation and justify your answer briefly.

int calculate(int n)
{
    int prod = 1;
    for(int k=1; k <= n; k++) {

        prod = prod * prod;
        for(int j=1; j <= k; j = j*2) {
            prod *= j;
        }
    }
    
    return prod;
}

Part D (10 points)

A N-list stores integers, the integers are stored in non-decreasing order, each integer k occurs exactly k times and N is the largest integer in the list. For example, a 4-list is (1,2,2,3,3,3,4,4,4,4) and a 5-list is a 4-list with (5,5,5,5,5) appended to the end.

Using the standard Node definition listed at the front of the test and replacing strings with ints, write MakeNList.

Node* MakeNList(int n)
// precondition: n > 0
// postcondition: returns the N-List

What is the Big-Oh of your implementation of MakeNList in terms of n?

The function isEqual below returns true if the two linked list parameters contain the same values in the same order and false otherwise. It is correctly implemented.

For example, given the lists below the call isEqual(list1,list2) evaluates to true, the call isEqual(list2,list3) evaluates to false (the lists don't contain the same values) and the call isEqual(list2,list4) evaluates to false (the values aren't the same).

list1 = ("apple", "banana", "fig", "lemon")
list2 = ("apple", "banana", "fig", "lemon")
list3 = ("apple", "banana", "fig")
list4 = ("apple", "banana", "FIG", "LEMON")

bool isEqual (ListNode * lhs, ListNode * rhs)
// pre:  lhs and rhs are singly linked lists, possibly empty
// post: returns true if lhs and rhs have same values in same order
//       returns false otherwise
{
    if (lhs == 0 && rhs == 0) return true;      // both empty
    if (lhs == 0 && rhs != 0) return false;     // lhs shorter, not equal
    if (lhs != 0 && rhs == 0) return false;     // rhs shorter, not equal

    return (lhs->info == rhs->info && isEqual(lhs->next, rhs->next));
}

  string left = LowerString(lhs->info);
  string right = LowerString(rhs->info);
  return (left == right && isEqual(lhs->next, rhs->next));

To avoid re-writing the function and creating a new function with each new kind of comparison, you will implement a generalized version of the function that has a third parameter. The third parameter is used to compare two nodes to determine if they are equal. It is a pointer to an object that does the comparisons. Using inheritance callers can create new Comparator subclasses and use the generalized isEqual function.

// compare two strings for equality, let subclasses define what equals means

class Comparator
{
  public:
    virtual ~Comparator () {}

    // return true if two strings are the same, false otherwise

    virtual bool isSame (const string& lhs, const string& rhs) const = 0;
};

class Equal : public Comparator
{
   public:
    virtual bool isSame(const string& lhs, const string& rhs) const
    {
        return lhs == rhs;
    }
};

int main()
{
    ListNode * lhs = makeSomeList();
    ListNode * rhs = makeAnotherList();
    Comparator * comp = new Equal();

    if (isEqual(lhs,rhs,comp)) {
       cout << "lists are the same" << endl;
    }
}

What is the purpose of the C++ keyword virtual in the declaration above?

Part B (4 points)

Write a subclass of Comparator named SameLength that returns true if both string parameters have the same length, and false otherwise. For example, using this Comparator should result in the lists below being compared as ``equal'' since the strings stored in corresponding nodes have the same lengths.

list1 = ("apple", "banana", "fig", "lemon")
list2 = ("lemon", "grapes", "yam", "mango")

Write the code below.

class SameLength : public Comparator
{
  public:
    // return true if both strings have the same length
    virtual bool isSame (const string& lhs, const string& rhs) const
    {
        // add code here




    }
};

Write the generalized version of the function isEqual below that returns true if the corresponding values within the two lists compare as equal according to the comparator parameter and false otherwise. See the call to this generalized function above for how it would be called.

bool isEqual (ListNode * lhs, ListNode * rhs, Comparator * comp)
// pre:  lhs and rhs are singly linked lists, possibly empty
// post: returns true if lhs and rhs have nodes that contain equal values
//       as defined by comp, false otherwise
{
    if (lhs == 0 && rhs == 0) return true;    // both empty
    if (lhs == 0 && rhs != 0) return false;   // lhs shorter
    if (lhs != 0 && rhs == 0) return false;   // rhs shorter

     // complete function here
    

}

class SortedWordStats : public WordStats
{
  public:
    int uniqueCount(tvector v)
    // post: returns number of unique/different elements in v
    {
        sort(v.begin(), v.end());  // v is now sorted
        int count = 0;
        string last = v[0];
        for(int k=1; k < v.size(); k++){
            if (v[k] != last){
                last = v[k];
                count++;
            }
        }
        return count;
    }
};

Write a function that returns the number of unique/different strings in a sorted linked-list. For the list below countUnique should return 3 since there are three different strings in the list.

    ("dog", "dog", "elf", "frog", "frog", "frog", "frog")

For full credit your function must execute in O(n) time for an n-node list.

int countUnique(ListNode * list)
// pre: list is sorted, list is NULL/0 terminated, no header node
// post: returns # different/unique strings in list
{

}

  ("dog", "elf", "frog")

You do not need to return removed nodes to the heap. Note that list is not passed by reference.

  void removeDups(ListNode * list)
  // pre: list is sorted
  // post: list is sorted, but contains no duplicates