CSCI 385 Fall 2015
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

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