Lab02, CISC181, Spring 2004

Welcome

Lab two has three parts.

Parts 1 and 2 involve writing programs that were discussed in lecture, and mainly test your ability to work with problem solving, input output of simple variables, and control structures (if, if/else, switch, for loops, while loops).

Part 3 involves some work from your Anderson textbook, chapter 34, that introduces functions, and the idea of separate compilation. Functions are discussed in Deitel chapter 3, but separate compilation is a topic you will need to get primarily from your Anderson textbook.

Separate compilation is an important idea to understand as you move from smaller programs into working with larger ones. Nearly all "real world" programs are built with separately compiled object files, so this is an important "real world" topic.

Part 1: Conversion Program

The first part requires you to write a program that will convert from binary (base 2) to decimal (base 10.) You will prompt the user to enter an integer in base 2. This integer may be either positive (e.g. 10010) or negative (e.g. -1001).

You will read the number entered into a regular int variable. Note that when you do, the computer will treat the number entered as a decimal number. However you are going to interpret the digits as binary digits. This is an important point, and a bit of further explanation may be helpful, so read on.

Consider the following example run:

Please enter a binary number > 10011
The decimal equivalent of 10011 is 19.

When you enter the number 10011 and store it in an int variable, as far as the computer is concerned, the value you stored represents ten thousand, and eleven. But we are going to treat that value as if it represented 10011 in binary, which is 19 is decimal (16 + 2 + 1).

The suggested way to accomplish this is to use the modulus operator (%) and integer division, dividing and "modding" by 10 each time, to strip off each digit of the number. A while loop can be used to repeat the process until all digits are added up.

Your user might input digits that are not valid for binary numbers. As you strip off each digit, you can test for this. If you find a digit other than a 0 or a 1, your program should print an error message on cerr and exit immediately. You can use the exit(-1); function to do this, or just return -1 as the result of the main function.

Your program should handle negative numbers. It may be easier to design an algorithm if you treat that as a special case. You can detect that the number is negative, remember that fact somehow by setting a variable, then make the number positive, compute the decimal equivalent, and then set the result to be negative at the end of the program.

Be sure that your program contains appropriate comments, and that you follow some reasonable convention about indenting your code to reflect the control structures (if/else, while, etc.) Once you choose a convention, be consistent, at least within each single file.

When you have completed the program, please create a script file called lab02p1.txt (the name stands for lab02, part 1), upload it into WebCT. If your TA requests it, also print a paper copy and submit it to him/her. What should your script file have in it? Well, read over the next section.

A few comments on script files

Any time this semester that I ask for a script file for a program, unless I tell you otherwise, assume the following instructions. Produce a script file where you

list the finished program (with "cat programName.cpp" or "more programName.cpp"),
compile the program with either CC or g++
run the executable for the program one or more times. (e.g. with ./a.out.) (See instructions below on how many times is necessary.)

Each time I ask you to create a script file, you should both submit it by WebCT, and make a printout for your TA and hand it in (during lab.) (See lab00 instructions online for details of how to get printouts.)

