Description
Introduction and Background
This is an extra credit assignment worth 5%. (So, someone with a perfect score who also got full marks on
this could have 105 weighted points at the end, out of 100 points of required work.) It is open to anyone in
the class, but is completely optional.
The assignment is to implement some functions that operate on C++ linked lists. It’s a little more like a lab,
in that you just write those specific functions: we wrote a little interactive test program you should be able to
use to thoroughly test your code. However, I would expect it to take more time than a lab session to
complete. Unlike a lab you are required to do the work independently (i.e., no partnerships).
Like PA5, this is a multi-file program with a Makefile that uses separate compilation. We did that primarily
to give us the freedom to easily test your code using a different test driver than the one we gave you.
Hopefully between the Makefile handout (readings for Week 15), the recent lectures, and the last
assignment, you are feeling comfortable with multi-file C++ programs.
The assignment files
The files in bold below are ones you modify and submit. The ones not in bold are ones that you will use, but
not modify.
ecListFuncs.h This contains the Node struct definition for our linked lists (but not the method
implementations), commented prototypes for the functions you are required to write, and prototypes
for a few list utility functions you may want to use (the utility functions are defined in ectest.cpp).
ecListFuncs.cpp Implementation file for the the list functions required for this assignment. Stub
versions of the functions are already provided so you can compile the program right from the start.
ectest.cpp Test program for your list functions. This is a command-based program, similar to the
testlist programs we used in lecture and lab to test linked list code we did there. You probably want to
compile and run the program right away to see what it does.
Makefile A file with rules for the “make” command. There are comments at the top of the file telling
you how to use it.
README See section on Submitting your program for what to put in it. Before you start the assignment
please read the following statement which you will be “signing” in the README:
“I certify that the work submitted for this assignment does not violate USC’s student
conduct code. In particular, the work is my own, not a collaboration, and does not involve
code created by other people, with the exception of the resources explicitly mentioned in
the CS 455 Course Syllabus. And I did not share my solution or parts of it with other
students in the course.”
The assignment
Complete the implementation of the five functions longestRun, removeMultiplesOf3, insertMiddle, and
merge, described in more detail in ecListFuncs.h. Each of the first three will be worth the same amount of
credit, and merge will be worth twice as much as the others (i.e., 1 + 1 + 1 + 2). None of the functions
depend on each other, and we will test each of them separately, so you can still get some extra credit by just
implementing some of the functions.
The complete specification for these functions (i.e., prototypes + function comments) is given in
ecListFuncs.h. You put your implementations of these functions in ecListFuncs.cpp.
We provided a Makefile; to compile the code use the command:
make ectest
Grading criteria
Unlike other programming assignments this one will be graded primarily on correctness. As usual, it is up to
you to come up with thorough test cases for your code. You should be able to try out all those tests using the
test driver provided (ectest.cpp).
The other evaluation criteria is not wasting resources. For example, you will lose credit if you implement
what should be an O(n) function in O(n2), or if you have memory leaks, e.g., by doing unnecessary calls to
new, or not reclaiming memory no longer needed. There are a few additional restrictions on how you must
complete merge — see function comments for details.
We will not be evaluating your code on style, except that if your code is so messy/unreadable that we can’t
evaluate the aspects mentioned in the previous paragraph you will just lose credit for that part. (I would hope
things like using good names and consistent indenting are automatic for you by now.) You are not required to
write helper functions, but you are welcome to do so to increase code readability and reuse.
Note: you will receive no credit for this assignment if the completed versions of your functions print
anything.
README file / Submitting your program
Your README file must document which of the functions you successfully completed and known bugs in your
program (this might be in the form of test cases you tried, but that didn’t work), and any special instructions
or other information for the grader. It must also contain the signed certification shown near the top of this
document.
The submit script will check that the necessary files are present, will compile them, and will make sure there
are no cout statements in your code.
6 loagesRun
D KEE I 4 run maxKun Val
m RunLen
y ftp.fg t length Is max Runlen A4
M V ML T V T L
L
z 01 2 QI
I I
I 2 Z Z Z 3 3
a Q o d l Q Q
F it node 271 null
7 n
DI
r
multi 3
n
x x x 0 X X O
list
list next node
mode next newone
s b Fitz f 8
A
node
note In Id
