Description

 

Part 1

Find upper bounds, O(n) notation, for the following recurrences.  Use the Equation editor in MS Word in order to ensure that your answers are readable, except for recursion tree where I’d recommend you create an image like in the week 2 slides.  Show your work.  Be sure to solve at least one of the problems using each of recursion tree, substitution, and master method.

1. T(n) = 2T(n/2) + n/log n
2. T(n) = 7T(n/2) + n²
3. T(n) = T(n/2) + T(n/4) + T(n/8) + n
4. T(n) = 2T(n/4) + √n

 

Part 2

Rank the following functions by their order of growth.  Be sure to put similar functions into the same category (f and g are in the same category iff f(n) = Θ(g(n))).  The result should be a table.  The first column should be the category (and will span multiple answers if there is more than one function in that category).

The second column should be the function itself.  You do not need to justify your answers for this question.

 

n2	3n2+7n+15
2log2n	log10 n
n3-log n	4n
n71+5n +17n	18n
2n	3 log2 n
√n3	n!
¾n4	n3

Part 3

Using divide and conquer, create an algorithm to solve the problem that follows.  You can use C, C++, Java, or Python to solve this problem (ask the instructor if you have another programming language in mind).  Include the asymptotic upper bound for your algorithm in your response (including the cost of subdivision and combining the results).

You have a long string containing many characters (such as this paragraph), and you want to search for a substring within this string.  For example, one may want to search for “characters” or “want to” or “bstring wi” or “language”.  All but the last example should be found.

 Keep in mind that if you use divide and conquer to solve this problem there is one complication.  The string to be found could be split between two of the subproblems (assuming your algorithm divides the string into two smaller strings).  You’ll need to handle that case as well.