Homework 6

Details

You may work in pairs on this assignment.

Submit any code you write using Webhandin 385-HW6. Submit other parts of your solution on paper in class.

1. Construct a Huffman encoding that is optimal for the alphabetic characters in this problem description. Include only the alphabetic characters in this problem (problem 1). Treat upper and lower case characters the same. Ignore spaces, commas, periods, etc. Show enough details so that the steps of your construction of the tree are clear. In other words, do not only show the final tree.
   You may write a program that inputs this description and outputs the number of each character if you wish. In fact, I encourage you to do so. If you do, you may share your program with each other if you wish. However, you are responsible for your own solution so if you use someone else's program and it is incorrect, you'll still lose points.
   You may write a program to construct your tree, but you need to write it from scratch. Also, you need to somehow draw the tree based on the results of your program since your program will probably not draw a tree. You may not share this program with others.
   After you construct the tree, compute the number of bits necessary to encode this problem description using your Huffman encoding. You may compare your answer with your classmates as a way to determine if you match. Your trees might differ, but the number of bits should not.
   You will notice that the tree won't actually contain the number of letters in the alphabet because certain letters do not appear in this description. (I can't write out how many letters there are in the alphabet because then this description would include a letter that would otherwise not occur in this description). I would list the letters that don't occur, but then they would be included in this description and they would occur. It is actually a bit surprising how many letters do not occur. By the way, it is interesting to note that if I spelled out the word for how many letters do not occur, it would result in a letter that only occurs once occurring twice instead. That's interesting. With that information, can you tell how many letters are missing?
   
   
   
2. Implement an algorithm in Algoraph to solve the Traveling Salesperson problem. Use TravelingSalesmanInstance as the data type. The algorithm should return a string that gives the cost of the optimal cycle followed by a ":" and then followed by the order the vertices should be visited with spaces between the vertices.
   For instance, a valid output for a vertex with 6 vertices might be: 34:0 1 4 3 5 2.
   Note: A valid solution on a graph with n vertices will be a permutation of the numbers 0 through n-1.
   Grades will be based on how many of the following graphs your algorithm can correctly solve (the puzzleID for each is given in parentheses):
   1. K05 TSP (1325)
   2. K09 TSP (1319)
   3. K10 TSP (1320)
   4. K12 TSP (1321)
   5. K15 TSP (1322)
   6. K20 TSP (1323)
   7. K25 TSP (1324)
   8. K30 TSP (1326)
   9. K35 TSP (1327)
   10. K40 TSP (1328)
   11. K45 TSP (1329)
   12. K50 TSP (1330)

   To verify that your solutions are valid, get the ValidTSPSolution Checker and add it to your project (Create a class with the same name and copy/paste the code into the class). It will not verify that your solution is optimal, but it will tell you whether or not your solution is a Hamiltonian cycle and whether or not the weight that you report is the weight of that cycle

   The tester is a little clunky, but it works. To use it you will need the puzzleID from above and your solution. Copy and paste that information into the appropriate two lines of the main method.

   Submit on paper all of the solutions you obtain using your algorithm. For each include the graph name followed by the output of your algorithm. Also submit a text file containing the same information (so I can check it).