CS215 - Introduction to Program Design, Abstraction, and Problem Solving

Fall, 2002

Programming Assignment #1

Assigned: Tuesday, October 1st, 2002

External Documentation Due: in class on Tuesday, October 8th, 2002

Program Listing and Executions Due: by e-mail by 11:59 pm on Tuesday, October 15th, 2002

Design, write, and execute a C++ program that will demonstrate the use of several sort and search routines by allowing the user to work with an ongoing, "current" list by repeatedly choosing actions from the following menu:

   1.  Reset the current list from the keyboard
   2.  Reset the current list using randomly generated elements
   3.  Perform Bubble Sort on the current list
   4.  Perform Insertion Sort on the current list
   5.  Perform Selection Sort on the current list
   6.  Perform Linear Search on the current list
   7.  Perform Binary Search on the current list
   8.  Quit the program

Here are some requirements for your program:

Your program should be able to handle lists with up to 50 items.
When your program starts executing, it should automatically start with a current list of 0 items; in other words, the current list should start off as an empty list. Your program should track the fact that this empty current list is known to be ordered.
Before displaying the menu each time, the program should display the current list. If the current list is empty, then the phrase "(empty)" should be displayed. The current order status (known or not known to be ordered) should also be displayed.
Whenever the user chooses to reset the current list from the keyboard, the user should then be allowed to enter in between 0 and 50 positive elements from the keyboard, signaling the end of the input by entering the "sentinel" element of -1.
Whenever the user chooses to reset the current list using randomly generated elements, the user should be asked for the size of the list (a value between 0 and 50), as well as the lowest lower and upper limits that the elements in the list could have (the "range" of the elements), and then the program should automatically generate list elements within the given range using the random number generator.
Whenever the user chooses to reset the current list (whether by keyboard or by randomly generated elements), the program should track the fact that this new current list is not known to be ordered.
Whenever the user chooses to perform a sort on the current list, the program should perform the chosen sort, and in doing so also count the actual number of element comparisons and element movements used by the sort, and then print out a short report showing both the theoretical number of element comparisons and element movements necessary for sorting a list of this size, as well as the counted number of element comparisons and element movements that were actually used to sort the current list. The program should also track the fact that this re-arranged current list is now known to be ordered.
Whenever the user chooses to perform a search on the current list, the program should first ask the user for a target element to search for, then perform the search, and in doing so also count the actual number of element comparisons used by the search, then print out the results of the search (whether or not the target was found, and if it was, what position it was found in), and then finally print out a short report showing the theoretical number of element comparisons necessary for searching a list of this size, as well as the counted number of element comparisons that were actually used to search the current list.
Whenever the user chooses to perform a Binary Search on the current list, the program should first check to see if the current list is known to be ordered. If it is, then the program should continue with the Binary Search. If it is not, then the program should remind the user to first sort the list before attempting a Binary Search, and then decline to perform the Binary Search at this time.
All inputs given by the user to your program should undergo data validation to insure that they are correct in data type and range before being used.

You should write this program by extending the AList class that we are currently developing in our CS215 lecture. At a minimum, your program must include and use the following C++ methods and associated parameters:

AList::Read: fills up the native object list with positive data given by the user from the keyboard, until the sentinel -1 is entered
AList::GenerateRandomList: given the desired number of elements to be on the list, and given the desired lower and upper range values for these elements, fills up the native object list with that many randomly generated elements within the given range
AList::Print: displays the native object list's elements on the monitor
AList::BubbleSort: sorts the native object list using Bubble Sort, and sends back the number of list element comparisons and the number of list element movements used
AList::InsertionSort: sorts the native object list using Insertion Sort, and sends back the number of list element comparisons and the number of list element movements used
AList::SelectionSort: sorts the native object list using Selection Sort, and sends back the number of list element comparisons and the number of list element movements used
AList::LinearSearch: given a target item to search for, searches the native object list using Linear Search, and sends back whether or not that item was found, and if so, at what list position, as well as the number of list element comparisons used
AList::BinarySearch: given a target item to search for, and given a native object list that is already sorted, searches the native object list using Binary Search, and sends back whether or not that item was found, and if so, at what list position it was found, as well as the number of list element comparisons used

In order to make your main function relatively modular and easy to read, you should also include additional methods and/or functions as necessary.

Here are some hints to make your coding easier:

Code and test each of the five fundamental sort and search methods separately. When they are working properly, then you can combine them into the overall program.
There are some C++ library function that you can use to help you generate random numbers. To initialize the random number system (by initializing the so-called random number seed) use srand(int(time(0))). This statement should be executed exactly once (no more) for each complete execution of your program, and before your program attempts to generate any actual random numbers. To generate exactly one random number, use number = rand(), where number is some local variable of your own that you are using to "ctach" the functional value of rand(). To have access to the srand, rand, and time library functions, you should #include both the stdlib.h and the time.h libraries at the top of your program.
When generating random numbers to fill up the current list, the modulus operator (%) will be of great help to keep them within the desired range. Also, don't worry if you don't generate every possible element within that range -- missing or duplicate randomly generated elements are normal.

Be sure to follow the overall requirements for programming assignments found in the document called "Programming Requirements" posted on the CS215 Web Homepage. You'll need to develop and run your own thorough set of testcases, as well as run the set of required testcases I will make available shortly before the program listings and executions are due.

