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).

Pseudo-code.

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.

1

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. Graph the data to see this scaling behavior. – much more fun that a bunch of numbers! 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 ),

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 or the outfile writing format in main() . 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.

(2)The code should print to a file a table of the 100 random keys, execution time and the number of bisections. (3)And another simliar file for dictionary with "bisections" the number of dictionary sections
(In the future we use this basic procedure to some data analysis by running it for many values of N and many values of keys and to plot it to see as best we can the claimed scaling of log(N) and (log(log( N)) respectively. This require more instruction in how to plot data and do curve fitting and even error analysis. These skills will be useful later in the class project phase.)

2