|
|
You should print out your solutions to this assignment, and either turn them in at lecture, or leave them in the TA's mailbox at Sudikoff by class time on Fri. Oct. 16, 2009.
Please also e-mail an electronic version of your code to cs8hw@cs.dartmouth.edu, with the subject "CS 8 Short Assignment 6". Please attach your code as one or more enclosures to the message, and do not include it directly in the body of the e-mail message.
You must work alone on this short assignment.
You are to implement a version of the PriorityQueue abstract data type using Data.Map. This means that you are to implement the five functions in the ADT priority queue using the map defined in Data.Map instead of using a list, as was done in ListPriorityQueue. (You may start with this program and modify it if you like.) Note that this is the same process that I demonstrated when I went from a list implementation of Digraph to a map implementation of Digraph in DigraphMap.hs, and you should look look at this program for ideas. Note: this is an fairly easy assignment. If you find yourself spending more than an hour on it you probably are missing something and should get help.
Your solution (or my sample solution if you prefer) will be used in PS 3.
Data.Map includes the function findMin, which will prove useful. If the priority queue is to store (key, value) pairs, where key is the priority value, then it makes sense to have this be the key in the priority queue also. Unfortunately, many entries in a priority queue can have the same priority, but only one entry in a Map can have a given key. This is a problem.
The solution is the same one we saw in DigraphMap: instead of associating a single value with a key, we keep a list of all values associated with the key. The function getMin will return only one of those values (which one does not matter). The function deleteMin should remove only one of those values (the same one that getMin returns), or the whole node if we are removing the last value.
Download PQDriver and ListPriorityQueue, load PQDriver into ghci, and type sorted1 and len2. Note approximately how long len2 takes.
Import your priority queue implementation into PQDriver and test it by typing sorted1 and len2. How do the run times compare?
Hand in a listing of your Map implementation of the priority queue ADT and email it to the cs8hw box. Hand in your test run with PQDriver and other tests that you have done. Say what the run times for len2 were with your implementation and the list implementation ListPriorityQueue.