CS 312 (W'07, T Th sections)

A great source of some of these CS theory collection types (such as PriorityQueue, Set, Bag, etc.) is the Wintellect PowerCollections. It's a "shared source" library that's free to download (you just have to register on the site, which is free). It's high quality stuff, in my experience, and should help with this and other projects:

http://www.wintellect.com/MemberOnly/PowerCollections.aspx

Don't forget--all you have to do is click "Sign Up" and create a login to download them.

Oops. I just realized that the PowerCollections plan to have PriorityQueue, but for now they don't. They suggest you use an OrderedSet meanwhile. But Dr. Ringger suggests we use a Heap instead. Someone Else will post a link to one.

I just found another library full of collections. This one does have PriorityQueue, implemented with a heap, and it's "so good" that Mono has included it with its standard distribution.

http://www.itu.dk/research/c5/

One of the things you have to do for the project report is build a TSP solver that does prune the priority queue and one that does not. You can prune a heap-based priority queue, but it costly because you can't access the tail of the queue very easily.

So you've got a very fast priority queue datastructure (ie, a heap) that doesn't efficiently support an operation that you want to do on your priority queue in order to save space. So in order to save space by pruning the tail of the priority queue, you've got use more computation time to either (a) use a less time-efficient priority queue datastructure or (b) use a heap-based priority queue in a non-time efficient way.

Which option is better: (a) or (b)? Honestly, I don't know. I am hoping to see papers with (a) and papers with (b) and I'll let you know what I see.

The really cool thing about this issue is that the implementation and use of a priority queue in a pruning branch and bound algorithm suggest that some time/space tradeoffs are just unavoidable (particularly for NP-complete problems like the TSP).

Here is a Fibonacci heap class that should work fine. Note that this class was ported from Java and has two .cs files that are both needed for it to work.

Dr. Jones,
The C5 interval heap structure that I mentioned in my previous post has both a DeleteMin method and a DeleteMax method. I wonder if both are optimized. Any idea?

The interval heap priority queue is cool and a good data structure for this lab (I'd just never heard of it before, nice find). If you use one in your project then in your report you should explain how it works and how the complexity of insert/delete min/delete max compare to a priority queue.

The SVN distribution has a few cosmetic fixes to the comments, naming conventions, and a couple of trivial code adjustments to make things more clear and run well. I've already finished the project based on this, so I don't think you'll run into bugs:

http://itsvn.byu.edu/cs312/TSP/branches/assignment/

On scaling (getting weird results?)

So in completing the project I discovered that there is an X and Y scale factor that is applied that makes the results look wrong when they are actually correct. Graphically, nodes that obviously should be in a certain order do not appear in that order. Check out City.CostToGetTo for the reason for this.

For my own debugging purposes, I changed the implementation of this method to give costs that would graphically look correct so I'd know when I was done. I'm letting you all know so that you don't get confused or frustrated when you do the algorithm 'right' and see it 'wrong'.

I think that it would be advantageous to have the early day due-date moved back along the project due-date. I think this would be good because we only learned today how to solve the problem.

After visiting with one of the TA's I would also suggest that we don't do one of the last two projects. Frankly, there isn't enough time to complete the projects, homework, and study for the exam and retain anything that we tried to learn.

Thanks for your consideration and taking the time to let me vent.

Response to comments by "tallguy":

Thank you for the suggestions.

1. The due dates for Proj #5 will remain as scheduled.

2. We will keep upcoming homework assignments light and reasonably coupled to the projects. The most recent homework assignments are representative examples of what is to come.

3. Projects #6 and #7 are less demanding than previous projects.

Take heart!

I barely have time to start looking at a project much earlier than a day or two before it's due with the schedule I am dealing with. What my problem is not the project, or the the fact I can't start it till a few days before it's due (as frustrating as that is), but rather that I feel like I have to do 4 projects for every 1 assigned.

It takes a while to complete the original project, and instead of having that, "ah I accomplished so something" feeling, I have another 3-5 hours of preparing a report. Then if that wasn't tedious enough, we have to come up with an improvement, which most of the suggestions tend to rival the original problem in time required, yet it must be completed with it's 2-4 hour report to accompany it in a matter of 2 days, (1 if you used a late day). It's just too much work! And then forget about homework, reading the lecture notes, reading the book, or even understanding the theory because there just isn't time for it. It's maddening.

I for one am would like to be able to get some sleep, rather than work on mindless details that keep me from enjoying a project.

PS. And without Word or Excel on any of the lab computers, it sure make those w/o laptops suffer trying to write up a report that uses pictures and tables. I'm sure no LaTeX zen master either.

I've beeing looking at the InvtervalHeap that Andrew suggested and I can't figure out how to get it work. I'm assuming I need some Comparer method (based on the error), but I'm not sure how those work. Has anyone had any success with this?

DrFindley,

The good news is that the next two projects (after this one) are minor projects in 312. You will have completed the major projects with the TSP.

We'll see what we can do about word and excel in the lab machines. That won't help you for this year, but it will help those that come after you.

For the IntervalHeap Comparer problem you need to have a seperate class that implements IComparer for comparing two Nodes (the data structure where you store the cost matrix and the lower bound, etc.) in the priority queue. The code should be similar to this:

class NodeComparer : IComparer{
public int Compare(Node x, Node y){
return x.LowerBound.CompareTo(y.LowerBound);
}
}

Then when you initialize your IntervalHeap you should pass a new NodeComparer to the constructor. This will then use the Compare method that is inside NodeComparer to establish priority in the IntervalHeap.

P.S. The first line of the class should be

class NodeComparer : IComparer{

It doesn't seem to be putting less-than greater-than signs but you need to specify the type of thing it is comparing (less-than)Node(greater-than) on the declaration line of the class

class NodeComparer : IComparer(less-than)Node(greater-than)

Regarding Word and Excel:

There are several alternative options: OpenOffice, LyX (for Wysiwig LaTeX), ...

(Did I say that?)

Are these available on the lab machines? If not how difficult would it be to add them?

ok, here are all the answers to the C5 Interval Heap thing. (i didn't know how to do it at first either.....here is how to get it all to work):


1. download the C5.dll from the site: http://www.itu.dk/research/c5/


2. In the Solution Explorer, right click on the Project Name and click "Add Reference..."


3. Go to the browse tab and add the C5.dll


4. OK, now you are ready to use the thing. go ahead and use it like this:

    C5.IntervalHeap<Node> queue = new C5.IntervalHeap<Node>();


5. Where your Node class is the type of object that the intervalheap holds (your own class).


6. You do need to make the Node class comparable, so the base class should look like this:

 class Node : IComparable<Node>

 {

   public int value; //can be anything

   public Node() { }

   public int CompareTo(Node other)

   {

     return value.CompareTo(other.value);

   }

 }



I hope that helps everyone. Thanks to Andrew Arnott for showing me how to do all of that.

We need a model solution to project 5 to use for project 6. Occasionaly, a student will need a working project 5 in order to do 6 but didn't write their own project 5 quite right.

Do you want your project to be the model solution in such cases?

If so, drop me an email jones at cs.byu.edu

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)

URL:
Remember me? YesNo

Comments: