Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
CS547 Homework 1 - due Friday September 8, 2006 ----------------------------------------------------- 1. Write a program to find the both the minimum and maximum of an array of integers, with the fewest number of comparisons of array entries in the worst case. Calculate how many comparisons your program makes in the worst case. Your answer should be something in the form of cn+d, where n is the number of array elements, and c and d are constants. The constant c MUST be less than 2. Otherwise, you have not really improved on the naiive algorithm. My hint is to save both max and min as you go through the array, and somehow take two elements at a time. Turn in your program and a copy of output for a couple of examples. You could write this program in C++ on polaris, using and ssh program. The C++ compiler is called g++. You can type "./a.out" to run your program. You can use the script command to save your output. Ask me if you want some help with this. 2. Redo problem 1, except this time write a recursive function which returns a structure consisting of the max and min of the array. If you program in C++, the header must look like this: maxandmin maxmin(int A[], int i, int j) The return type maxandmin will be the name of your structure. A is the array. i is the beginning position, and j is the ending position where you will search for max and min. Your function cannot use any helper functions, meaning this is the only function allowed. The function should split the array in half, as mergesort does, and make recursive calls on each half of the array. Turn in your program and a copy of output for a couple of examples. For extra credit, express the running time of your function as a recurrence equation, and solve it. 3. Write a program which takes an array of integers and prints out YES if there is a subset of the numbers in the array which add up to 10. Otherwise return NO. To solve this problem, you must use a recursive algorithm, which must have this header if you program in C++ bool subset_sum(int A[], int length, int k) The first argument is the array. The second argument is the length of the array. The third argument is the number you want them to add up to. This function cannot use any helper functions, meaning that this is the only function allowed. The function should work as follows. Consider the last element in the array. There are two possibilities: Either this argument is in a subset that adds up to k, or it is not. Based on those two cases, make two recursive calls on all the elements of the array except for the last one. Turn in your program and a copy of output for a couple of examples. Also, time your program for an array of zeroes for arrays of size 25,26,27,28, 29 and 30. Print me those timings. You can use the command "time ./a.out". This will run the program, and then print out the time taken. The first number given is the user time. That is the number I want. Write down the user time for each of those six experiments. For simplicity, you can modify your program to put all zeroes in the array for this part. For extra credit, express the running time of your program as a recurrence equation, and solve it. 4. I may add more problems by Friday September 1.