CSCI 262 Data Structures--Spring 2004

    Assignment 4

    Due at the beginning of class, Friday, March 5, 2004

    Home | | Syllabus | | Assignments | | Lecture Notes

    Programming Style: You will be graded not only on whether your programs work correctly, but also on programming style, such as the use of informative names, good comments, easily readable formatting, and a good balance between compactness and clarity (e.g. do not define lots of unnecessary variables) Create appropriate functions for tasks that can be encapsulated.

    Problem 1: Polynomial calculator

    In this problem, you will implement the polynomial calculator described in the textbook, in section 4.5. The code from the textbook is available to you in the course directory:

      ~csci262/assignments/assign4

    Copy the files from the above directory. You will have all the code for implementing the stack class, and some of the code to implement the Queue class using linked lists and the polynomial class. Your job is to complete the code in queue.cc, polyCalc.cc and polynomial.cc to generate a working polynomial calculator.

    To complete the assignment, fill in the correct code for the following function stubs:

    In queue.cc: 

      Queue :: ~Queue( )
Queue :: Queue(const Queue &original)
void Queue :: operator = (const Queue &original)

    In polynomial.cc: 

      void Polynomial :: equals_difference(Polynomial p, Polynomial q)
void Polynomial :: equals_product(Polynomial p, Polynomial q)
void Polynomial :: mult_term(Polynomial p, Term t)
We will leave the equals_quotient() function for another day!

    In polyCalc.cc: 

      void introduction()
void instructions()
void do_command( ) -- Complete the switch statement to handle '*' and '-'.
    Give a reasonable introduction and set of instructions for working this calculator.

    Note: mult_term() should work the same way as the other Polynomial functions. That is, the result should be stored in the calling polynomial. Thus, if r and s are Polynomials, and theTerm is a Term, then mult_term could be called as follows: 

      s.mult_term(r, theTerm);
    The result of multiplying r times theTerm is stored in s. To use this in equals_product, you should create a temporary polynomial to hold the result of multiplying one of the polynomials by individual terms of the other polynomial.

    Compiling your program:
    Compile your program with the following compile command:

      g++ -g -Wall queue.cc stack.cc polynomial.cc polyCalc.cc -o polyCalc

    Make sure to test your programs with some sample polynomials for adding, subtracting and multiplying to make sure the calculations are done completely. Turn in a printout of the following:

      polynomial.cc
      queue.cc
      polyCalc.cc

    Problem 2: Recursion

    Ackermann's function, defined as follows, is a standard device to determine how well recursion is implemented on a computer. 

      A(0, n) = n + 1 for n >= 0.
A(m, 0) = A(m - 1, 1) for m > 0.
A(m, n)= A(m - 1, A(m, n - 1)) for m > 0 and n > 0.

    (a) Write a recursive function to calculate Ackermann's function. Name your file ackermann.cc. The main program should prompt for 2 positive integers (m and n) and read them in, then output the return value for a call to the recursive ackermann function.

    Sample output: 

      mathcs% ackerman
Enter positive integer for m: 0
Enter positive integer for n: 0
The ackermann value is 1.
mathcs% ackerman
Enter positive integer for m: 0 
Enter positive integer for n: 9
The ackermann value is 10.
mathcs% ackerman
Enter positive integer for m: 1
Enter positive integer for n: 8
The ackermann value is 10.
mathcs% ackerman
Enter positive integer for m: 2
Enter positive integer for n: 2
The ackermann value is 7.
mathcs% ackermann 
Enter positive integer for m: 4
Enter positive integer for n: 0
The ackermann value is 13.
mathcs% ackerman
Enter positive integer for m: 3
Enter positive integer for n: 2
The ackermann value is 29.

    (b) Try running your program for m = 4, n= 2 and for m = 4, n=3. What happens? Explain why you think this happens, using a partial drawing of the recursion tree for m = 4, n = 2 to illustrate your answer.

    What to turn in:

    • Turn in a hard copy of the files:
        queue.cc
        polynomial.cc
        polyCalc.cc
        ackermann.cc

      Make sure you include a file prologue with your name, class, lecture section, the date, and the assignment number, along with a description of the file contents and their purpose. Also include appropriate comments for each of the functions you implement (with proper pre and post conditions).
    • Your written answer to the question about ackerman's function in problem 2.
    • Submit the soft copy of your program using the command:
      ~csci262/bin/submit csci262 assign4

    Home | | Syllabus | | Assignments | | Lecture Notes

    Constance Royden--croyden@mathcs.holycross.edu
    Computer Science 262--Data Structures
    Date Created: February 7, 2002
    Last Modified: February 27, 2004
    Page Expires: January 14, 2005