20-ECES-228-001 Data Structures Fall 2007

Homework Assignment Number 2
Linked Lists and Stacks

Due: October 5, 2007
Submit source code implementing the extended pqueue class and solution to the powers problem to xxxxx@email.uc.edu

Rationale:

    You will exercise your understanding of the implementation of ordered lists called Priority Queues using arrays. You will use a Stack ADT to solve a fundamental computational problem: finding positive integer X raised to the power Y where Y is a positive integer.

Homework Problems:

   
  1. Extend the PQueue class, implemented in pqueue.h and pqueue.cc and requiring node.h and node.cc, to include a new method findmax which returns the object in a priority queue of greatest value, where value is determined by a method called value which is to be supplied by the user in a class of the following prototype: 
       class valueA : public valueFunc {
    public:
      long long value (void *object);
   };
    where class valueFunc is prototyped in funcs.h. If no valueA object is supplied, or if there are no elements in a PQueue object, findmax returns NULL. The method findmax does not remove any objects from the PQueue container to which it is applied.

    A description of the PQueue class is given below.

    Send the grader files pqext.h, containing the full specification of your class extension, call it class PQExt, and pqext.cc which implements the class. Your code should link with the supplied PQueue class and a main (say in hw2a.cc) testing it, as follows: 

       g++ -c pqext.cc
   g++ -c pqueue.cc
   g++ -c hw2a.cc
   g++ hw2a.o pqueue.o pqext.o -o hw2a

    Observe the following:

    1. If no new objects are inserted into the priority queue the maximum object remains maximum as objects are removed until it is removed. That fact makes this assignment extremely simple.
    2. The first object entering an empty priority queue immediately becomes the maximum object.
    3. In this example: 
         long long valueA::value (void *object) { 
      return (long long)*(int*)object; 
   }
	
   PQExt *pqe = new PQExt(new valueA());
   pqe->insert(new int(45));
   pqe->remove();
   pqe->insert(new int(12));
   int *ptr = (int*)pqe->findmax();
   cout << *ptr << "\n";
      The number 12 should be output.
  2. Implement a solution to the Powers Problem (see below) using the Stack class implemented in stacker.h and stacker.cc and Big Integers which are implemented in bigint.h and bigint.cc.

    Send the grader files power.cc and power.h which implement class Power with method char *pow(int x,int y) which returns a bigint which has value xy. It should link with stacker.cc and a file, say hw2b.cc, using it as follows: 

       g++ -c bigint.cc
   g++ -c node.cc
   g++ -c power.cc
   g++ -c stacker.cc
   g++ -c hw2b.cc
   g++ hw2b.o power.o stacker.o bigint.o node.o -o hw2b

Description of class PQueue:

    A PQueue object is a container for any type of object having some defineable notion of "value". A user of the PQueue class defines a value function and passes it as an argument to the PQueue constructor upon object creation. The value function takes a pointer to an object as input. Its output is a long representing the value of input object.

Objects may be inserted into a PQueue container using the method 

    void insert(void *object);
Objects may be removed from a PQueue container using the method 
    void *remove();   // Return value is a pointer to the removed object
When remove() is invoked, the object of lowest value in the container is removed and returned. The final method available in this class is the following 
    bool empty();
which returns true if and only if the container is empty.

Example:

The following sample hw2a.cc file: 

    #include <iostream>
    #include "pqext.h"
    #include "funcs.h"
    using namespace std;

    class valueA : public valueFunc {
    public:
       long long value (void *object) { return (long)*(int*)object; }
    };

    int main () {
       PQueue *lst = new PQueue(new valueA());
       lst->insert(new int(34));
       lst->insert(new int(12));
       lst->insert(new int(9));
       lst->insert(new int(22));
       lst->insert(new int(55));
       lst->insert(new int(2));
       lst->insert(new int(3));
       lst->insert(new int(16));
       cout << *(int*)(lst->remove()) << " "
            << *(int*)(lst->remove()) << " "
            << *(int*)(lst->remove()) << "\n";
    }
