Due Thursday, 23 July. Paper submissions are due at the beginning of class, electronic submissions at 2:30 pm. The programming assignment must be submitted electronically.
You may collaborate in groups of up to five (not necessarily the same group for both parts). Submit only once per group. Prominently list on what you submit both your teammates and others who helped.
Give the strongest big-O bound you can find for each of the following, and provide a brief explanation of why the bound is correct.
public static int squareRootA(int n) {
int i = 0;
while(i * i <= n) {
i = i + 1;
}
return i - 1;
}
public static int squareRootB(int n) {
int low = 0; // this algorithm works by successively halving
int high = n; // range (low, high), as dictionary searching
while(high - low > 1) {
int mid = (low + high) / 2;
if(mid * mid <= n) {
low = mid;
} else {
high = mid;
}
}
return low;
}
public static int squareRootC(int n) { // assumes n perfect square
// take every other number in the prime factorization
int ncur = n;
int sqrt = 1; // always we have (sqrt * sqrt) * ncur == n
for(int i = 2; ncur != 1; i = i + 1) {
while(ncur % i == 0) {
ncur = ncur / i / i;
sqrt = sqrt * i;
}
}
return sqrt;
}
A final use of computer programming by scientists is for entertainment. In this program you will write a program to play a card game. In particular, your program will be able to play the game ``Go Fish'' over the Internet.
The rules of Go Fish in this assignment are the following. The shuffled deck has four cards of each of 13 ranks (0,1,2,...,12). Both players receive 7 cards as their initial hands; the remainder forms the pond. Players take turns. A turn begins when a player chooses a rank from her hand and asks the other if he has any. If so, he hands all his cards of this rank for her to place in her hand. Otherwise he says, ``Go, fish,'' and she draws a random card from the pond. She continues requesting ranks until she draws a card she did not just request; then her turn ends. When a player accumulates four cards of the same rank, the player has a book; the player shows the book and removes it from the hand. The game ends when a player goes fishing from an empty pond or when a player has no cards from which to choose a request. The winner is the player who accumulates the most books by the game's end.
This assignment has two levels.
The user should type only the name of the opponent when running your submitted program. The final line your program prints to Console should say who won the game. Thus the following transcript gives a very minimal example of the program's appearance to the user.
Against whom shall I play? bob I won!To indicate the game's progress, the program will probably display additional information about how the game is proceeding.
Your program (called a client) will communicate with another player via a server. It will be able to compete against another client specified by the user or against preexisting players on the server. The server's job is to deal cards, to referee the game, and to notify players of the game's progress. (Your program will not be connected to the opponent; both clients will connect to the server only.)
The server keeps track of both players' hands and takes care of the forced communication (replying to requests and revealing books) on its own. It frequently sends information to the clients about the progress of the game, and it prompts the clients to choose which rank to request when appropriate. Your program's primary tasks, therefore, are to keep track of what is in the hand (based on the server's messages) and to generate requests when the server prompts the program to do so.
Thus your program's general structure is the following. After connecting to the server, your program will continue receiving and handling messages. When the server tells the program that the game is over, the program should print the result and stop. When the server tells the program that it is ready for the program to request a rank from the opponent, the program should send a request to the server. When the server gives the program other information about the game's progress, the program should update what it holds in its hand; it will send nothing to the server.
Your program will require a set of functions, called the FishNet package, written to make communicating with the server easier. You can download FishNet.java off the `Assignments' section of the course Web page. You should include this in your project, with Console.java and your own program.
Also on the Web page is the FishHuman package. It implements the same functions as in FishNet. If you put it in the project instead of FishNet, then your program will play the user without connecting to the server at all. This may be useful for debugging. The FishHuman and FishNet packages provide identical functions. (For example, the name of FishNet.connect does not change to FishHuman.connect.)
FishNet.connect(Console.readString());in your program.
int[] message = FishNet.getMessage();The return value, message, encodes the server's message. The first element, message[0], indicates what type of message it is. There are several possibilities. (You do not necessarily need to use all of these in a significant way, but your program should be ready for all cases.)
FishNet.requestCard(0);