CS 146: Homework due 4/24 and 4/28

Due 4/24:

21.3-1, but use size rather than rank during union. In case of two sets with the same size of calls to union(x,y), the first item's set representative the combined representative. (So here, x's initial set will be the root of the combined set if x and y sets have the same size.)
Consider the graph in Figure 22.1a of the text, page 528. Assign edge weights to each edge as follows: for edge (u,v), the weight is u+v. On this graph, run both Prim's algorithm (starting from vertex 1) and Kruskals algorithm. Show work for each: the order in which edges are taken or discarded for both, the disjoint set structures for Kruskal, the heap for Prim.
24.1-1, the first half of the question. (May require material from 4/19.)
24.2-1 (May require material from 4/19.)
Run Dijkstra's algorithm on Figure 24.6 (page 596). Show how distance and parent information changes throughout.

Due 4/28:

Programming assignment: You are to solve the problem described at Programming Challenges Bicoloring Problem. Note, the website is temporarily unavailable as of April 27, so a copy of the problem can be found here.
You need to submit your solutions to me. You should email them to me with the following subject line: "CS146Spring06: Program 4 TaylorDS", without the quotes, and where TaylorDS is replaced by your last name and initials. The email should be empty, other than an attached file of source code, in a single text file named "Prog4.java" (no quotes). This file should contain a class called Prog4 so that it can be compiled. I should be able to compile it, and run it on a test case of my own with no fuss. Please follow these directions carefully, as the process will be (hopefully) automated. I will allow you to use any fairly recent version of Java, but 1.4 and earlier will not recognize the Scanner class.
I will be running javadoc on your program, so for those of you who have not been adding proper documententation, you need to start now.
Note: both the input and output format are precisely specified for the problem. If you assume a different input format, your program may or may not work correctly. If you give a different output, your solution will be rejected. The input must be taken from System.in, you may not read it from a file. Make no assumptions not in the problem specification. I will be automating the testing of your programs, and the automated system will not be very forgiving. It should not take great effort for me to get your code to run.