EC504-Homework 1 Solved

Start reading Chapters 1, 2, 3 and 4 in CLRS . They give a very readable introduction to Algorithms.. Also glance at Appendix A for math tricks which we will use from time to time.

1.   

(a)     In CRLS do Exercise 3.1-2 on page52, Problem 3-2 on page 61, Problem 3.2-7

(b)    Place the following functions in order from asymptotically smallest to largest – using f(n) ∈ O(g(n) notation. When two functions have the same asymptotic order, put an equal sign between them.

 

(c)     Substitute

T(n) = c1n + c2 nlog2(n)

into T(n) = 2T(n/2)+n to find the values of c1,c2 to determine the exact solution.

(d)    Extra Credit(10 pt): Generalize this to the case for T(n) = aT(n/b)+nk with trial solution

T(n) = c1nγ + c2nk

using bγ = a. What happens when γ = k?

Now set γ = k but start over with the guess T(n) = c1nγ + c2nγlog2(n) to determine new values of c1,c2.

2.Here is a classical problem that is often part of interviews. You are given n nuts and n bolts, such that one and only one nut fits each bolt. Your only means of comparing these nuts and bolts is with a function TEST(x,y), where x is a nut and y is a bolt. The function returns +1 if the nut is too big, 0 if the nut fits, and -1 if the nut is too small.

Design and analyze an algorithm for sorting the nuts and bolts from smallest to largest using the TEST function, such that the worst case performance of the algorithm has asymptotic complexity O(n2). This is quite easy. Note that given a bolt you can find the number of nuts that are smaller and the number that is larger and which matches.

We will show later that this partitioning into small and large sets can be a modified the recursive quick sort algorithm to get a O(nlog(n)) solution to this problem!

“Pseudo-code” – any clear and concise description of the algorithm even with a drawing if you want – a picture i worth a thousand words?

You can also do a version of quick-sort, by picking a bolt and pivoting the nut array, and similarly picking a nut and pivoting the bolt array.

3.Binary search of a large sorted array is a classic devide and conquer algorithms. Given a value called the key you search for a match in an array int a[N] of N objects by searching sub-arrays iteratively. Starting with left = 0 and right = N-1 the array is divides at the middle m = (right + left)/2. The routine, int findBisection(int key, int *a, int N) returns either the index position of a match or failure, by returning m = -1. First write a function for bisection search. The worst case is O(log N) of course. Next write a second function, int findDictionary(int key, int *a, int N) to find the key faster, using what is called, Dictionary search. This is based on the assumption of an almost uniform distribution of number of in the range of min = a[0] and max = a[N-1]. Dictionary search makes a better educated search for the value of key in the interval between a[left] and a[right] using the fraction change of the value, 0 ≤ x ≤ 1:

x = double(key - a[left])/(double(a[right]) - a[left]); to estimate the new index,

m = int(left + x * (right - left)); // bisection uses x = 1/2

Write the function int findDictionary(int key, int *a, int N) for this. For a uniform sequence of numbers this is with average performance: (log(log( N)), which is much faster than log(N) bisection algorithm.

Implement your algorithm as a C/C++ functions. On the class GitHub there is the main file that reads input and writes output the result. You only write the required functions. Do not make any changes to the infield reading format. Place your final code in directory HW1. The grader will copy this and run∗ the makeFind to verify that the code is correct. There are 3 input files

Sorted100.txt , Sorted100K.txt, Sorted1M.txt for N = 102,105,106 respectively. You should report on the following:

(1)The code should run for each file on the command line.
Next for extra credit do your best to modify the code. (This modified code does not have to be turned in but if you do turn it in give it a different name. In class let’s discuss together what how you did this. This code should be used to graph the performance as function of N to see this scaling behavior. – much more fun that a bunch of numbers! To extend the range of sizes there is a code makeSortedList.cpp that can generate more sorted input lists any size N. For example you might 6 sizes: N = 102,104,105,106,107,108. Then collect on Time and OpCount and graph them as function of N. You may use any graphing routine you like but in class we will discuss how to use gnuplot which is a basic unix tool. ( See gnuplot instructions on GitHub at GeneralComputingInfo/Plotting_and_Fitting ), Any hack is ok to get some rough graphs. You will find there is an art to measuring these slow growth rates! If you want to automate the size you can integrate makeSortedList.cpp as subroutine into your code.

(In the future exercises, we will develop thes basic procedure to do performance analysis by running for many values of N, averaging over many cases (e.g. keys) with to get mean values for Time and OpCount even including error bars and fitting routines to determine average scaling. This is an important art of engineering analysis. This require more instruction and experimentation with how to plot data and do curve fitting and even error analysis. These skills may also be useful later in the class project phase depending on what you topic you choose.)