Homework 10

Details

Complete Project 8 from the Brickficiency Handout.

Make sure you commit your code to your SVN repository before the deadline. Also submit a hard copy of a write-up that includes

1. A description of your final algorithm. Clearly describe your strategy and why you think it will yield solutions that contain most/all of the wanted items.
2. A discussion of various things you tried along the way that either worked or didn't. Be as specific as possible.
3. A comparison of your partial algorithm to mine. Does it give better solutions? Include a table that includes the results below in one column and your results in another column (or columns if you tested several algorithms).
4. Give the computational complexity of your algorithm. If this does not make sense or is not possible, explain why.
5. A self-assessment. That is, grade yourself out of 20 points with a justification of why you should get that grade.

Before you run the tests, you need to get the updated wanted lists and extract it to your C drive: WantedList.zip. (Sorry. I found a few more errors in some of the old lists that cause the program to crash.)

Here are the results of my algorithm on the test data:

File,k,time,cost,items got, items wanted
OnesAndTwos.bsx,5,10,518.47,3641,3655
OnesAndTwos.bsx,6,10,566.32,3647,3655
BigList.bsx,6,10,1287.40,8990,9808
BigList.bsx,7,10,1233.57,9012,9808
BigList.bsx,8,10,1291.57,9063,9808
BigList.bsx,9,10,1286.34,9155,9808
BigList.bsx,10,10,1266.30,9168,9808
BiggerList.bsx,10,10,1443.98,9660,10278
BiggerList.bsx,11,10,1425.37,9689,10278
BiggerList.bsx,12,10,1425.89,9693,10278
BiggerList.bsx,13,10,0,0,10278
BiggerList.bsx,14,10,0,0,10278
BiggerList.bsx,15,10,0,0,10278
HugeList2.bsx,10,10,2146.50,14002,14816
HugeList2.bsx,15,10,2036.63,14081,14816
HugeList2.bsx,20,10,0,0,14816
HugeList2.bsx,25,10,0,0,14816
HugeList2.bsx,30,10,0,0,14816
OnesAndTwos.bsx,5,120,518.47,3641,3655
OnesAndTwos.bsx,6,120,566.32,3647,3655
BigList.bsx,6,120,1259.41,9085,9808
BigList.bsx,7,120,1257.86,9111,9808
BigList.bsx,8,120,1304.44,9183,9808
BigList.bsx,9,120,1313.20,9258,9808
BigList.bsx,10,120,1303.63,9298,9808
BiggerList.bsx,10,120,1447.62,9742,10278
BiggerList.bsx,11,120,1433.50,9768,10278
BiggerList.bsx,12,120,1415.45,9797,10278
BiggerList.bsx,13,120,1432.93,9833,10278
BiggerList.bsx,14,120,0,0,10278
BiggerList.bsx,15,120,0,0,10278
HugeList2.bsx,10,240,2146.50,14002,14816
HugeList2.bsx,15,240,2062.84,14194,14816
HugeList2.bsx,20,240,0,0,14816
HugeList2.bsx,25,240,0,0,14816
HugeList2.bsx,30,240,0,0,14816