outputs the numbers 2, 3, 9 when linked to pqueue.o.

Implementation details of PQueue:

    A PQueue container has one array: objects of type void*[], each element of which is a pointer to a contained object. The arrangement of objects in objects after insertion and removal operations has the following properties: 1) all contained objects are pointed to by elements objects[0] to objects[n-1] where n is the number of contained objects and n < size; 2) for any i from 0 to n-1, if 2*i+1 < n then value(objects[i]) < value(objects[2*i+1]) and if 2*i+2 < n then value(objects[i]) < value(objects[2*i+2]). For example, the following array values satisfy the above (the number on the extreme left is value(objects[0])): 
 
    5 23 13 25 67 14 15 33 78 70 16

Using pqueue.cc:

    Build, say hw2a.cc as above. Be sure to include pqueue.h. Compile using the following: 
    g++ -Wall -c pqueue.cc
    g++ -Wall -c hw2a.cc
    g++ -Wall hw2a.o pqueue.o -o hw2a
then run hw2a.

Powers Problem:

    Given a positive number X and a positive integer Y, compute X raised to the Y power in a very small amount of time (log(Y) multiplications maximum).

Example:

8 raised to the power 5 is 32768.

Method:

input: A positive number X and a positive integer Y
output: X raised to the Y power

    1. Create stack S.
    2. While Y is greater than 1 do the following:
    2a.   Push Y mod 2 onto S.
    2b.   Y := Y div 2.
    3. P := X.
    4. While S is not empty do the following:
    4a.   P := P*P.
    4b.   Pop S and put the result in Z.
    4b.   If Z=1 then P := P*X.
    5. Return P.

Services provided by the Stack class:

    
    // Example
    Stack *stack = new Stack(NULL);  // No display of stack contents expected
    ...
    stack->push(new int(10));     // Push an object onto the stack (example)
    ...
    int *a = (int*)stack->pop();  // Pop and return an object (example)
    ...
    int *b = (int*)stack->peek(); // Only look at the top stack object (example)
    ...
    if (!stack->empty())...       // Test whether the stack is empty

Services provided by Big Integer functions:

    All big integers are merely character strings of arbitrary length where each character is an ascii counterpart to a digit from 0-9. Negative numbers are not implemented (OK, so they should be called big non-negative integers). The following are examples of their use as provided by the functions in bigint.cc: 
   char *n = toBigInt(6754);  // turns the int 6754 into a string "6754"
   ...
   char *m = addBigInt(n,"654");  // adds two big integers
   ...
   char *p = multiplyBigInt(m, n); // multiplies two big integers

Using bigint.cc and stacker.cc:

    Create a file called power.cc and add a Power class to that file. The class has only the null constructor and one method of two arguments with the following protoype: 
    char *pow (int x, int y);
The homework assignment is to code this method to return x raised to the power y. Create power.h accordingly. The following file, named hw2b.cc, shows how to use the Power class: 
    #include <iostream>
    #include "power.h"
    using namespace std;

    int main (int argc, char **argv) {
       if (argc != 3) {
          cerr << "Usage: " << argv[0] << "  \n";
          exit(0);
       }

       int x = atoi(argv[1]);
       int y = atoi(argv[2]);

       Power *p = new Power();
       cout << x << "**" << y << " = " << p->pow(x,y) << "\n";
    }
When invoked with the command line hw2b 453 23 the result is 
    453**23 = 12310016818803551465696882268112889772096056731865941383954477

To compile use the following: 

    g++ -Wall -c hw2b.cc
    g++ -Wall -c stacker.cc
    g++ -Wall -c bigint.cc
    g++ -Wall -c power.cc
    g++ -Wall -c node.cc
    g++ -Wall hw2b.o stacker.o bigint.o power.o node.o -o hw2b