2. (radix sort)
a. Take the following list of numbers and show how it is sorted into increasing order using radix sort with radix 2.
[3, 7, 10, 2, 5, 8, 6, 9, 2, 1].
Show the results of distribution after each pass.

b. Sort the same list using radix 3. Again show the results of distribution after each pass.

3. (union-find)
Consider the following set of cities, some of which are to be connected by a telegraph network: {Cecil City, Franksford, Johnstown, Marysville, Zussberg} They can be abbreviated by their initials: {J,M,F,C,Z}. The telegraph company decides to start connecting them according to cost -- lowest cost connections first. They run out of funding before all groups are connected, however. At various points during the construction, the Interstate Telegraph Agency asks to know the status of one city or another, wanting to know what subnetwork it currently is in. A typical question is "What subnetwork is Johnstown in?" and the answer might be "Johnstown is in the subnetwork whose central office is at Cecil City." Generally, the central office for a subnetwork will be at the particular city in the same subnetwork that comes first in an alphabetical listing. Given the following sequence of connections and queries, show the resulting "subnetworks" after each connection is complete. Also, give the answers to queries, too. An example of a current state of subnetworks might be an expression like { {C, F, Z}, {J}, {M} }, meaning that Cecil City, Franksford and Zussberg have been connected, but neither of the other cities have been connected to anything yet.

a. Connect Fransford to Johnstown.
b. Connect Franksford to Zussberg.
c. What subnetwork is Zussberg in?
d. Connect Cecil City to Marysville.
e. What subnetowrk is Cecil City in?

Part B: Applet:  Read and analyze each of the options. Make sure you understand the problem and a strategy for handling it. (You may work with others when doing the analyzing and strategizing.) Then choose one of them to implement. (Do the implementation on your own.)

4. Write an applet that manages the following "group formation" activity. A set of people, called PLAYERS, is to be partitioned into groups. That is, each person will be in exactly one group. The groups may be of different sizes. The process will be done by allowing any player (say it's John) to say "I want Mary to be in my group." And then, Mary (and everyone else in Mary's group) is put into John's group. This combining of groups continues until nobody speaks up any more. At any time, anybody can ask what group somebody is in. For example, before Mary's group is merged in with John's, someone might ask, "What group is Mary in?" and the answer might be "The same group that Zoe is in."

5. Write an applet that illustrates the radix-sort algorithm for a deck of 52 standard playing cards. It should begin by displaying the 52 cards symbolically (e.g., 2C for the Two of Clubs) in an array painted on a canvas. One of the commands should be be SHUFFLE, which randomly orders the cards. There should be three other commands, DISTRIBUTE-BY-RANK, DISTRIBUTE-BY-SUIT, and MERGE. These commands could then be entered by the user to sort the cards.

6. The game of Set is a card game for 2 or more players that uses a special deck of 81 cards. Each card represents a unique element of the set C X T X F X P, where
C is the set of colors: C = {R, G, V}. Here R = red, G = green, V = violet.
T is the set of numbers up to three: T = {1, 2, 3}.
F is the set of forms: F = {<>, O, ~}, where <> = diamond, O = oval, and ~ = squiggle.
P is the set of patterns: P = {*, (), //}, where * = solid, () = outline, // = striped.

One of the cards, for example, represents the element (R, 1, <>, *). This is a single red diamond solidly filled-in. Another card, for example, represents the element (V, 3, ~, //). This is three violet squiggles, striped.

Rules of play: The deck is shuffled and the faces of the cards are hidden from view of the players. 12 cards are dealt face-up on the "table". The players do not take turns. On the other hand, the first player to call "Set!" is given the opportunity to select 3 cards on the table as a "set." A "set" in this sense is a collection of three of the cards having the property that in each type of property (color, number, shape, pattern) the three cards must either all agree or all differ. For example the following three form a set:
(R, 1, <>, *), (G, 1, <>, ()), (V, 1, <>, //).
On the other hand, the following three do not form a set:
(V, 1, ~, *), (V, 2, ~, *), (V, 3, O, *),
because the shapes are not consistently all the same or all different.

Write an applet that supports the following aspects of playing the game of Set: (a) Representing and shuffling the 81 cards. (b) Dealing out cards from the shuffled deck. A "Deal 3 cards" button should cause three cards to be added to the table. (c) Providing 2 buttons for controlling the game: "Player A calls Set!", "Player B calls Set!", (d) Making the cards on the table act sort of like buttons, so that after, say, player A clicks on "Player A calls Set!", he or she can click on 3 cards. The applet should then check to make sure those cards really do form a set, and if so, remove them from the table and give player A one point; if not, the player should lose one point. If the cards from a set, then they are also removed from the table. You are free to implement additional features if you wish.

Individual Work:  This assignment requires individual work.