Lab04, CISC181 , Spring 2004

Background

Chapter 4 in Deitel/Deitel (arrays).

Part 1 (adapted from DD problem 4.15)

Use a single-subscripted array to solve the following problem.

Read in 20 numbers, each of which is between 10 and 100 inclusive. As each number is read, print a message indicating whether the number is a "new" number (one not yet encountered) or a "duplicate" of a number already seen.

Write two different solutions to this problem, according to the following criteria:

  1. The first solution should use the smallest possible array of int's that can solve the problem effectively.
  2. The second solution may use as much space as you like, but should solve the problem as efficiently as possible in terms of CPU time required. (Hint: you are trading time vs. space; you will use a larger array, perhaps, but will use less CPU time).
Include explanations in comments in your code that explain the two different approaches to solving the problem. You may combine the two solutions into one main program (demonstrate one, then the other), or you may write two different programs. In any case, submit only one script file, lab3p1.txt (lab 3, part 1).

Hint: combining the two into one program will make it easier to do part two.

Part 2

Devise a way to test the theory that your second solution takes less CPU time than the first, and then test the theory. You will need to run your two algorithms on a large set of input, using the same set of input in both cases. (Twenty numbers is probably not sufficient.)

Here is one suggested approach, but there may be other valid ways of doing it.

  1. Ask the user to input values for min and max; these will represent the range of numbers (similar to 10 through 100 from part 1).
  2. Ask the user for n, the numbers of integers you will process (this is similar to the value 20 from part 1).
  3. Generate n random numbers between min and max, and store them in an array. This array might be called "numberSource".
  4. Now run your two algorithms (in the same program) using the values from "numberSource" as your input, instead of 20 values typed in by the user. That way, you can run it on a large number of values, and also be sure you are using the SAME values for both algorithms (to keep things fair.)
  5. Use the StopWatch class from the previous lab to time how long each algorithm requires.
The reason for making min, max and n variables input by the user is so that you can experiment easily (without recompiling) with small values (to test your code), then large values (to get more accurate timing results.)

You may need to impose some limit on n, so that you know how big to make your array. Alternatively, you can allocate the size of the array at run time, but that is more complex, and requires knowledge of C++ features we haven't covered yet. But, if you want to try it, be my guest. The easy way is to restrict n to be, say, less than 10,000, and declare a numberSource array of 10,000 elements.

I will be more impressed with your code if you divide up the problem into a reasonably number of well written functions. However, for now, if you want to do all the processing in the main, that's fine. Whatever you do, though, NO GLOBAL VARIABLES. If you use functions, be sure you pass all needed variables as parameters.

Grading>

  1. Part 1: 100 points (50 points per algorithm). Half the points are for correctness, and half the points are for style (good comments, indenting, clean script with appropriate testing, etc.)
  2. Part 2: 100 points; 25 points for code correctness, 25 points for code style, and 50 points for a text writeup in which you describe your results. That writeup should explain in a few sentences or paragraphs what your timing revealed, and any theories you have about why the results turned out as they did.
  3. Total points: 200
Phillip T Conrad
Last modified: Wed Mar 10 08:58:35 EST 2004