No referencing needed. I will post any additional notes I have to the order in a few hours.
HOMEWORK 4: CS 425 (THEORY OF ALGORITHMS) DUE DATE: 10/12/2020 1. Given the pseudocode for Binary Search Algorithm as below: BinarySearch(A, p, r, V) if p < r="" q="(p" +="" r)/2="" if="" v="A[q]" return="" q="" else="" if="" v=""> A[q] return BinarySearch(A, q+1, r, V) else return BinarySearch(A, p, q-1) else if p = r, if V = A[p] return p else return -1 return -1 end function Using this pseudocode, write a function for BinarySearch and also complete the program, by writing a main, which will supply the array A (you may like to use the same main as the other programming exercise you have done so far), and also get an user input for V (which should have same data type as the array itself). Call the function BinarySearch by sending the array, and 1 for p, N for r and V, store the value in a variable x, which stores the position number of the searched key V. Then check if x is -1, then display data is not found, otherwise display the value of x, by using a suitable title, saying Data V is found in location x (value of x should be displayed). Must compile, run and copy and paste the program underneath this word document. 2. a) Construct a Binary Search Tree using the following data: 5437172844716460 b) Illustrate how will you search for 30 from the above tree and how many searches will be needed. c) Illustrate how you will delete the root from the above tree, redraw the tree after deletion. d) Add a new data after conducting operation c, say the new value = 50 (Do not start from scratch, show this operation by adding onto existing Tree). e) Write down the pre-order, post-order and in-order traversal. 3. a) What is the advantage of an AVL Tree over a regular Binary Search Tree? b) Construct an AVL Tree using the following data, explain each step: 80, 70, 60, 50, 40, 30, 20, 10 4. Write a C++ Program that can implement Binary Search Tree Operations, namely a) Insert a key b) Delete a key c) Inorder tree traversal d) preorder tree traversal e) post order tree traversal f) display the tree g) quit. Run the program with the following inputs and commands, and attach the output with your source program. 1. Insert 49, 37, 60, 24, 78, 5, 20, 16 in that order 2. Display the tree. Make a sketch using the results, so that sketch looks like conventional BST with root at the top and go down for left and right nodes. 3. Delete 24 from the tree and display the tree again. 4. Display the post order tree traversal sequence 5. Insert the following two keys: 70 and 29 and display the tree again. 6. Display the Inorder and Pre-order sequences one at a time. 7. Quit. Solving Recurrence Relations Dr. Alak Bandyopadhyay Alabama A & M University CS 425 LECTURE 4: Solving Recurrence Relations & Some Applications Dr. Alak Bandyopadhyay Alabama A & M University CS 425 Chapter Contents Definition of Recurrence Relations and Their Use Recurrence Relations of some specific algorithms Methods of solving Recurrence Relations Recurrence Relations A recurrence relation or function is one, that is expressed in terms of itself with a changed parameter, normally smaller. Can easily describe the runtime of recursive algorithms Can then be expressed in a closed form (not defined in terms of itself) Examples: If f(x) is a function of some variable x, then, f(x) = f(g(x)) + h(x) is a recurrence relation, where g(x) is a known function in x, e.g. f(x) = f(x/2) + lg(x) Here g(x) = x/2, and h(x) = lg(x) Example of Recurrence Relations Examples: T(N) = 2T(N/2) + 1 T(N) = T(N-1) + N Depending on the type of algorithms, different type of recurrence relations are formed. However, all the recurrence relations have two basic steps as noted in recursive algorithms: - the recursive (or repeat) step and the initial or basic step or condition, i.e. T(n) should be known for some specific value of n. Some Recurrence relations for some specific algorithms Insertion Sort best case: T(N) = T(N-1) + 1, with T(0) = 0 Insertion Sort worst case: T(N) = T(N-1) + N, with T(0) = 0 Merge Sort: T(N) = 2T(N/2) + N, T(1) = 0 Binary Search Algorithm: T(N) = T(N/2) + 1, T(1) = 1 Selection Sort: T(N) = T(N-1) + N, T(2) = 1 Strassen’s Algorithm for Matrix Multiplication: T(N) = 7T(N/2) + O(N2), with T(2) = 1 Method of Solutions Master Theorem (Applied to only specific type of equations) Substitution Method (More General Method) Master Theorem: Given the recurrence relation as: T(n) = aT(n/b) + f(n), where, a and b are positive constants such that a>=1 and b > 1, and f(n) is any function. Steps: Find x = logb(a) = ln(a)/ln(b) Compute g(n) = nx Check: a) if f(n) > g(n), asymptotically (i.e. for large values of N), then, T(n) = Q( f(n) ) b) if g(n) > f(n), asymptotically (i.e. for large values of N), then, T(n) = Q( g(n) ) c) if f(n) = Q(g(n)), i.e. they both are same order of magnitude, then T(n) = Q( f(n) *lgN) Applications of Master Theorem Use Master Theorem to solve: T(n) = 4T(n/2) + n Compare with general form of the equation, a = 4, b = 2, f(n) = n g(n) = (nlogba) logba = log24= log4/log2 = 2 (log implies log base 10) g(n) = n2 As g(n) is aysmptotically much larger than f(n) T(n) = Q(g(n)) = Q(n2) 2. T(n) = 2T(n/4) + √n Compare with the general eqn, and find that a = 2, b = 4, f(n) = √n = n1/2 logba = log42 = log2/log4 = ½ g(n) = n1/2 = f(n) Hence, T(n) = Q(lgn * g(n))= Q(lgn * n1/2 ) Substitution Method Applied to any type of recurrence relation of the form T(n) = aT(g(n)) + f(n)eq (1) with T(c) = d (c and d are constants)eq (2) where g(n) is any linear relation of n, such as n-1, n/3 etc. Steps of substitution method Step1: First change n to an auxiliary variable x so, that the original equation is transformed into T(x) = aT(g(x)) + f(x) This equation should be used as a template. Step 2: Substitute x = g(n) into both sides of the template eqn. This will help you, getting a substitution for T(g(n)) term in the original eqn. Step 4. Repeat the procedure with the transformed equation until you find a pattern, and write a generalized equation after kth step. This is explained using a few examples next pages. Examples of Substitution Method Solve T(n) = T(n-1) + n(1) with T(0) = 0 (2) Step 1: x = n-1 Put n = x in eq (1), to get T(x) = T(x-1) + x Put back x = n-1, to get T(n-1) = T(n-1 – 1) + (n-1) = T(n-2) + (n-1) Step 2: Put this expression back into eq (1) T(n) = T(n-2) + (n-1) + n(3) Step 3: Now use x = n-2, and from (1) T(x) = T(x-1) + x Put back x, T(n-2) = T(n-3) + (n-2) Step 4: Put this in eq(3), to get new expression for T(n) as T(n) = T(n-3) + (n-2) + (n-1) + n If one continues like this, the pattern after the kth step (k unknown) T(n) = T(n-k) + (n-(k-1)) + … + (n-1) + n To get k, use eq (2), by setting n – k = 0 and get k = n Using this value of k, T(n) = T(0) + (1) + 2 + … +(n-1) + n Use T(0) = 0 as given in eq (2), T(n) = 1 + 2 + 3 + .. + n = n(n+1)/2 =Q(n2) Example 2: Substitution Method Solve T(n) = 2T(n-1) + 1, with T(0) = 0 Solution: Let, x = n-1, T(x) = 2T(x-1) + 1 put back x = n-1, T(n-1) = 2T(n-2) + 1 T(n) = 2[2T(n-2) + 1] + 1 = 22T(n-2) + 2 + 1 Now take x = n-2, and once again T(x) = 2T(x-1) + 1 Put back x = n-2, T(n-2) = 2T(n-3) + 1 Putting back in revised equation for T(n) T(n) = 22T(n-2) + 2 + 1 = 22 [T(n-3) +1] + 2 + 1 = 23T(n-3) +22 + 2 + 1 Generalized k-th step: T(n) = 2kT(n-k) +2k-1 + … +22 + 2 + 1 Using T(0) = 0 condition, implying, set n-k = 0, or k = n T(n) = 2nT(n-n) +2n-1 + … +22 + 2 + 1 = 2nT(0) +2n-1 + … +22 + 2 + 1 As T(0) = 0, T(n) = 2n-1 + … +22 + 2 + 1 = (2n-1+1-1)/(2-1) = 2n – 1= Q(2n) Recurrence Tree Method Solve for T(n) = T(n/3) + T(2n/3) + cn In the tree method, construct number of branches depending on number of sub-problems with sizes as mentioned. Then continue to end with problems of size as small as possible. More Examples of Recurrence Relations and Detailed Steps of Solving Details of substitution Methods are explained here through three different examples: Recurrence Relations involving - Linear Search Algorithm - Binary Search Algorithm - Merge Sort Algorithm Ex. 1 - Linear Search Look at an element (constant work, c), then search the remaining elements… Recurrence Relations T(n) = T( n-1 ) + c “The cost of searching n elements is the cost of looking at 1 element, plus the cost of searching n-1 elements” Linear Seach (cont) Caveat: You need to convince yourself (and others) that the single step, examining an element, *is* done in constant time. Can I get to the ith element in constant time, either directly, or from the (i-1)th