Programming Assignment 1
Due on April 28, Friday, 11:59pm, 2000
Implement the algorithms for Question 4 in Homework Assignment #1 in
C++ using linked lists. Each node of a linked list represents a
term in a polynomial and should contain the information on the
floating point value of the coefficient and the
integer value of the degree
of each term.
(1) input file format
Take from an input file the values of coefficients and degrees for the
terms of two polynomials. Your main function must take the "argc and argv"
parameters so
that the user may pass the input file name from a commandline.
The format in the input file is as follows:
A value of the coefficient of a term is followed by a value of the
term's degree enclosed in a parenthesis. Then a comma follows except
at the end of the list. The beginning and the end of the sequence of
the terms of each polynomial are signaled by an opening bracket and an
closing bracket, respectively. For example, two polynomials 2x^4 +
3.5x^2 + 5 and 1.2x^6 + 2x + 6.7 may be represented in the input file
as:
[ 2(4), 3.5(2), 5(0) ]
[ 1.2(6), 2(1), 6.7(0) ].
By the way, 0 may be represented by [ 0(0) ].
(2) output
Print the sum of the two input polynomials and their product to the
screen in the same format as the input polynomials.
(3) Dynamic allocation of pointers
A polynomial could also have been represented by an
array. Nonetheless, the primary reason for using a linked list,
opposed to an array, to represent a polynomial is to conserve memory
spaces. In addition, you may need in your program some pointers
pointing to some nodes of the linked list, depending on the algorithm
you employ. Likewise, you are not allowed to pre-allocate excessive
number of pointers at compile time but are required to allot just as
many pointers as necessary at runtime. Consider how to resolve this
problem. Dynamically allocating separate individual pointers will not
be helpful. They need to be somehow linked together or placed in an
array in order to be useful.
NOTE:Be sure to free up any dynamically allocated memory when the
alloted memory is no longer needed.
(4) Target running time
Addition: O (m + n)
Multiplication:
Try to achieve O( mn * lg m ) where m denotes the number of terms
in one input polynomial, n denotes the number of terms in the
other polynomial and m <= n. Of course, if your program can get better than
that, that's even better.
(5) Makefile
Provide a makefile so that the reader only needs to type "make" in the
command line to compile your program. With no functional makefile, you
will get zero point. The makefile should include a command to delete
all the object files, backup files ( with '~' at the end ), core and
the executable file of your program with the "force" option. That
command should be placed under the "clean" dependancy target. The
Following is an example you may use.
clean:
rm -rf *.o *~ core your_exec_file_name
(6) Comments/Style
1. The readability of your program also counts. Use a proper style and
add comments where appropriate. Excessive comments that interrupt the
readability, however, are also subject to penalty. Use sound judgement
and common sense. Comments in the following example will be
considered inappropriate and result in points deducted.
int main()
{
// character variable
char ans;
// integer variable
int num;
Those comments are unnecessary and better be left out. More
appropriately, they should be commented as follows.
int main()
{
// stores the user choice--'continue/do not continue'
char ans;
// stores user input
int num
2. The following information must be typed at the left top corner of
each of your files:
Your name
student ID number (if you prefer, the last four digits are fine)
your login
your lab section number
The assignment number (e.g. as1)
due date
(7) Readme file
Write a readme file, no more than a page long, and describe the run
time analysis of your program. Be succinct. The shorter, the better.
(8) Program Modularity
Make your program modular. Write separate files for the main program,
prototypes of your functions, classes, etc, and their definitions. So
you are most likely to have at least three files.
(9) Name of the executable
The executable name of your program must be
"pcalc". This is for the
sake of the reader. If everyone uses the same executable name, the
reader doesn't have to waste her/his time to figure that out. To
generate an executable with a desired name, you need to use -o option
in your command. If you don't know how to write a makefile for that
purpose, ask your TA.
(10) Tentative grading scheme
The following is the breakdown of the scores. Please be reminded that
this scheme is subject to change, and the purpose of making known this
grading scheme is just to give you a rough idea regarding how your
program will be graded.
Correct result printed in a right format: 25 pts.
Accomplishing a target running time: 20 pts.
Economical usage of memory spaces: 10 pts.
Freeing up dynamically allocate memory: 5 pts.
Modular program / readability: 5 pts.
Style/comments: 10 pts.
readme file: 10 pts.
correct exec file name / cleanup command in makefile: 5 pts.
others (e.g. closing the input file, etc): 10 pts
-------------------------------------------------
TOTAL: 100 pts.
NOTE: If your program uses other than linked lists to represent
the polynomials, your will receive no credit.
last upadated Apr. 13, 4:21am.
Further updated Apr. 26, 10am
Back to Sample Assignment