CS 157 Spring 2001 Assignment 11 – Arrays and Sorting and Searching and Efficiency, Oh My! 100 points

Assigned: 04/11/2001

Due: 04/23/2001 at the start of class.

Pre-Lab (Do Before Lab): Bring an empty (or nearly empty) disk (keep any .c files you create, but other files can be deleted). Plan out sequence of statements needed for program.

Main Assignment:

Your have recently been hired by VISA Inc as a security guru to avoid use of phony credit card numbers. You are writing a program to “simulate” some credit card checks. I am working with you on the job, and have developed three functions for you - see Cred.h on my assignments www page (and put Cred.c into your project too, but don’t include it and don’t bother looking at it). Your mission is to first obtain a list (array) of 500 valid credit card numbers (using my function: void GenListCredCards (int array[], int numToGen, int numDigit)) with 4 digit credit card numbers and a list (array) of 1500 credit card numbers attempted to be used for purchases using my function: void GenSearchList(int array[], int numToGen, int numDigit) with 4 digit credit card numbers. Your program should sort the list of credit card numbers, then for each attempted credit card number, do a binary search to determine if it is in the list of valid credit card numbers. Keep track of how many are found and how many are not found, plus, the estimated amount of effort that would have been used to find the valid credit cards if linear search were used (binary search returns the place where the number was found, if it was found in array element 3, linear search would have required 4 comparisons to find the value). Finally, do a complete rough estimate of the relative efforts needed for this task using binary search vs linear search (see sample below). Binary search depends on a sort having been done once (with effort of approximately size * log₂(size)), plus each search will take effort of approximately log₂(size). I have provided a function: int ApproxLog2N (int value) which will calculate the log base 2 of a number. Any item not found in a linear search will take a number of comparisons equal to all of the elements in the array in order to determine the number is not there.

Sample interaction with the user (there is randomness in my functions, so your results will vary):

Welcome to YOURNAMEHERE's Phony Credit Card Detection Program

It probably used around 4500 comparisons during sorting

and probably around 13500 comparisons during searching

for a total of 18000 comparisons

This compares to 146759 estimated comparisons to find 604 credit cards that were found

plus 448000 comparisons searching for 896 credit cards that were not found

for a total of 594759 comparisons

Details:

1) The header file Cred.h will have comments explaining each functions use. The implementation file Cred.c is not intended for you to see. It will not be documented in any significant way, in order to discourage looking at it.

2) Sorting and binary searching are well known algorithms. You can use known functions for these. But note – at least one of them will require a minor change from what was shown in class to work on this problem. You will need to understand the algorithm in order to make the necessary change.

3) This program specification indicates the use of a large amount of data and doesn’t require any intermediate output. While initially testing, you will want to try this with smaller sets of data and with intermediate output.

4) Don’t build in the size of the problem too significantly. I really should only see the numbers “500” and “1500” twice in your program (in a constant, plus, Visual studio seems to not allow array declarations to use symbolic constants, only numbers).

5) Your greeting to the program user should use your name instead of “YOURNAMEHERE” (see above).

Miscellaneous:

1) Make your program work like shown above. If you have any questions about what should be done, please ask!!

2) MAKE SURE YOUR PROGRAM WORKS! (i.e. more than just removing compile errors). Make sure you test your program well.

3) Remember: Indentation, meaningful variable names, symbolic constants, and meaningful comments. Weaknesses in any of these could result in points off. You MUST include comments that explain your program in order to get full credit. Also make sure you put YOUR NAME, section, and e-mail address in comments at the beginning of the program.

4) This program is due 4/23; another program will be handed out on 4/18 to be due 4/30. This means that we will have two assignments spread over three labs (4/12, 4/19, and 4/26) but that programs will overlap.

Hand-in:

1) Listing of the program

2) Disk with .c source file plus .exe executable file. NAME YOUR PROGRAM FILE yourlastname11.c