Assignment 5
Assignment 5 is worth 5% of your final mark, and is due by Saturday April 7 Wednesday April 11 at 11:59 pm. Late submissions will not be accepted, barring exceptional circumstances.
There are two three Practical Lab sessions for this assignment (Tuesday March 27, Tuesday April 3, and Tuesday April 10).
This assignment should be submitted via MarkUs.
Your assignments must follow the style guidelines discussed in the course style guide. Failure to do so may result in deductions. There are new requirements for this assignment.
You should not make any changes to the starter code other than in the specified locations.
Announcements and Updates
April 7: Updated information about newly added Practical Lab session on April 10.
April 6: The tester is now available. It can be run using the Makefile.
Overview
This assignment is a program that will help to solve a logic puzzle. In this puzzle, you are given a list of numbers and a target value, and you must determine the largest sum less than or equal to the target value that can be created from a subset of those numbers, and the subset (or subsets) that add up to that sum. For example, if you were given the list of numbers {1, 2, 5, 6} and a target value of 6, the largest sum that is less than or equal to the target value of 6 is 6, and that sum can be created by the subsets {1, 5} and {6}.
The program uses recursion and linked lists to generate all the possible subsets of the list of numbers, and then filters that list to determine the optimal subset. Details of this algorithm are discussed below.
Because one of the goals of this assignment is to practice recursion, certain portions of this assignment that involve repetition must be written using recursion. All sections that must be written with recursion are clearly identified as such. You may use recursive helper functions. A few sections of this program may be written using iteration, and are clearly marked as such. Any submission that uses iteration to solve one of the recursive functions will receive a mark of 0 for that function and any associated test cases. (The use of iteration is defined by the presence of a for, while, or do while loop either in the function itself or in a non-library helper function.)
The Puzzle
As indicated, there are two inputs to this puzzle: a list of numbers, and a target value. The correct solution to the puzzle involves a list of one or more subsets that satisfy the required criteria. In order to solve the puzzle, you need to determine the largest sum that is less than or equal to the target value that can be created from a subset of the numbers. Then, you need to print out all of the possible subsets that add up to that sum.
As another example, if the list of numbers was {1, 2, 3, 4, 5} and the target is 3, then the largest sum that is less than or equal to 3 that can be created from those numbers is 3. This sum can be created with {3} and with {2, 1}, so the program would print out:
3
2 1
If the target value was 100, then the largest sum would be 15, which can be created with {1, 2, 3, 4, 5}. If the target value was 2, then the largest sum is 2, which can be created with {2}.
There is no algorithm that can elegantly solve this puzzle. We can't, for instance, simply take the largest numbers in the subset and add them together (a type of algorithm that would be called a "greedy algorithm"), since that's not guaranteed to give us the best answer. If we had the numbers {3, 4, 6} and the target value 7, then taking the largest number would give us a subset of {6}, instead of the correct answer of {3, 4} (which add up to a total of 7). So, we will take a brute-force approach. We will first generate a list of every possible subset (of every possible length) of our initial numbers. Then, we will go through that list and figure out the sum that is closest to the target value. Finally, we will go through our list a second time, and pick out any subsets that have this sum. This is not particularly efficient, but is fine for small sets of numbers.
Default Number List
To save you typing, the program has a default number list ({1, 2, 4, 5, 8, 12, 15, 21}, defined in DEFAULT_NUMBERS), which means that you don't need to reenter the list of numbers each time you run your program. When started, the program asks if you want to use the default list; if you answer no, then you are prompted to enter the number list. In either case, you need to enter a target value each time.
Input and Output
Here are some sample sessions with the program:
Use default set of numbers? [y/n] y
Enter target value: 9
The subset(s) closest to the target value are:
5 4
8 1
Use default set of numbers? [y/n] y
Enter target value: 150
The subset(s) closest to the target value are:
21 15 12 8 5 4 2 1
If the user decides not to use the default set of numbers, the program prompts the user to enter up to MAX_NUMBER_OF_NUMBERS numbers. Once MAX_NUMBER_OF_NUMBERS have been entered, the program moves on to prompting for the target.
Use default set of numbers? [y/n] n
Enter a number (-1 to exit): 1
Enter a number (-1 to exit): 2
Enter a number (-1 to exit): 3
Enter a number (-1 to exit): 4
Enter a number (-1 to exit): 5
Enter a number (-1 to exit): 6
Enter a number (-1 to exit): 7
Enter a number (-1 to exit): 8
Enter a number (-1 to exit): 9
Enter a number (-1 to exit): 10
Enter target value: 5
The subset(s) closest to the target value are:
5
3 2
4 1
The user can enter -1 to halt the prompting process if they want fewer than MAX_NUMBER_OF_NUMBERS numbers.
Use default set of numbers? [y/n] n
Enter a number (-1 to exit): 1
Enter a number (-1 to exit): 2
Enter a number (-1 to exit): -1
Enter target value: 2
The subset(s) closest to the target value are:
2
The code to handle this prompting is already written for you in main().
The program should exit after printing the set of subsets.
You can assume that all numeric values will be valid ints greater than or equal to 0.
Commenting
You are expected to comment your code for this assignment. Commenting should follow the guidelines that have been discussed in class.
Starter Code
The starter code is available here, and a Makefile is available here. A transcript is available here.
Linked List
The first part of the assignment is to write some linked list functions that you will use as a data structure for the remaining parts of your program.
Step 1
Take a look at the Node struct. Notice that it has an int[] named numbers that stores the collection of numbers that make up this particular subset, an int named n that stores the number of items in that array, and a pointer to the next Node called next.
Step 2
Write the createNode() and destroyNode() functions. createNode() should copy the contents of the array into the new Node's numbers array, and copy n into the new Node's n. You can copy the contents of the array iteratively. Note that numbers is not malloc()ed; it is declared as a normal array. This means that destroyNode() is a very simple function (i.e., it's a single line of code); it exists to provide us with greater flexibility in the future. (By insuring that all creation and destruction of Nodes go through these functions, rather than being malloc()ed and free()ed directly by other code, we isolate the changes that would be required in the future if we change the implementation of Node. For example, if we changed to a malloc()ed array, and we are using a destroyNode() function, then all we need to do is make one change to that function, and everywhere that uses Nodes will work correctly. If we were manually malloc()ing and free()ing Nodes, then we'd have to change every place in our program that uses a Node.)
Step 3
Write the function debugPrintNode(), which should should print out the contents of the Node. This function is used for debugging purposes, and it not used to print the final results. If a Node contained the numbers {1 2 3}, then debugPrintNode() would print:
----------
Numbers: 1 2 3
n: 3
----------
Hint: you should write a helper function to print out the numbers in the array, since this is something that you will be doing more than once. This helper function can be written iteratively.
There should always be 10 dashes (independent of the number of items in the subset).
If debugPrintNode() is passed NULL, then it should print out the following:
[null]
The [null] is prefixed by two spaces, which are there to help align the text when it is printed as part of a list.
Step 4
Next, write the debugPrintList() function. Like the previous function, this function is used for debugging purposes, and is not used to print out the final results. This function must be written recursively. This function should print out the contents of the linked list pointed to by head in the following format. If our linked list had three Nodes, containing the subsets {2 4 6}, {2 4}, and {2}, the function would print:
----------
Numbers: 2 4 6
n: 3
----------
|
v
----------
Numbers: 2 4
n: 2
----------
|
v
----------
Numbers: 2
n: 1
----------
|
v
[null]
Note that the arrow is made up of a pipe character (shift-backslash) and the letter v. The list must be formatted exactly as it appears, including the leading spaces before the arrow and the [null] (although the spaces before the [null] are handled by debugPrintNode()). If debugPrintList() is passed the null pointer, it should just print out [null].
Step 5
Next, write the function addNodeToList(), which creates a new Node to store the specified numbers, and then adds the Node to the end of the list. This function must be written recursively. Hint: you might want to write a (recursive) helper to find the end of the list.
Step 6
Write the function addLists(), which joins two linked lists together by adding the list pointed to by head2 onto the end of the list pointed to by head1. If head1 is NULL, then you should just return a pointer to head2. If head2 is NULL, then head1 is unchanged (although it should be noted that you don't have to do anything to handle this case). This function must be written recursively. You do not have to worry about circular references (e.g., passing in a pointer to the second Node of head1 as head2).
Step 7
Make sure you've tested your linked list functions to ensure they are working correctly. Bugs in your linked list code may make the next steps much more difficult.
Generating Subsets
Next, you will generate a list of matching subsets. This will be done in two stages. First, you will generate all possible subsets of the numbers in the original list. Then, you will filter those subsets to select only those that have the appropriate sum.
There are two functions used to generate the list of all possible subsets: generatePermutations(), and insertIntoEveryElement().
generatePermutations() takes an array of numbers (and the size of that list), and returns a linked list containing all of the possible permutations of those numbers, including permutations that are shorter than the original list. For example, if we had the numbers {1 2 3}, we would get the following list:
----------
Numbers: 3 2 1
n: 3
----------
|
v
----------
Numbers: 3 1
n: 2
----------
|
v
----------
Numbers: 2 1
n: 2
----------
|
v
----------
Numbers: 3 2
n: 2
----------
|
v
----------
Numbers: 3
n: 1
----------
|
v
----------
Numbers: 2
n: 1
----------
|
v
----------
Numbers: 1
n: 1
----------
|
v
[null]
Notice that the order of the numbers in the subset does not matter, since we are adding the elements together. In other words, since we have the entry {3 1}, we do not also have the entry {1 3}.
generatePermutations() must be written recursively, and must use the following algorithm:
Create an empty results list.
if (the length of 'numbers' is 1)
{
Add a Node containing that single number to the results list.
}
else
{
Take the first number off of 'numbers'.
Recursively generate the permutations of the remaining array.
Recursively traverse that list, and create a new list that consists of the subsets
obtained by adding the removed number to every subset in the list.
Add that list to our results list.
Add the (unmodified) list of recursively generated subsets to our results list.
Add a subset consisting of the single number we removed to our results list.
}
Return the results list.
As a concrete example, let's walk through the steps involved in generating the permutations for the numbers {1, 2, 3}. (Note that we are using pseudocode here and saying things like generatePermutations({1, 2}), even though that is not valid C, since you can't pass an array like that, and that call is missing the second parameter.)
We start with a call to generatePermutations({1, 2, 3}). Since {1, 2, 3} is not of length 1, we remove the first number 1, leaving us with {2, 3}. We then need to recursively generate the permutations for {2, 3}, so we call generatePermutations({2, 3}). Again, since {2, 3} is not of length 1, we remove the first number 2, and call generatePermutations({3}). This time our array containing {3} is of length 1, so we execute the base case of the recursion, which means we create a Node containing {3} (i.e., we create a linked list of length 1, whose single Node contains the subset {3}) and return a pointer to it.
We are now back inside the call to generatePermutations({2, 3}), having received a linked list of length 1 from our recursive call. Now, we need to generate a list with all of the possible subsets we can generate by inserting 2 (the number we removed) into the list of subsets that we received. So we start with the first item in the list (which is {3}), generate the subset {3, 2}, and add it to our results list. There are no more items on the recursively generated list, so we're finished that step. Our results list now consists of a linked list of length 1, with the subset {3, 2}. We add the subsets from the recursive call, so our results list now contains {3, 2}, and {3}. Then we add a subset containing the single number we removed, so we add {2}, which means our results list contains {3, 2}, {3}, and {2}. We return a pointer to that list.
This puts us back inside our call to generatePermutations({1, 2, 3}). We take the list of subsets we got from the recursive call, get the first element ({3, 2}), and add 1 to it, generating {3, 2, 1}. We add it to our results list (which now contains 1 item). Then we do the same for the second element ({3}), generating {3, 1}, and add it to our results list (which now contains 2 items). Next, we do the same for the third element ({2}), generating {2, 1}, and add it to the results list (which now contains 3 items). Now, we add the items that we had recursively generated (which are the three subsets we just finished inserting 1 into: {3, 2}, {3}, and {2}), so our results list contains 6 items. Lastly, we add the subset consisting of the single number 1, giving us a results list of 7 items ({3, 2, 1}, {3, 1}, {2, 1}, {3, 2}, {3}, {2}, {1}). This is the end of the recursive calls, so we're done.
Steps 8 and 9
Write generatePermutations(), following the instructions above, and the pseudocode in the function. Each of the steps can be done with very little code, since you have helper functions to do most of the work. Note: you can print debugging information iteratively, although the function itself must be written recursively.
Hint: if you want to process an array starting at the second index, you can use a pointer to &a[1] (and a length of n-1). As a (non-int) example, if you have the string char *s = hello, and you say strlen(&s[1]), you will get 4, since you are passing a pointer to the second character in the array. As far as strlen() knows, the array begins at that character, so it ignores s[0], since it doesn't know that that character exists. (If you're a bit confused by this, try drawing some pictures.) You can use the same technique to begin processing a list of numbers at index 1.
As part of writing generatePermutations(), you will need to write the helper function insertIntoEveryElement(). This function must be written recursively.This function takes a linked list and an int, and generates a new linked list containing all of the subsets that can be generated by adding the single int into every Node in the list. For example, if we had a linked list containing {2, 4}, {1, 2}, and {3} and the single int 5, we would generate a new list containing {2, 4, 5}, {1, 2, 5}, and {3, 5}. Note that insertIntoEveryElement() does not modify the original list; instead, it creates a new list out of newly created Nodes.
Step 10
Fill in main() so that the list of subsets is generated.
Step 11
Once you have the list with all of the subsets in it, you need to filter the list to check for subsets that have the correct sum. In order to determine the largest sum that is less than or equal to the target value, we need to traverse the linked list. Write findHighestValidTotal(), and its helper function calculateSumOfNode(). calculateSumOfNode() may be written iteratively, but findHighestValidTotal() must be written recursively. Think carefully about what findHighestValidTotal() needs to return for each call; you will need to take into account the sum of that Node, the largest valid sum of the remaining Nodes in the list, and the target value. This is easy to get wrong, so make sure you print out some debugging info and thoroughly test this function before moving on to the next step.
Update main() to call the appropriate function(s).
Step 12
Now that we know the largest valid sum, we need to obtain a list of subsets that add to that sum. By definition there will be at least one subset (since otherwise we wouldn't have calculated that number as our valid sum), but there may be more than one subset with that sum. Write a function that takes a linked list and the highest valid total, and returns a linked list containing all of the subsets that have a sum equal to the valid total. (Note that this function does not return subsets that add up to less than or equal to the specified total, since the total being used here is the largest sum less than or equal to our target value that was calculated in Step 11. In other words, the calculation in Step 11 could tell you that the largest sum less than or equal to the target is 5; the filtering in this Step would then select all of the subsets that add up to 5.) This linked list should consist of new Nodes; the original list should not be modified.
Step 13
Write printList(), which traverses this new list and prints out every subset of numbers, and update main() to call it. You should use the helper function you wrote back in Step 3.
Step 14
Finally, you need to cleanup your linked lists. Write a helper function that takes a linked list, and cleans up all of the Nodes in it. This function must be implemented recursively. Update main() to perform the necessary cleanup.
Tester
We will provide you with a simple tester program that will check the format of your output. Details will be posted here shortly. The tester is now available. See the Announcements and Updates section for details.
A Note About Auto-Marking
We will be testing some of your functions individually. In other words, the auto-marker will provide another .c file that calls some of your functions, so some marks will be based on your individual functions. This means, for example, that if you have working versions of the linked list functions but don't have all of the subset functions working correctly, you are still eligible for part marks on the linked list sections.
Submission
Submit the file subsets.c via MarkUs before the due date. Late submissions will not be accepted.