| Assigned: | Tuesday, August 20 |
| First version due: | Wednesday, September 11, 11:59pm |
| Second version due: | Tuesday, October 1, 11:59pm |
This assignment lets you get familiar with C++.
It is important that you follow the instructions. Do not try to improve on the design described here. Read the entire assignment before you start working on it.
This is intended to be a warmup assignment. It does not reflect the kinds of things that we will be doing. Expect later assignments to be larger, and to involve principles of data structures.
This assignment has two parts, involving two different ways of writing the program. Turn in both of them at the same time. (Remember that you turn in two versions of a programming assignment. For this assignment, each version involves two programs.)
Given any positive integer n, the hailstone sequence starting at n is obtained as follows. You write a sequence of numbers, one after another. Start by writing n. If n is even, then the next number is n/2. If n is odd, then the next number is 3n + 1. Continue in this way until you write the number 1.
For example, if you start at 7, then the next number is 22 (3 times 7 plus 1). The next number after 22 is 11. The hailstone sequence starting at 7 is (7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1), and it contains 17 numbers. The hailstone sequence starting at 6 is (6, 3, 10, 5, 16, 8, 4, 2, 1), and the hailstone sequence starting at 1 is (1).
The functional requirements tell what the program is supposed to do.
Write two C++ programs that do the same thing.
Each reads a number n from the user
(after giving a suitable prompt) and then tells the user four things:
(1) the entire hailstone sequence starting at n,
all on one line, with the numbers separated by spaces;
(2) the length of the hailstone sequence that starts with n;
(3) the largest number in the hailstone sequence that starts with n;
and (4) how many of the numbers in that hailstone sequence are even.
The output needs to be sensible and easy to read, not just numbers.
For example, a session with this program might look as follows.
Parts in black are printed by the program.
Parts in blue are typed by the user.
What number shall I start with? 7
The hailstone sequence starting at 7 is
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
The length of the sequence is 17.
11 of the numbers are even.
The largest number in the sequence is 52.
Here is another example.
What number shall I start with? 1
The hailstone sequence starting at 1 is
1
The length of the sequence is 1.
0 of the numbers are even.
The largest number in the sequence is 1.
The nonfunctional requirements are additional requirements on how the program must be written, documented, etc.
The programs are required to be written in accordance with the design issues and algorithmic issues discussed below.
Every function is required to have a clear and concise contract.
The design of a program includes issues such as which functions it includes, how those functions are organized into modules, and what each function and module accomplishes. It does not include details of how each function works.
For this assignment, each of the two programs should have just one module.
This is an exercise in using C++, not an attempt to design the most efficient possible solution to this problem. Your design is required to use the following functions in each of the two programs. Do not try to fold all of these functions together into one. Do not modify what each function is supposed to do. Make it do what is called for.
Include a function that computes the value that follows a given value n in the hailstone sequence. If you call it next, then next(7) = 22 and next(22) = 11. Any time you want to get the next number in the sequence, you must use this function.
Include a function that takes an integer n and prints the hailstone sequence starting at n on one line, separating the numbers by spaces. This function should not print a newline character. Make the return type void, indicating that it does not yield an answer, it just does something.
Include a function that takes an integer n and returns the length of the hailstone sequence starting at n. For example, if this function is called hailstoneLength, then you will find that hailstoneLength(3) = 8, hailstoneLength(4) = 3 and hailstoneLength(1) = 1.
Include a function that takes an integer n and returns the largest number in the hailstone sequence starting at n. For example, if this function is called hailstoneLargest, then you should find that hailstoneLargest(3) = 16 and hailstoneLargest(4) = 4.
Include a function that takes an integer n and returns the number of even numbers in the hailstone sequence starting at n. For example, if this function is called hailstoneEvens, then you should find that hailstoneEvens(3) = 5, hailstoneEvens(4) = 2 and hailstoneEvens(1) = 0.
Include a main program that interacts with the user, asking for the start number n, and then printing the results.
For this programs, all parameters are required to use call-by-value. Do not use call-by reference. No function is allowed to change any of its parameters. So, for example, if one of your functions has a parameter called n, then there must not be a statement that changes the value of n in the function.
Algorithmic issues are concerned with how functions work.
You are required to write two different programs that do the same thing. For program 1, use if-statements to make decisions and loops for repetition. Think about the job that each function needs to do, and how to do that job.
Program 2 is similar to program 1, but for program 2 you are not allowed to use any kind of loop. Instead, use recursion. Think about how each function can help itself. Here are some suggestions.
Suppose that you want to find the length of the hailstone sequence starting at 7. If you ask for the length of the hailstone sequence starting at 22 (result: 16), how would you determine the length of the sequence starting at 7?
Handle the length of the sequence starting at 1 as a special case. Use an if-statement to decide whether this is the special case of 1 or not.
Suppose that you want to know the largest number in the sequence starting at 7. Ask for the largest number in the sequence starting at 22. (The answer is 52). The largest number is clearly the larger of 7 and 52. As another example, suppose that you want to know the largest number in the sequence starting at 52. Ask for the largest number in the sequence starting at 26. The answer is 40. What you want is the larger of 52 and 40, clearly 52.
Important Note. In terms of efficiency, recursion acts as an amplifier. Algorithm designers use it because they know that, if they think of a clever idea and they use it in a recursive definition, recursion amplifies it into a very efficient algorithm. But recursion also amplifies bad ideas. If you do something in a slopply way in a recursive function, recursion can amplify it and make a very slow algorithm. In particular, if you do the same recursive call twice, which is a waste of time, recursion will be very slow. Try your program on input 31. Does it respond quickly, or is it really slow?
To count the even numbers, there are three cases. Call the first number in the sequence n.
Each function is required to have a clear, precise and concise contract. Write the contract just before the function definition. Make sure that the contract tells what the function does, not how it works. Here are a few pointers.
A contract must explain what each parameter is for. Read your contract. Is every parameter mentioned? Is it clear, from the contract, how every parameter affects what the function does?
Talk about parameters by name, not using phrases such as "the number" or pronouns such as "it".
If a function returns a value, then the contract must explain what is returned, and how each parameter affects what is returned.
A contract cannot omit any behavior that can be measured just by calling the function (as a black box).
If your contract discusses what is going on in the body of the function, such as what a local variable is used for, then it is telling how the function works. Get rid of that. The contract only explains behaviors that can be measured simply by using the function (as a black box).
Each function is required to have exactly the same contract in program 1 as it does in program 2. If you need a different contract, you are doing something wrong.
Compile each program and test it using g++ under Linux, as follows.
Log into one of the computers in Austin 208, or log into login.cs.ecu.edu using ssh or NX client or putty. Use your pirate id and password. Write your pirate id using lower case letters.
To obtain the NX client, do a Google search for NX client, and download the client. Note that the client is not the computer that you are using, so it makes no sense to say that you are "logging into NX". The NX client is software that runs on your computer that allows it to connect to a host (in this case, to login.cs.ecu.edu). So it is like a web browser in that respect.
Important. When you log in using NX client, push the configure button. In the Desktop section, be sure the setting is Unix. You can set the desktop manager to either GNOME or KDE. If you do not know which you prefer, choose GNOME.
You will probably have a box pop up asking you whether to install updates. You will want to close that box. (Do not try to install updates. You are not allowed to do that.) There is an invisible X button in the upper-left hand corner of the box. Move the mouse there and push the invisible button. (Yes, this is bizarre.)
For Gnome, create a terminal by right-clicking on the background and selecting open in Terminal. (For ssh or putty, you are automatically in a terminal.)
You can see the names of your files by typing command ls in the terminal window. At the end of each command, type the return key.
Create a new folder (or directory) for your CSCI 3300
assignments by issuing command
mkdir 3300
Then change to that directory using command
cd 3300
To show your current directory, type
dirs
Note that ~ stands for your home directory, and directories are
separated by /, not \.
To show the contents of your current directory, type
ls
Create another directory, inside the 3300 directory, for assignment 1.
For example, do commands
mkdir assn1
cd assn1
Create your program using a text editor. If you are using ssh, you will probably be best off editing the file on your local computer and transfering it to the server. In the ssh window, there is a yellow button with blue dots over it at the top of the screen. Push that to get a file transfer window. Drag files back and forth.
In the graphical interface, you can get a simple
text editor by typing command gedit in the terminal.
Other editors are also available. If you use command
gedit&
then you will be able to continue to use the terminal window. The
& tells the terminal window not to wait for gedit to finish before
coming back with the next prompt.
If you use NX and want to transfer files, you can do so using WinSCP. Do a Google search for WinSCP.
Software can be constructed by makefiles, which contain the
commands needed to build the software. Suppose that your two programs are
called hailstone1.cpp and hailstone2.cpp. Using a text editor, create the following file
in the 3300/assn1 directory, and call it Makefile. (Just copy
it from this document and paste it into the editor.)
CC=g++ -g -Wall -Wshadow -O
hailstone1: hailstone1.cpp
$(CC) -o hailstone1 hailstone1.cpp
run1: hailstone1
./hailstone1
debug1: hailstone1
gdb ./hailstone1
hailstone2: hailstone2.cpp
$(CC) -o hailstone2 hailstone2.cpp
run2: hailstone2
./hailstone2
debug2: hailstone2
gdb ./hailstone2
clean:
rm hailstone1 hailstone2
The spaces shown in blue must be a single tab character.
Do not use spaces. The first character on those lines should be a tab.
The first line of this makefile says to replace $(CC) by g++ -g -Wall -Wshadow -O, which runs the g++ compiler with options -g (requesting debug information in the file), -Wall (requesting warnings) and -O (requesting optimization, which will give more warnings).
Subsequent parts consist of a target, a colon, a list of
zero or more things that the target depends on, and then one or more
commands (preceded by tabs) that build the target. For example,
hailstone1: hailstone1.cpp
$(CC) -o hailstone1 hailstone1.cpp
says that file hailstone1 needs to be rebuilt any time there is a
modification to hailstone1.cpp. The command tells how to rebuild
hailstone1. The command will be
g++ -g -Wall -O -o hailstone1 hailstone1.cpp
Sometimes the target is a command to be done, not a file.
Dependencies can be other targets to be built.
For example,
debug2: hailstone2
gdb ./hailstone2
says that, to make the command debug2, first make hailstone2, if
necessary. Then run command
gdb ./hailstone2
which runs the debugger on hailstone2.
Compile hailstone1.cpp by running command
make hailstone1
If you get any errors, then modify your program using the text editor.
If you cannot understand the errors, first look on the line of the
first error and try to see what is wrong. After fixing that error,
compile again. If you cannot see what is wrong, ask for help.
If you just get another prompt after doing make, without any error messages, then your program contains no compile errors. That does not guarantee that it works, though.
Once your program compiles correctly, try running it. First,
list your files using ls. You should see one called hailstone1.
That is the executable version of your program. (Linux does not use
the .exe convention that Windows uses for executable programs.) Use
either command
./hailstone1
or
make run1
to run your program. (If you use make run1, then the computer
will automatically recompile your program first if you have modified
it, and then will run it.) Try it on several numbers, and check whether the
results are correct. Does it work? Be sure to try unusual numbers,
such as 1 and 2.
If your program gets stuck in
an infinite loop, type control-C (the control and C keys at the same
time) to stop your program. Then run the program using the debugger,
using command
make debug1
Again stop it, using control-C. The debugger will give you a prompt.
Type
backtrace
to see where the program is. Type
print n
to see the value of variable n. You can only print variables in the
current function. But you can choose any of the functions to be
the current one.
At the backtrace, you see the functions
that are running, with the most recently called on the top. Each is
numbered. To move to a larger number, use gdb command
up
and to move to a smaller number, use gdb command
down
To exit gdb, use command quit.
To log out, click on Actions at the top of the screen, and select logout. (For ssh, just type command exit.)
For a large piece of software, it is critical to have a development plan. You simply cannot write the whole thing and then begin testing. This assignment is not a large piece of software, but it is a good idea to become familiar with development plans on smaller programs rather than being thrown into them on your first large program.
Here is a suggestion for steps to get this done. It uses an approach called successive refinement, where you write a little bit, test it, write a little more, test that, and so on.
Write the design as a skeleton program.
Write (1) your name,
(2) the course number, (3) the assignment number
at the top of the program, in a comment.
If you use tabs, also include a comment telling how often there
is a tab stop. For example,
// tab stops: every 4 characters
says that a tab moves 4 characters.
Write a contract and heading for each function. The contract is a comment written just above the function heading. Check that the contract for each function explains how each parameter influences what that function does. Refer to parameters by their names, not by pronouns or vague phrases. Write it all down in file hailstone1.cpp, not just on paper. Do this before writing the bodies of the functions.
Be sure that each contract tells exactly what the function that it describes does, not how it works. The contract must clearly explain the result, and how each parameter influences the result. It should not mention the roles of local variables inside the body. There is no need to be verbose, but be sure that the contract is precise. Write the contract, as a comment, followed by the function heading. Here is a sample contract and heading for the next function, with an empty body.
//======================================================================
// next(n) returns the number that follows n in the hailstone sequence.
// For example, next(7) = 22 and next(22) = 11.
//======================================================================
int next(int n)
{
}
Write the body of the next function. You already have your design, so just write this in the design, in the spot that you have reserved for this function. Make sure that it does not try to do too much. Its only job is to get the next value in the sequence. Make it do that job, and nothing more. Make sure this function is well indented before you test it. Keep every function well indented while you work on it.
Now test it. Write a main program that just computes next of a few values, and checks that they are right. Here is a sample main program that uses the iostream library for output.
#include <iostream>
using namespace std;
...
int main()
{
cout << "next(7) = " << next(7) << "\n";
cout << "next(22) = " << next(22) << "\n";
cout << "next(3) = " << next(3) << "\n";
cout << "next(44) = " << next(44) << "\n";
return 0;
}
To keep the compiler happy, write main at the bottom of the program.
You will need to define a function before it is used. (This is
different from Java, where you can write methods in any order.)
Make a copy of your program, called hailstone2.cpp.
Command
cp file1 file2
copies file1, and calls the copy
file2. So use command
cp hailstone1.cpp hailstone2.cpp
Now that you have a skeleton of hailstone2.cpp, continue editing hailstone1.cpp.
You can come back to hailstone2.cpp later.
Write the function that computes the length of the hailstone sequence starting at n in the spot reserved for it in your design. Make sure it is well indented and readable. Check it by doing a hand simulation. Be sure that it uses the next function to compute the next value.
Modify your main program so that it now reads a number n from the
user and prints just the length of the hailstone sequence
starting at n. Your main program might look as follows, using
the iostream library.
#include <iostream>
using namespace std;
...
int main()
{
int n;
cout << "What number should I start with? "
cin >> n;
cout << "The largest number in the hailstone sequence starting at "
<< n << " is " << largestNum(n) << "\n";
return 0;
}
Test it.
Write the function that computes the largest number in the sequence. Keep it well indented and readable. Check it by doing a hand simulation. Augment your main program to use that function, so that it now prints both the length and the largest number. Test it.
Write the function that computes how many of the numbers are even. Keep it well indented and readable. Check it by doing a hand simulation. Augment the main program to show that information. Test it.
Write the function prints the entire sequence. Check it by doing a hand simulation. Augment the main program to show that information. Test it.
You should now have a finished version of hailstone1.cpp. Now turn to hailstone2.cpp. Modify the comment at the top of the program to say that this is part 2. Do the same steps as for part 1, writing each of the functions that previously used a loop, but using recursion instead. Test each function after you write it.
At this point you should have two working programs that are well documented, well indented and readable. Submit your program. See below for how to do that.
If you find that your program is already in good shape, good. Give yourself a pat on the back. If you find yourself having to clean up the program at this point before submitting it, then you have not paid attention to the plan, and you are using software development methods that have been shown over and over to yield very bad results. Remember that you do not know more than those who have walked this road before you.
You will receive feedback on your program. If you have followed this plan, then you should end up with a grade of 100%. If there are any problems, then fix them and resubmit your program.
Here are some things to do and mistakes to avoid, with a range of points that you might lose (out of 100) for each one. You will find that some penalties are very stiff, indicating how important they are. For example, you can end up with a 0 if you utterly fail to follow the design. To avoid losing those points, just do not make those mistakes.
Write your name, the course and the assignment number in a comment at the top of the program, along with the tab stops (see below) (up to 2 points).
Failure to compile (up to 100 points). Your program is expected to compile. If one of the parts has a fatal compile error, then you will receive no points for that part. So you lose 50 points if part 2 does not compile, for example.
Compiler warnings (up to 5 points).
Your program should not have any compiler warnings.
A warning that you might get is
control reaches end of nonvoid function
That means a function does not always return an answer.
Check the function definition, and make sure that it
returns an answer no matter what.
Failure to follow the design (up to 100 points). The design requires you two write certain functions. It also says what those functions must do. It is not acceptable to substitute a different design. It is not acceptable to do all of the computation in a main function, or to make the functions do something other than what they are supposed to do.
The only functions that print anything are main and the function that prints the entire sequence. So do not make any of the other functions print anything.
None of the functions has a reference parameter. Do not use reference parameters for this program.
The design does not call for global variables. Do not use global variables. Using even one global variable means that you are not following the design, and can lead to a very high loss of points.
Failing to follow the design on one of the functions can count the same off as failing to write that function at all.
Turning in only one of the parts (up to 50 points). There are two parts, one that uses loops, the other using recursion. You will loose 50 points for failing to turn in one of those parts.
Failure to write one or more functions (up to 8 points each). Each part has six functions, counting main. If a function is missing, you will lose about 1/6 of the 50% score for that part.
Incorrect results (up to 8 points per result kind). If one type of result is not shown or is incorrect, then you can lose as many points as if you had not written the function that produced that result.
Failure to use next (up to 5 points per occurrence). To compute the value that comes after n in the sequence, you must use next(n). If you compute the value without using next, then you will lose points.
Poor or missing contracts (up to 12 points). Every function must have a contract. A contract tells what a function does, not how it works. A contract tells precisely how each parameter affects what the function does, and refers to parameters by name. Here are some examples of how not to write a contract.
//largestNum(n) returns the highest number in the hailstone sequence.
The problem with the above contract is that it does not say what
n is. It talks about "the hailstone sequence", even though
there is no single hailstone sequence. A contract should not force
the reader to guess what the parameters are for.
//largestNum(n) goes through all of the numbers, checking each
//against a number that is being remembered to see whether it is
//larger. In the end, the number that is being remembered is
//returned.
What? That means nothing. It is an attempt to describe how
the algorithm works. It is so vague that it neither adequately explains
how the function works nor what it accomplishes. For this contract, you
will receive the same points as if you had not written the contract at all.
A reasonable contract for largestNum would be as follows.
//largestNum(n) returns the largest number in the hailstone
//sequence starting at n.
Notice that it tells what n is for, and just what the function
yields, without getting bogged down in explaining how the
function does its job.
Poor indentation (up to 10 points). You are expected to indent your function definitions correctly. Minor problems will not lose much, but seriously bad indentation can lose 10 points. Here are some simple rules of thumb.
Line up braces. A right brace should be directly below the matching left brace. Everything between the braces should be indented two or three spaces.
Never hide a right brace in the right margin, with the only exception being a "do nothing" statement written {}. Please do not use a semicolon as a do-nothing statement.
If two statements are done one after another,
then they are indented the same amount, regardless of
how large they are. So you write
if(...)
{
...
}
return k;
not
if(...)
{
...
}
return k;
since first you do the if statement then the return statement.
Failure to explain tabs (2 points).
Be sure that you either do not use tabs in your program or
that you tell where your tab stops are at the top of the program.
Different editors are set up with different tab stops. For example,
write
// tab stops: every 4 characters
If you do not know where the tab stops are, do not use tabs.
Crippled functions (up to 5 points). A crippled function is one that does not really do its job, but requires its caller to do part of the job. An example for this program would be a printSequence function that is supposed to print the entire sequence starting at n, but in reality prints everything in the sequence except the first value n. You would find yourself compensating for that by making main print n, then calling printSequence to print the rest.
Do not write crippled functions. If the function is not doing what it is supposed to do, fix the function. Do not compensate for the mistake at the point where you call the function.
Excessive inefficiency (up to 5 points).
This applies particularly to the recursive version. Do
not compute the same value twice, unless it is a trivial
repeated computation. Never make two identical recursive
calls that produce the same value, one after another. For
example,
if(largestNum(x) > n) return largestNum(x);
says to compute largestNum(x), and, if the result is larger
than n, to go compute the same thing, largestNum(x), again.
There is nothing wrong with writing the same thing in two
places in a definition; just be sure that both cannot be
done in one call to the function. To avoid computing a
value twice, put it in a variable.
Long lines, margin comments (up to 5 points). Avoid long lines. As a rule of thumb, keep lines at most 80 characters long. Avoid margin comments (comments written in the right margin telling what the code to the left of them does). Those comments rarely say anything useful, and they make lines long and clutter the program. If you need to write a comment inside a function, write a paragraph comment telling what the next paragraph of code does.
Modifying call-by-value parameters (up to 3 points). Do not change the value of a parameter. The reason is that, as a matter of principle, you do not want to lose track of the question that you were asked. If you modify a call-by-value parameter, you make debugging and later modification more difficult. So, for example, if your function has a parameter called n, do not change the value of n inside that function. Use a different variable.
Having two names for the same thing (up to 1 point).
If you have two names for the same thing you make the program
more difficult to understand. For example, suppose that your function
begins as follows.
int next(int n)
{
int m = n;
...
}
Now suppose neither n nor m are changed in the
function, as is typical
in a recursive function definition.
Then m is really just another name for n.
Why have two names? You would only create m if you intend to,
and need to, change it.
return x = ... (up to 1 point).
Some novice programmers feel that they have to put a value
into a variable in order to return it, so they write
return n = n/2;
There is no need to do that. If you want to return n/2, then say
return n/2;
Keep things simple and direct.
Having a variable with the same name as the function that contains it (up to 1 point). If you have a variable whose name is the same as a function's name, then you are not able to call that function in the part of the program where that variable exists. It is also confusing.
Kick-starting functions (up to 5 points).
To use a function, just use it where its result is needed.
Do not add an extra call. For example, do not write
length(n);
m = length(n);
There is no need to get the program ready to call the function.
If you want m to be set equal to the answer produced by
length(n), just write
m = length(n);
Packing functions together (up to 1 point). Put a blank line between function definitions. There is no need to pack them together. Spacing them out just a littl, makes the program more readable.
But also do not put huge blank sections in your program consisting of several blank lines in a row. A long space is two blank lines. Longer than that is excessive.
system("pause") (up to 5 points). Some programmers write system("pause") at the end of main to compensate for a flaw in the design of a Windows development environment. Since that is a nonstandard thing, I must edit your program to get rid of it before I can test your program. I should not have to fix your program for any reason.
You must submit your program using the following method. Email submissions will not be accepted. An excuse that you do not know how to use Linux will not be accepted.
To turn in version 1, log into one of the Linux machines, change
your directory to the one that holds your programs, and do the
following command.
~abrahamsonk/3300/bin/submit 1a hailstone1.cpp hailstone2.cpp
To turn in version 2, do the following.
~abrahamsonk/3300/bin/submit 1b hailstone1.cpp hailstone2.cpp
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
You can do repeated submissions. New submissions will replace old ones.
A good way to debug a program is to turn on the lights. That means show things that the program normally would not show. For this program, a good idea is to show the numbers in the hailstone sequence as you compute them, to see that you are doing the right thing. Remove those prints before handing in your program.
For errors such as infinite loops, you can find a debugger such as gdb useful. Gdb is described above.
One problem that you might encounter is an infinite recursion, where a function keeps calling itself with the same value until the program runs out of memory. If you run gdb with an infinite recursion, try to stop the program with control-C before it has produced too many copies. If you do a backtrace and gdb says the run-time stack is corrupt, or that there is no run-time stack, then it means that you have run out of memory. Try slowing down your function by putting some prints in it. Then you will be able to stop it before too many copies have been created. If you are using successive refinement, you will know which function is at fault. It will be the one that you just added.