Be sure to submit your External Documentation printed out on paper, using the MS Word word-processing program and the MS Word "External Documentation Outline" provided on the CS215 Web Homepage.

Be sure to submit your Listing and Executions as two separate attachments to a single piece of e-mail sent from your SWEB computer account using the "pine" e-mail program. For your Listing, you should simply attach your C++ program (which should be in a file called "program1.cc"). For your Executions, you should attach your script file (which should be in a file called "program1.script"). Make sure that your script file shows that your program compiles using the g++ command on the SWEB Unix computer system, and shows both the required testcases and your own proposed testcases being executed by your program running on the SWEB Unix computer system. Be sure to use the following Subject: line in your e-mail, based on your CS215 section number:

For students enrolled in CS215 section 001 (Tuesdays and Thursdays at 3:30 pm), use the subject line: CS215-001 PA1

Following is a sample of what your program executions should look like when completed. (The statistics shown below are only mock-ups -- your results may differ.)

Good luck!

Sort and Search Demo Program, version 1.0
(c) 2002, (your name)

Current list: (empty) (KNOWN to be ordered)

Actions:
   1.  Reset the current list from the keyboard
   2.  Reset the current list using randomly generated elements
   3.  Perform Bubble Sort on the current list
   4.  Perform Insertion Sort on the current list
   5.  Perform Selection Sort on the current list
   6.  Perform Linear Search on the current list
   7.  Perform Binary Search on the current list
   8.  Quit the program

Choose an action: 1

Resetting the current list from the keyboard.

Enter a series of elements, -1 to stop:  5 3 7 2 8 1 6 -1

Finished resetting, 7 elements entered.

Current list:  5 3 7 2 8 1 6 (NOT KNOWN to be ordered)

Actions:
   1.  Reset the current list from the keyboard
   2.  Reset the current list using randomly generated elements
   3.  Perform Bubble Sort on the current list
   4.  Perform Insertion Sort on the current list
   5.  Perform Selection Sort on the current list
   6.  Perform Linear Search on the current list
   7.  Perform Binary Search on the current list
   8.  Quit the program

Choose an action: 6

Performing Linear Search on the current list.

Enter a target element to search for: 8

The target was FOUND on the current list in position 4.

Theoretical search statistics:  7 element comparisons
Actual search statistics:       5 element comparisons

Finishing Linear Search.

Current list:  5 3 7 2 8 1 6 (NOT KNOWN to be ordered)

Actions:
   1.  Reset the current list from the keyboard
   2.  Reset the current list using randomly generated elements
   3.  Perform Bubble Sort on the current list
   4.  Perform Insertion Sort on the current list
   5.  Perform Selection Sort on the current list
   6.  Perform Linear Search on the current list
   7.  Perform Binary Search on the current list
   8.  Quit the program

Choose an action: 4

Performing Insertion Sort on the current list.

Theoretical sort statistics:  24 element comparisons, 73 element movements
Actual sort statistics:       19 element comparisons, 61 element movements

Finishing Insertion Sort.

Current list: 1 2 3 5 6 7 8 (KNOWN to be ordered)

Actions:
   1.  Reset the current list from the keyboard
   2.  Reset the current list using randomly generated elements
   3.  Perform Bubble Sort on the current list
   4.  Perform Insertion Sort on the current list
   5.  Perform Selection Sort on the current list
   6.  Perform Linear Search on the current list
   7.  Perform Binary Search on the current list
   8.  Quit the program

Choose an action: 8

Quitting Sort and Search Demo Program, version 1.0

Sort and Search Demo Program, version 1.0
(c) 2002, (your name)

Current list: (empty) (KNOWN to be ordered)

Actions:
   1.  Reset the current list from the keyboard
   2.  Reset the current list using randomly generated elements
   3.  Perform Bubble Sort on the current list
   4.  Perform Insertion Sort on the current list
   5.  Perform Selection Sort on the current list
   6.  Perform Linear Search on the current list
   7.  Perform Binary Search on the current list
   8.  Quit the program

Choose an action: 2

Resetting the current list using randomly generated elements.

Enter the desired number of elements (0 to 50): maybe
Response must be a whole number, try again: 51
Response must be between 0 and 50, try again: 5

Enter the lower limit of the range: 10
Enter the upper limit of the range: 30

Finished resetting, 5 elements between 10 and 30 randomly generated.

Current list:  15 22 11 26 17 (NOT KNOWN to be ordered)

Actions:
   1.  Reset the current list from the keyboard
   2.  Reset the current list using randomly generated elements
   3.  Perform Bubble Sort on the current list
   4.  Perform Insertion Sort on the current list
   5.  Perform Selection Sort on the current list
   6.  Perform Linear Search on the current list
   7.  Perform Binary Search on the current list
   8.  Quit the program

Choose an action: 7

Sorry, since the current list is not known to be ordered, the Binary Search
cannot be performed at this time.  Please sort the current list first.

Current list:  15 22 11 26 17 (NOT KNOWN to be ordered)

Actions:
   1.  Reset the current list from the keyboard
   2.  Reset the current list using randomly generated elements
   3.  Perform Bubble Sort on the current list
   4.  Perform Insertion Sort on the current list
   5.  Perform Selection Sort on the current list
   6.  Perform Linear Search on the current list
   7.  Perform Binary Search on the current list
   8.  Quit the program

Choose an action: 8

Quitting Sort and Search Demo Program, version 1.0