Homework 8

Details

Complete Project 7 from the Brickficiency handout. Briefly, you need to implement CustomApproximationAlgorithm and CustomApproximationPreProcess (if necessary).

Use the cached data with the following data sets to test your algorithm. Suggested times and k values are given for each.

Narrow Plates (k=2, 3, 4, and 5 for 30 seconds each.)
OppositesAttract2 (k=2, 3, 4, and 5 for 30 seconds each.)
BlackAndBlue (k=3, 4, 5, and 6 for 30 seconds each.)
OnesAndTwos (k=5, 6, 7, 8, 9 for 60 seconds each.)
TwoByTwo (k=2, 3, 4, 5 for 60 seconds each.)

In addition, you might try to get any solution for BigList, BiggerList, or HugeList. I don't know the minimum number of stores required, but it is likely over 10 for BigList, probably over 20 for BiggerList, and I think over 50 for HugeList.

As a reminder, here is where you can get the cached files and wanted lists:

WantedList.zip (Updated 10/26/15 at 7pm)
BrickficiencyCachedData.zip (See a previous e-mail from me about how to set up the cached data.)

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

A description of your final algorithm. Clearly describe your strategy and indicate whether your algorithm will always finish quickly or will keep trying to get better solutions until is is asked to stop.
A discussion of various things you tried along the way that either worked or didn't. Be as specific as possible.
A comparison of your approximation algorithm to mine. Does it give better solutions? Is it always quick? Also compare it to the standard algorithm. How close to optimal does your algorithm get?
Give the computational complexity of your algorithm. If this does not make sense or is not possible, explain why.
A self-assessment. That is, grade yourself out of 20 points with a justification of why you should get that grade.

Please take the write-up seriously and don't just throw it together at the last minute.

Here are my results when run on the lab computers:

NarrowPlates.bsx with k=2 (30 seconds): 139.51
NarrowPlates.bsx with k=3 (30 seconds): 125.55
NarrowPlates.bsx with k=4 (30 seconds): 116.97
NarrowPlates.bsx with k=5 (30 seconds): 113.96
OppositesAttract2.bsx with k=2 (30 seconds): 13.84
OppositesAttract2.bsx with k=3 (30 seconds): 12.50
OppositesAttract2.bsx with k=4 (30 seconds): 12.29
OppositesAttract2.bsx with k=5 (30 seconds): 12.36
BlackAndBlue.bsx with k=3 (30 seconds): 0
BlackAndBlue.bsx with k=4 (30 seconds): 49.21
BlackAndBlue.bsx with k=5 (30 seconds): 43.69
BlackAndBlue.bsx with k=6 (30 seconds): 43.52
OnesAndTwos.bsx with k=5 (60 seconds): 0
OnesAndTwos.bsx with k=6 (60 seconds): 0
OnesAndTwos.bsx with k=7 (60 seconds): 515.78
OnesAndTwos.bsx with k=8 (60 seconds): 506.22
OnesAndTwos.bsx with k=9 (60 seconds): 467.21
TwoByTwos.bsx with k=2 (60 seconds): 78.62
TwoByTwos.bsx with k=3 (60 seconds): 68.50
TwoByTwos.bsx with k=4 (60 seconds): 65.76
TwoByTwos.bsx with k=5 (60 seconds): 63.18