CPE 101
Lab 8 - Exploring Arrays

Due Date:  Fri 5:00pm

If you did this lab previously, then here is the alternate assignment.

Part 1

The first part of the lab is an "exploration."  You are provided with a complete already working program and asked to study it, then make modifications and observe the difference in how it operates.  Follow the instructions carefully and complete each step before proceeding.  If you hurry or skip a step you will run into difficulties.

Throughout the instructions there are numerous thought questions posed.  These are to prompt you to question your understanding.  You should record your answers to these questions in your lab notebook.  When you have finished all the steps you will submit your finished program via electronic handin.


1)  Download this working program and save it as  cubesArray.c
Compile it and be sure it compiles without error.

2) Study the source code line by line and be sure you understand what every line in the program is doing.  If you are uncertain, consult your textbook or instructor.

3) Predict the output from the program when the user enters 4.
Run the program and carefully study the actual output.
Is the program producing correct results?

4) Replace compound assignment operators with standard operators.
Rerun the program and verify it is still working correctly.

5) Predict the output when the user enters 0.
Run the program and carefully study the actual output. Do the actual results match your prediction?
Predict the output when the user enters -1.
Run the program and carefully study the actual output. Do the actual results match your prediction?

6) Modify the showTable() function so that it displays every other entry. i.e., 1,3,5, etc.  You should be able to do this by changing only a single line.   When you are successful, change it back to its original functioning.

7) Modify the showTable() function so that it displays the table in reverse order, i.e., 10,9,8, etc.  You should be able to do this by changing only a single line.   When you are successful, change it back to its original functioning.

8) It's really annoying to have to run the program all over just to get a new table. Enhance the program so that it will prompt the user for a new table size until a value of zero is entered.  The way to achieve this is to add a sentinel controlled loop in the main.  
The pseudocode is
    get table size from user
    WHILE table size not zero
        fill table
        show table
        get another table size
    END WHILE

Compile your modified program and run it to verify correct operation.

9) Another annoying characteristic of this program is that when the user enters 4 the program only prints a table up to 3.  Is that stupid or what?  If I ask you to give me a table of 10 cubes, are you going to give me 0 - 9? No of course not. Being a common sense human you are going to give me a table of 1 - 10.   Modify the program so it works the way common sense dictates. Compile your modified program and run it to verify correct operation.

10) Note the defined constant MAX_SIZE has a value of ten.   What happens if user enters 10? 11? 15? 20? 99? Because the array is declared at compile time, eventually we should get a run time error because we are trying to fill the array with more items than the space allocated to it.  For what input value does the program produce a runtime error?   What happens?

Should we try to anticipate the largest table someone might ask for? Or should we consider what is the largest "sum of cubes" that could fit in an integer?
Experiment to find out.  Change the constant to
    #define MAX_SIZE 1000
Then run the program with successively larger sizes; 30 50 100 then increase by 100.
How will you know when the integer has overflowed?  Use trial and error to determine the largest value of n that won't overflow sum of cubes.

Study the loop that computes the sum of cubes.  Currently it is a count-controlled loop but what we want is for it to also end before an overflow occurs.  Change the loop to an event-controlled loop (while) that accomplishes this.
Then at the end of the loop, check if we overflowed and display an error message if we did.

11) A more useful program would let the user enter the lower and upper bound on the table, instead of always starting at 1.  Make that enhancement.

12)  Then a good thing to do is make sure the user entered the limits in the proper order.  Add a check to make sure
Lower < Size and if not swap them.

13)  Make sure everything is thoroughly documented and that the header comment contains your name.

14)  Handin your file to Lab08.

       handin  graderjd  Lab08  cubesArray.c



Part 2


1)  Download this working program and save it as  compareArrays.c. 
Compile it and be sure it compiles without error.

Study the source code line by line and be sure you understand what every line in the program is doing.  If you are uncertain, consult your instructor.

2) Predict the output from the program when the user enters these data items on a single line:
1 2 3 4 -1
Record your prediction in your notebook.
Run the program and carefully study the actual output. Is the program producing correct results? If not, explain why.

3) Predict the output from the program when the user enters these data items on a single line:
1 2 3 4 5 6 7
Record your prediction in your notebook.
Run the program and carefully study the actual output. Is the program producing correct results? If not, explain why.

4) Predict the output from the program when the user enters these data items on a single line:
1 2 3 4 5 -1
Record your prediction in your notebook.
Run the program and carefully study the actual output. Is the program producing correct results? If not, explain why.

5) Predict the output from the program when the user enters these data items on a single line:
6 7 8 -1
Record your prediction in your notebook.
Run the program and carefully study the actual output. Is the program producing correct results? If not, explain why.

6) Predict the output from the program when the user enters these data items on a single line:
4.1 3.8 5x2
Record your prediction in your notebook.
Run the program and carefully study the actual output. Is the program producing correct results? If not, explain why.

7)  Enhance the main program so that it declares a second array (with same size as the first) to hold a second set of numbers read from the keyboard. 

8) After the main program lists the items in the first array, call the  fill_to_sentinel() again to fill the second array.

9) Enhance the main program so that it compares the two arrays to see if they are the same size.  If they are different sizes, display a message  "Lists are not the same size!"

10) Enhance the main program so that if the lists are the same size it then compares the two arrays to see if the contents are the same.  If any two items are different, display a message  "Lists don't match at item n" where n is the number of the item in the list (counting from one).

11)  Test your program with two lists that are different sized, with two lists that are exactly the same, and two lists that have different numbers.

Make sure you have included appropriate comments and that the header comment contains your name(s).

  Handin your file to Lab08.

       handin  graderjd  Lab08  compareArrays.c




Part 3

Create a header file, lengthofSequence.h that contains this prototype:

int
lengthOfSequence(int  list[],      /* input - array of data */
              int list_size);    /* input - declared size of list */

Implement the function that returns the length of the largest increasing subsequence of numbers in the list in lengthOfSequence.c.


An "increasing subsequence" is a part of the list where each number is greater than its predecessor.

For example:
int a3[] = { 3,1,3,5,6,4 };
The only one increasing subsequence is 1,3,5,6 which is length 4.

int a5[] = { 3, 1,3,5,6, 4, 1,2  };
Has two increasing subsequences, the first is length 4 and the second is length 2.

You may assume the numbers in the list are all positive.
Given a list with only one element the function returns 1.
Given a list_size of zero the function returns 0.

Save your function in a file named lengthOfSequence.c.

Write unit tests (using checkit) in a file named subsequenceTest.c.

The instructor has provided a test driver that you may use to verify your functions are working correctly before you submit it.  It is an object file compiled for unix1 located at:  ~graderjd/Public/lengthOfSequenceTest.o

Make sure you have included appropriate comments and that the header comment contains your name(s).
  Handin your files to Lab08.

       handin  graderjd  Lab08  lengthOfSequence.c  subsequenceTest.c



Bonus Problem

A sequence of n > 0 integers is called "pandemonic" if the absolute values of the differences between successive elements take on all possible values 1 through n - 1. For instance,

1 4 2 3

is pandemonic, because the absolute differences are 3, 2, and 1, respectively. The definition implies that any sequence of a single integer is pandemonic. Write a function to determine whether an array containing a sequence of numbers is pandemonic.

The prototype for the function is: 
/* Determine if an array is pandemonic. */
Boolean is_pandemonic(int[] list, /* input - list of n integers */
                      int size);  /* input  - number of items in the list */
Make sure you have included appropriate comments and that the header comment contains your name(s).
  Name your source file bonus.c and use Handin to submit it to Lab08.