For the fourth lab for CS 124, you will write two programs that use branches and loops. To complete the lab, you only need to know about the basic while and if statements that are covered in Section 3.1 of the text.
To begin the lab, start Eclipse and create a new project to hold your work for this lab. You can call the project "Lab4", for example. You will be writing three short programs for the lab, but you can put them all in the same project. (There is no rule that says that you are only allowed to have one main program in an Eclipse project.) There is no graphics programming in this lab. Two of the three programs will use TextIO. You need to add a copy of TextIO.java to the project. The easiest way to do this is to drag TextIO.java from the project that you created for Lab 3 into your Lab 4 project. Remember that in Eclipse, standard input and output operate in the "Console" pane in the bottom right section of the Eclipse window.
Now that you know about control structures, you can start writing some more serious programs. As programs become more complex, it becomes more important to think about programming style. It's not good enough to write programs that will run ("syntactic correctness"), or even to write programs that run correctly ("semantic correctness"). You want to write programs that are attractive, well-designed, easy for a reader to understand, and easy to modify when necessary. Achieving these goals requires attention to programming language "pragmatics," in addition to syntax and semantics.
One big aspect of pragmatics is programming style. Following certain style guidelines can help make your programs easier to read and modify, and often it can help you get the program right in the first place. Here are some style guidelines that you should follow in your programs; these guidelines will be part of the basis for grading the programs:
The factorial of a positive integer n is defined to be the product 1*2*3*...*(n-1)*n. That is, multiply together all the numbers from 1 to n. The usual notation for this is "n!". In a computer program, you have to do one multiplication at a time. For example, to compute 7!, you could say:
product = 1; product = product*2; product = product*3; product = product*4; product = product*5; product = product*6; product = product*7;
It would be nicer to do this with a loop. To compute n!, you need a counting loop that counts 2, 3, ..., n. Each time through the loop, a product variable is multiplied by the value of the counting variable.
Note that, since you are now working with loops, you might accidently create an infinite loop, meaning that your program never ends because it keeps running through the loop indefinitely. If you think this is happening, you can stop the program by clicking the small red "Terminate" box that appears in the header of the Console window in Eclipse.
Exercise 1: Write a program that uses a loop to compute the value of 12!. Print out the answer at the end.
(By the way, 12 is the largest number whose factorial can be computed as a value of type int. You might try computing n! for larger values of n, using an int variable, to see what happens.)
Suppose that you want the computer to administer a quiz to the user. The program asks the user a question. The user responds. The program has to test whether or not the user's answer is correct. This is a natural place to use an if statement to compare the user's response to the correct response.
As a simple example, we can consider a quiz that consists of five questions. For each question, the computer asks the question and grades the user's response. the user gets 20 points for a correct response (and no points for an incorrect response). At the end of the quiz, the program reports the score.
Exercise 2: Write a program that administers a five-question quiz to the user. After asking each question, tell the user whether the response was correct. If not, tell the user the correct answer. At the end of the quiz, report the score. The user gets 20 points for each correct answer. You can design the quiz of your choice. One possibility is to use simple arithmetic questions, such as "Compute 3 + 12". (If you give a quiz where the user's responses are strings, remember that two strings s1 and s2 must be tested for equality with s1.equals(s2).)
Note that this question does not use a loop. Each of the five quiz questions will require its own section of code. Of course, once you have one question working, you can use cut-and-paste creatively to save a lot of typing for the other questions.
The final program for the lab will use both while and if statements, with the if statement nested inside the loop.
The term Monte-Carlo Algorithm is sometimes used to refer to a program that does some of its computation based on random numbers. Many Monte-Carlo programs are simulations that use random numbers to simulate random events in the real world. In this part of the lab, you will do a simple case of a simulation that has been studied extensively. The exercise is about queuing -- that is, standing in line. Think of a line (or "queue") of people waiting for service. As people leave the front of the line, new people arrive at the back of the line. There are several questions you could ask about this situation: How long does the line get? How long does the average person wait in line? For how much of the time is the line empty? How do the answers to these questions depend on the rate at which people join the line and the rate at which they are removed from the front of the line?
For this exercise, we will imagine a simple scenario: Time proceeds in a series of discrete steps. At each time step, there is a 50% probability that someone will be removed from the front on the line (but only if there is actually someone waiting in line, of course). Also at each time step, there is a separate 50% probability that someone will be added to the back of the line. The only question we want to ask is, After a certain number of time steps, how long is the line?
In the simulation program, you need an integer variable to keep track of the length of the queue. To simulate "removing a person from the front of the line," just subtract 1 from this variable. To simulate "adding a person to the back of the line," just add 1 to the variable. Checking a 50% probability just means checking "if (Math.random() < 0.50)". At the end of the program, output the value of the queue length variable.
To make things definite, let the number of time steps be 1000000. You will need a while loop that counts off 1000000 steps. In each step, you have the possibly of adding one to the queue length, and you also have the possibility of subtracting one from the queue length.
Exercise 3: Write the queuing simulation program described above. It will not be very long. Once you have a working program, run it about a dozen times and note the answers. Now, try changing the probability of adding a person to the line to 0.51 (leaving the possibility of removing a person at 0.50), and run the program another dozen times. Finally, change that probability of adding a person back to 0.50, change the probability of removing a person to 0.51, and do another dozen runs. Write a paragraph that presents and discusses the results of this experiment. What patterns do you see in the data? Are you surprised by the difference produced by such a small change in probability? You might want to try other probabilities and report on the result.
Extra Credit Opportunity: For a small amount of extra credit, you can make your program print out the maximum length of the line, as well as its average length. That is, as the simulation was running, what was the largest number of people standing in line at the same time?