(1) It is very common that a problem can be solved by various methods. Even though these methods can generate the same result (report), their performances can be very different. The numbers of key comparisons is the most important factor when comparing the performances of these approaches. For example, the two methods, i.e. 1A and 1B, in Part 1 below may have the averages like 772 and 10, respectively. (This means that the ratio of times which these two methods need to solve the same problem is roughly 70 to 1.) After completing this HW, you will really see that using the right method to solve a problem is a must. That is why in the industry the second best approach is normally considered an unacceptable choice.

(2) The HW demonstrates how we can solve a complicated problem by using Divide N Conquer, which is a very common skill used by IT people. It is so useful that a master can see he or she can get the works done several times faster than those who do not use the technique.

Part 1

Method 1A

1A-1. Create one array arr1 of size 1000. Populate it with random numbers in the range from 0 to 2000.

1A-2. Randomly generate 5 numbers and try to search each number in the array.

1A-3. Display the number of key comparison for each search.

1A-4. Display a table like the following:

Target Number

# of Key Comparison

1

356

(Not Found) 1000

2

54

256

3

1568

546

4

349

(No Found) 1000

5

545

678

Average

696

Method 1B

1B-1. Use the same array which was generated above. Sort the array.

1B-2. Use binary search to do the search for the same 5 random numbers in Part 1.

1B-3. Display the report like the one above. Compare the differences between the two tables. With this method, the numbers of key comparison should be fewer than 10, which is roughly 70 times faster than that of the Method 1.

Part 2

Create a function like:

void findMedianNo(int arr1[], int size1, int arr2[], int size2)

which takes two arrays and their sizes as parameters and displays (1) the int median number of the two arrays as if they are combined together as one array, (2) the number of key comparisons during the entire process. Please be informed that NO ANY AUXILIARY DATA STRUCTURES, such as array, IS ALLOWED to use in the function for solving this problem and no data in the arrays can be modified.

In main() create another array named arry 2 of the same size, i.e. 1000. Populate it with any random numbers and sort it. (Please be aware that the integers in this array are very different from those in arr1.) Find the median number of the two arrays. (In the case that the sum of the two array sizes is even, the function should first locates the two median numbers and return the average of the two integers without the decimal.)

There are at least three possible methods, i.e. linear and binary, to solve this problem and "Big-Os" of these methods are very different. Could you figure out what these three methods are? (Hint: Use the examples in Part 1 to figure out one of the three solutions.) Display reports to show the differences in terms of numbers of key comparisons among these three methods. In this homework, you should at least use the linear method for implementation.

Discussion:

What are the possible algorithms for solving the problem in Part 2? (Part 2 is a typical interview question which was actually asked in an interview of a famous IT company in the Bay Area. If you can answer one such question, you can answer another 100 questions of this type. There are various algorithms to solve the problem. The pattern of answering these questions is like this. (1) The easiest method uses linear method, just like the one for solving 1A above. The Big O of this method is N, which is the worst. (2) After giving the first answer, you will have to figure out an algorithm whose Big O is Log(N). In this case it is binary search. (3) This may not be the end of the story, since something better than binary search may exist. What could that be?

Hints

In general the coding cannot be easily done if we try to "directly" solve a problem like the one in Part 2. This is mainly because the size of the array is 1000, and hence the complexity and time needed for tracing a big array like this can easily exhaust us. Instead of solving a large complicated problem all at a time, we should apply the technique of Divide N Conquer to solve a few sub-problems one at a time. For example, we can divide the Part 2 problem into the following few sub-problems.

(1) Start with two small arrays, such as 4 and 5. We can hard-code the integers in the array. Since the arrays are so small, we know if the function returns a correct median or not. (With array sizes so small we can much easily trace the program and fix the bugs. If we start with the arrays with a thousand random integers, we cannot tell if the return integer is correct or not. Thus we will be wasting a lot of time getting nowhere.)

(2) Modify the function so that it returns correct result for the cases that the sum of the two array sizes is even.

(3) Change the array sizes to 10 and 11, respectively, and populate the arrays with random numbers. Test the program to ensure that the result is correct.

(4) Change the two array sizes to 10, and populate the arrays with random numbers. Test the program to ensure that the result is correct.

(5) Finally, you can use the size of 1000. We can verify the answers generated from the three methods. If they are the same, we know that very likely the code for the three methods is all correct.