433-253 Algorithms and Data Structures

Project 1

Aim

The aim of this project is for you to get experience with writing ADTs using advanced features of ANSI C and non-trivial data structures.

Outline

In this project, you are required to modify some ANSI C programs to improve their functionality and efficiency by using appropriate algorithms. C supports addition and multiplication to be performed only on integers with limited precision. For example the size of a regular int may be 32 bits and hence the variable int cannot handle values greater than 2^32. The project has two parts. In the first part of the project you are required to extend the features of C to create an ADT which supports addition and multiplication for arbitrarily long integers. You are required to conceive a proper data structure and also general algorithms for addition and multiplication of long integers. Your program should be efficient. The second part of the project is related to an application of a stack ADT for postfix evaluation program. The use of the stack ADT for evaluation of postfix expression is discussed in Section 4.3 of Algorithms in C, Sedjewick.

Your task

Part 1: Long integer arithmetic ADT

Your task is to develop an ADT that allows users to perform addition and multiplication of arbitrarily long integers. You are given an implementation where an arbitrarily long integer is represented by an array of ints. This program has a limitation that array length is fixed. You are required to remove this restriction by employing a linked list data structure for arbitrarily long ints. You should use the following definition for linked list node.


typedef struct node* link;
struct node { unsigned short int item; link next; };

The details about ADT are given in Chapter 4 of Algorithms in C, Sedjewick. Specifically;

You should produce large.c containing your implementations of functions large_add and large_mul (these filenames must be used).
The functions should take two nodes pointing two long numbers as arguments and should return the pointer of the result.
You should also produce a file large.h (this filename must be used) describing the data structures and the large ADT interface.
Your implementations should be efficient which means that your solutions should not take more time than the prototype implementation.

A prototype implementation (array version) with a test procedure is available through this link(www.cs.mu.oz.au/253/large_pro.c). Note that the prototype implementation may not be robust and may not follow many good styles of ANSI C(for example the functions returns nothing). The prototype functions are given below.


#define MAX_LEN         40
#define TRUE		1
#define FALSE		0

#define int_ln		16   /* size of short int in bits */
void lrg_int_add(X,Y,R)
short unsigned X[]; short unsigned Y[]; short unsigned R[];
{
  int k;
  long int temp, partial_sum,carry;
 
  carry = 0;
  for (k = 0; k < MAX_LEN-1; k++) {
      temp = carry + X[k] + Y[k];
      R[k] = (short unsigned) temp;
      carry =  temp >> int_ln;
  }
   partial_sum =  carry +  X[MAX_LEN-1] + Y[MAX_LEN-1];
   R[MAX_LEN-1] = (short unsigned) partial_sum ;
  carry = (short unsigned) partial_sum;
}

/**     Multiple Precision Multiplication 
** Inputs
		multiplier[MAX_LEN]
		mulitplicand[MAX_LEN]
	Output
		Product[MAX_LEN]				    **/

void lrg_int_mult(multiplier,multiplicand,result)
unsigned short int multiplier[]; unsigned short int multiplicand[];
unsigned short int result[];
{
int i,j,k;

long unsigned temp,partial_sum,carry;

for (i = 0; i < 2*MAX_LEN; i++)
    result[i] = 0;

for (i=0; i < MAX_LEN; i++) {
    carry = 0;
    for (j=0; j < MAX_LEN; j++) {
	partial_sum = (long unsigned) multiplier[i]*multiplicand[j];
	temp = (long unsigned) result[i+j] + partial_sum+carry;
	result[i+j]= (unsigned short int) temp;
	carry  = temp >> int_ln;
    }
    result[i+j] += carry;
  }


} /* end of lrg_int_mult */

Part 2: Post fix evaluation program

This is an exercise in using an ADT to realize some application. Your task is to extend the the functionality of the postfix evaluation program (Program 4.2, posteval.c) given in the Algorithms in C by Sedjewick to expressions involving arbitrarily long integers. The program is available at (www.cs.mu.oz.au/253/proj1/posteval.c). For this purpose you should use the ADT you have developed in Part 1. You also need to modify the stack ADT to suit your needs and are free to use any implementation of the stack. The text book (Algorithms in C by Sedjewick) provides many implementations of stack. Your implementation should be in the file postfix.c (this filename must be used) You should include all the necessary stack implementations and interface details in your file postfix.c . Program 4.2 of Algorithms in C by Sedjewick is given below:

-----
void STACKinit(int);
 int STACKempty();
void STACKpush(Item);
Item STACKpop();
-----
#include stdio.h
#include string.h
#include "Item.h"
#include "STACK.h"
main(int argc, char *argv[])
  { char *a = argv[1]; int i, N = strlen(a);
    STACKinit(N);
    for (i = 0; i < N; i++)
      {
        if (a[i] == '+')
          STACKpush(STACKpop()+STACKpop());
        if (a[i] == '*')
          STACKpush(STACKpop()*STACKpop());
        if ((a[i] >= '0') && (a[i] <= '9'))
          STACKpush(0);
        while ((a[i] >= '0') && (a[i] <= '9'))
          STACKpush(10*STACKpop() + (a[i++]-'0'));
      }
    printf("%d \n", STACKpop());
  }
-----

Questions and answers

Questions and answers pertaining to the project will be available in QandA.html and will be considered part of the specification of the project.

Marking

This project is worth 8% of the final mark for the subject. Marking will be based on the overall quality of code (correctness, reasonable efficiency, documentation, robustness, etc) and whether the specified algorithm has been implemented.

Submission

You will need to submit your version of large.h, large.c and postfix.c (this filename must be used). Submit using the command submit 253 1 on a Computer Science machine by 4:00PM on Thursday 11 April. Verify your submission using the command verify 253 1. Late submissions will incur a penalty of two marks per day (or part thereof) late. If you cannot submit on time you should contact the tutor in charge or lecturer at the soonest possible opportunity (this generally means before the deadline). Late submission will be done using the command submit 253 1.late

Important Note

You are reminded that all submitted assignment work in this subject is to be your own individual work. You should not exchange written material, either on paper or electronically, and should not let other students copy your program. Students submitting the work of others for assessment will be penalised by the Department, and risk prosecution under the University's Discipline Regulations.