YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPSC 427a: Object-Oriented Programming | Handout #2 | |
Professor M. J. Fischer | September 10, 2010 | |
Problem Set 1
Due before midnight on Friday, September 17, 2010.
The class demo 02-InsertionSortCpp illustrates how a C++ class and multiple source files can be used to put structure on a program. In this problem set, you will be asked to read the code carefully in order to distinguish which parts of the program support modularity, code reuse, and robustness, and which parts comprise the actual executable code. You will then be asked to repurpose the code for a different but related application.
Recall from class that the insertion sort demo does the following:
This isn’t a particularly interesting application in its own right except to serve as a unit test for verifying the correctness of the sort function.
Many people, when asked to write a program to do what is described above, would come up with a monolithic program such as you will find in 02-InsertionSortMonolith, where everything is contained in main() (which you will find in the file sort.cpp). Indeed, this program does exactly the same thing as 02-InsertionSortCpp (with one minor difference), but the code looks very different.
For this problem, I want you to print out files sort.cpp from 02-InsertionSortMonolith, and files main.cpp, datapack.hpp, and datapack.cpp from 02-InsertionSortCpp. Then for each line in sort.cpp, find whether or not that line appears in one of the other files, and if so, highlight it there. If it appears but in a slightly altered form, highlight it in a different color (or otherwise indicate that it corresponds but has been changed slightly).
Now, the lines that are not highlighted in the demo files are the ones that do not appear in the monolithic version. These lines are there for the purpose of putting structure on the code. You will see that they define subunits such as classes, function declarations, and function definitions. Now go back to sort.cpp and mark the lines that belong to the same subunit in the demo program. For example, you might use the notation “sd” to mark all of the lines in sort.cpp that came from the definition of DataPack::sortData(). I don’t care what notation you use as long as it is clear and unambiguous.
After you have identified the code-structuring parts of the demo program, write a brief paragraph on each, describing how its use contributes (or not) to the goals of modular, reusable, robust programming. Also, for any lines that appear in both versions of the code but with modifications, describe why the monolithic version of the program would not work if the lines were the same as in the demo program.
You are to modify the demo program (not the monolithic code—I do want you to succeed in getting your program to work) to change its behavior in two ways:
I have described the algorithm for expanding the DataPack. I will leave it to you to decide how this code should be integrated into the DataPack class in as clean and modular a way as possible. In thinking about where to put the code, you should ask yourself the following questions:
Common elements of two sorted lists can be found by a simple merge. Namely, compare the first element of each list. If they are the same, then a common element has been identified which should be put into the third DataPack. Discard the common element (and any duplicates) from both lists and continue. If they are different, discard the smaller element from its list and continue. Stop when either list is exhausted.
The code for carrying out the merge should go into a member function in either the DataPack class or a new class. It should not be put into main() or into a global (C-style) function. You should give some thought to this design decision and explain it in the notes accompanying your submission.
As part of your testing, you should run your code under valgrind to make sure that there are no storage leaks.
You will probably find it most convenient to submit the written part of your assignment on paper rather than electronically unless you have annotation software available. Alternatively, you can submit legible PDF scans of your paper solutions. Papers can be submitted in class, given directly to the TA, or put in my AKW mailbox, #408 (in which case you should write the date and time of submission on the paper). Remember to write your name on your papers and to staple or clip them together.
You should subit the programming part of this assignment using the submit script that you will find in /c/cs427/bin/ on the Zoo. Remember to submit the following items: