For the third 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, create a new directory named lab3 inside your cs124 directory. (You can do this either using the graphical user interface or using the mkdir command on the command line.) Put a copy of the file TextIO.java (or at least of TextIO.class) inside the lab3 directory; you will need this file for Exercise 1, to enable the program to read input from the user.
The lab is due next Tuesday, September 20. You should turn in printouts of the programs for Exercises 1 and 2. Exercise 2 also includes a short written part, which you can either write out by hand or type, if you prefer. Your programs should be available for testing in your cs124 folder.
Command-Line Editing: You probably already know how to use the arrow keys when working on the command line. Left- and right-arrow keys move the cursor left and right within a line. Up- and down-arrow keys move you backwards and forwards through a list of previously typed commands. This list is saved when you log out, so you can even get back to commands that you typed several days ago. (The size of the list is limited to 500 entries, so you can't go back indefinitely far.)
You should also know about the TAB key. If you press TAB while typing on the command line, the computer will try to complete the command or file name that you are typing. If there are several matches for what you have typed so far, the computer will complete as much of the word as possible. For example, if the current directory contains files named MyProgram.java and MyProgram.class and you type "javac My<TAB>", the computer will extend the line to "javac MyProgram.", and you can continue typing from there. If you press TAB again, the computer will show you the two possible completions, MyProgram.java and MyProgram.class.
Sometimes, you remember typing a command a while back, but searching for it with the up-arrow key will be almost as much of a pain as retyping it. There's another solution: before you type anything, hit CONTROL-R. This does a "reverse search" through the list of saved commands: As you type more characters, the computer jumps back to the most recent line that contains the sequence of characters that you typed so far. Hitting CONTROL-R again will search further back in the list. When you get to the command that you want, hit return to give the command or hit left- or right-arrow to edit it first.
The first exercise for this lab is a task that we will probably revisit several times over the course of the term: Administering and grading a quiz on the computer. The first version, which you will work on today, uses nothing more complicated than if statements and is necessarily, therefore, rather limited.
Exercise 1: The exercise is to write a program that administers a quiz to the user. The quiz consists of 5 simple math problems, such as "What is 5 + 17?". (Think of the user as being a child in grade school.) The program should present each question and get an answer from the user. At the end, it should tell the user how many questions were answered correctly. If you do that much, you can get a grade of up to 80% on the exercise. For a higher grade, you should also print a table at the end that shows each question, the correct answer to the question, and the answer given by the user. To make a neat table, you should read about the commands TextIO.put(x,n) in Section 2.4 of the text; these commands can be used to output information in columns of a specified width. Your program should use if statements, but no loops. The program that you write should follow standard formatting guidelines to make it easy to see the structure of the program.
As you work on this assignment, you will notice one big gap in your programming knowledge. It would be nice to put the questions and answers into a data structure of some sort where they could be processed with a loop. Without this capability, you will have to process them one-by-one with several almost-identical code segments. You can save yourself some typing by using copy/paste/edit effectively.
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 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, print out 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 2: Write the queuing simulation program described above. It will not be very long. (Don't forget to keep the standard formatting guidelines in mind!) Once you have a working program, run it about a dozen times and note the answers. Now, try changing one of the probabilities to 0.51 and run the program another dozen times. Finally, change that probability back to 0.50, change the other probability 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?
Note: Since you are now working with loops, you might accidently create an infinite loop, meaning that your program never ends because it keeps looping through the loop indefinitely. If you think this is happening, you can type CONTROL-C on the command line where you are running the program. This will forcibly terminate the program.