Be sure that your name and your section number appears in a comment inside each of your C++ programs! (But... don't EVER include your student number in anything you submit; this leaves you open for identity theft! Just your name and your section number is sufficient.)

How many times do I need to run each program?

When demonstrating runs of a program for this class, or any computer science class, keep the following in mind.

If the program has different kinds of output for different runs, be sure you include several runs that test the different kinds of output.

An example is in your conversion program: you need to show positive and negative binary numbers, and also a few different kinds of invalid input. It would be a good idea to test for boundary cases such as 0 and 1 also.

In this and all future labs, figuring out how many runs to do is part of the assignment. Points may be deducted if you don't show sufficient runs. Ask your instructor or your TA if you are not sure.

Note that you also need to keep the amount of output reasonable; showing 20 runs just to be "safe" when three would suffice is not reasonable.

Part Two: A "Guessing Game" Program

This part involves writing software that can play a guessing game between a computer and a human.

The game is simple (though just slightly more elaborate than the version of the game we played in lecture. Here are the rules for how two humans might play the game. (After that, I'll explain how to adapt this for the computer.)

Before the game starts, a value for n is agreed upon.
Player 1 chooses a number between 1 and n called the "mystery number". Player 1 does not reveal this number to Player 2.
Player 2 now tries to guess the number, repeatedly. For each incorrect guess, Player 1 earns a point, and responds with "higher" or lower", indicating to Player 2 whether the mystery number is higher or lower than Player 1's guess.
When Player 2 guesses the number correctly, Player 1 and Player 2 switch roles, and repeat the game. That is, now it is Player 2 that chooses a number, and player 1 that guesses, so now Player 2 has an opportunity to earn points.
The winner is the contestant with the most points.
In the event of a tie, odds/evens is used to break the tie:
- Player 1 wins if the sum of the two mystery numbers is odd.
- Player 2 wins if the sum of the two guessed numbers is even.
Player 2 might seem to have an unfair advantage; he/she can always make the tie breaker come out in his/her favor. However, consider that if she/he uses that strategy consistently, then that gives Player 1 an advantage, because it allows Player 1 to rule out half the numbers (all the odd ones, or all the even ones) right from the beginning.

The program should ask the human to choose a value of n. Then the program should play one round of the game, with the Computer serving first as Player 1, and the human as Player 2, then with the two sides reversing roles.

For the part where the computer guesses the number, you'll need some code that returns a random number. You can look this topic up in your textbook, and/or you can copy some sample code from this link:

http://copland.udel.edu/~pconrad/cisc181/04S/labs/lab02.

For this assignment, you do not need to take the odd/even rule into account when devising a strategy for the computer's guessing algorithm; a straightforward binary search is suggested. (However, its interesting to consider how the odd/even rule changes the strategy.) Also, the computer's number should be truly random (well, pseudo-random, anyway. What I mean is: don't program some "strategy" into the computer's choice of number; just use the "rand" function to choose a random integer between 1 and n.)

When you have completed the program, please create a script file called lab02p2.txt (the name stands for lab02, part 2), and do two thingsl: upload it into WebCT, AND print a copy for your TA.

A few questions to think about

When you, the human, take your turn as Player 1 (the one choosing the number), you are allowed to choose any number you like. Unlike the computer, which for now, is constrained to choose a truly random number, you could use a strategy for picking a number. What strategy is best?
If you know the computer's algorithm for guessing numbers, are there numbers that are better choices than others? Why?
Assuming you know the algorithm the computer uses to do its guessing, (and in the case of your own program, you certainly do!) could you write another program that could determine, given a number and a value of n, what the best choices are for your mystery number; that is, the numbers that your adversary will take the most guesses to come up with? How would you approach this problem?

(These are just things to think about; you aren't required to turn in answers to these questions. Well, not yet, anyway.)

Part Three: Separate Compilation

For this part, I would like you to step through the steps in Anderson Chapter 34, sections 34.11 through 34.17. Please do all of the following steps. This may seem like busy work, but that is not my intention. Rather, it is for you to learn about separate compilation by actually doing it, rather than by just hearing me talk about it, or by just reading about it.

Create a subdirectory in your account (call it anything you like),a anywhere except under your public_html directory. (This subdirectory should NOT be publicly readable.
For example,
```
mkdir cisc181_a34
```
Or, if you already have a cisc181 subdirectory under your main directory, cd into there, and do
```
mkdir a34
```
cd into the new subdirectory that you created in step 1
type in each of the files in sections 34.12 through 34.15. Don't whine; its less than 40 lines of code.
step through the steps in sections 34.11 through 34.17
make a script file showing:
- a pwd command, illustrating which directory you are in
- an ls of your directory, showing the source files (.cpp files), object files (.o files), and executable.
- a cat of each of the source files (.cpp files)
- a separate compile for each of the .cpp files, e.g.
  g++ -c chicago.cpp
  OR
  CC -c chicago.cpp
- a link of all the object files, e.g.
  g++ chicago.o indiana.o indy.o main.o
- an execution, e.g. ./a.out

Grading for Lab 02

lab02p1.txt(binary conversion): 100pts
lab02p2.txt (guessing game): 100pts
lab02p3.txt (separate compilation): 50pts
Total Points for Lab : 250pts.

Next Steps:

Do your reading assignment (found on the Calendar in WebCT) and complete the "prelab exercises" in the Lab manual for Chapter 3 before coming to lab next week (3/3/04.) Note that this week you do not have to do ALL of the pre-lab exercises. Look at the following link for guidance (click on "pre03.html") for instructions for "pre lab, chapter 3").

http://copland.udel.edu/~pconrad/cisc181/04S/hwk

You can also get to this link from the "hwk" link on the main CISC181 web page:

http://copland.udel.edu/~pconrad/cisc181

From now on, get in the habit of looking at this page for guidance as to which pre-lab exercises to complete each week.