Course Home | Course Policies | Homework | Lab Open Hours | Programming | Labs | Schedule & Lecture Notes

Programming Assignment 05

Merging Lists

Due: Tuesday, March 29, 11:59pm

Please see the general programming webpage for details about the programming environment for this course, guidelines for programming style, and details on electronic submission of assignments.

Collaboration Policy

For this assignment, you must work individually in regard to the design and implementation of your project.

Please make sure you adhere to the policies on academic integrity in this regard.


Contents:


Overview

Our goal for this assignment is to manipulate list of integers and iterators for those lists. Given two lists, both of which are known to be sorted in non-decreasing order, your goal is to efficiently merge the elements from the second list into the first list, while ensuring that the combined result is still sorted. Because the two original lists are internally sorted, the merging process can be completed in linear time.

The source code for the entire project is already complete, with the exception of a single routine that we ask you to implement.

/**
 * Given two distinct lists, each of which are assumed to be sorted in
 * non-decreasing order, this function mutates the primary list so as
 * to include all elements of the secondary list while maintaining the
 * non-decreasing invariant.
 */
void merge(list& primary, const list& secondary)
Notice that we have designated the secondary list as immutable with the const designation. You are not to remove any values from that list, but to reinsert those values in the proper place in the primary list.

Before writing your code, think about how you will accomplish the task. It may help to consider the process you might use if doing this with lists written on paper. You might imagine placing one finger at the beginning of the first list and one finger at the beginning of the second list. Now, you should be able to advance the fingers in a way, ensuring that items are copied from the second list into the proper place in the first list as you go. To implement this strategy, the iterator classes can be used to represent the idea of a finger moving through a list.

Advice: if you are having trouble, always consider that a problem can be fixed by simplifying your code rather than complicating it. There exists a remarkably simple solution to this assignment. In fact, the merging process is described on page 491 of the text, due to its role in the larger context of designing an algorithm for sorting elements. You may skim that material from the book for general guidelines regarding the merging process, but the implementation details for this assignment vary greatly from the coverage in the book. In particular, the description in the book creates a third list as the result, rather than mutating one of the original lists. Furthermore, the book bases its description on their Sequence ADT rather than the stl::list interface.


Limitations

Our goal for this assignment is to have you get used to using the standard library list class and its iterator and const_iterator classes for low-level manipulations of a list. The list class includes some higher-level functionality including, as it happens, a function to merge a second list into a first. Needless to say, you are not allowed to use that method for this assignment (nor should you be using the sort method). You should be primarily relying on the insert method to add individual elements to your list.


Files We Are Providing

All such files can be downloaded here.


Using Our Driver

The executable MergeTest is a driver which will handle reading the input, creating the initial lists, calling your routine, and then outputting the merged result.

You will need to design your own input; in particular, I recommend constructing a simpler merging example when starting the project, since you may need to debug initially and may not want to run the full test code. Your full test code should consider several variations and ways to "trick" the merger code, so be sure to test exhaustively and think about how things could be broken!

The expected format for input is as follows:

You will notice that this format allows you to specify a test file which involves many different merges, as demonstrated in the following example of a properly formatted input file.

5
9
12
1000
4
10
11
15
1000
3
4
1000
1000
1
5
5
8
1000
2
8
10
1000
-1

The driver will create the two lists A = {5, 9, 12} and B = {4, 10, 11, 15}, and then invoke merge(A,B). Hopefully this results in A = {4, 5, 9, 10, 11, 12, 15}.

After that, it will create two lists A = {3, 4} and B = { }, and again call merge(A,B) (which hopefully results in A = {3, 4}).

Then it will merge {1, 5, 5, 8} and {2, 8, 10}, hopefully producing the list {1, 2, 5, 5, 8, 8, 10}. After this, it exits.

By default, the driver reads input from the keyboard. However, if you would like to have the driver read input from a text file, give the filename as a single argument when starting the program (as was done in an earlier programming assignment)

The driver will output the sorted result. Your code is expected to succesfully sort all the inputs given in our test file.


Files to Submit


Grading Standards

The assignment is worth 10 points. Eight points will be awarded based on our own evaluation of your assignment and the readme file. One additional point will be awarded fractionally based on how well your program performs on other students' test inputs. The final point will be awarded fractionally based on how well your test input fools other students' flawed programs.