ADVANCED ALGORITHMS - WordPress.com

ADVANCED ALGORITHMS REVIEW OF ANALYSIS TECHNIQUES (UNIT-1) 1 1. ALGORITHM : is a sequence of unambiguous instructions for solving a problem in a finite amount of time. Ex-1 : Write an algorithm to find the factorial of a given number n. Ex-2 : Write an algorithm for find the value of

m power n. 2 Ex-3 : Write an algorithm for finding the GCD of (m,n). Ex-4 : Find the GCD of 60, 24 using the method of common prime factors. Ex-5 : Find the minimum distance between any two elements in the array of size n. 3 ASYMPTOTIC NOTATION

1.1. What is the meaning of asymptotic. Consider a curve such as y = 1 / x As x increases, y decreases. The positive x-axis is an asymptote of the curve. As you continually increase x towards infinity, the value of y gets closer and closer to zero. Hence the curve gets closer and closer to the x-axis but never reaches it. We say the curve is asymptotic 4 1.2 Asymptotic Complexity : is a way of expressing the main component of the cost of an algorithm,

using idealized units of computational work. Ex-6 : Sorting the deck of cards. Cost Formula : 52 + 51 + 50 + + 2 So, CF = N(N+1) / 2 - 1 = (N2) + (N) 1 Here, the term N2 is dominating the CF. So, the behavior is said to be O(N2) . 5 1.3 Big-O Notation : f(n) - the cost function of an algorithm. g(n) - the cost function of another algorithm. Here, if f(n) <= g(n), then the algorithm with Cost Function f is faster than the other. Note : The Big-O is the formal method of

expressing the upper bound of an algorithms running time. 6 Definition : For non-negative functions f(n) and g(n), if there exists an integer n0, and a constant c > 0 such that for all integers n >= no 0 <= f(n) <= c g(n), then f(n) is Big-O of g(n). This is denoted as : f(n) = O(g(n)) Ex-7 : Let f(n) = 3n + 2, g(n) = n, c = 4 Show that g(n) is Upper Bound of f(n).

7 1.4 Big- Notation : For non-negative functions f(n) and g(n), if there exists an integer n0, and a constant c > 0 such that for all integers n > no f(n) >= c g(n), then f(n) is Big- of g(n). This is denoted as : f(n) = (g(n)) Ex-8 : Let f(n) = 3n + 2, g(n) = n, c = 3 Show that g(n) is Lower Bound of f(n). 8

1.5 Theta Notation : Def : For non-negative functions f(n) and g(n), if there exists an integer n0, and two constants c1,c2 > 0 such that for all integers n >= no c1 g(n) <= f(n) <= c2 g(n), then f(n) is Theta of g(n). This is denoted as : f(n) = (g(n)) Ex-9 : Let f(n) = 3n + 2, g(n) = n, andc1 = 3, c2 = 4 Find the probable value of n0. 9 Note : For non-negative functions, f(n) and g(n),

f(n) is theta of g(n), iff f(n) = O(g(n)) and f(n) = (g(n)) Ex-10 : Compare the two functions N2 and 2n /4 for various values of n. Determine when the second becomes larger that the first. Ex-11 : Determine the frequency counts for all statements in the following algorithms. s=0 for i = 1 to n do s = s + i; 10 Ex-12 : Determine the frequency counts for all statements in the following algorithms. x = 0;

n = 5; for i = 1 to n do for j = 1 to i do for k = 1 to j do x = x + 1; 1.6 Little-o Notation : Def : For non-negative functions f(n) and g(n), if there exists an integer n0, and a constant c > 0 such that for all integers n >= no 0 <=f(n) < c g(n), then f(n) is Little-o of g(n). This is denoted as : f(n) = o(g(n)) 11 Note : Let f(n) = 2n2 and g(n) = n2 and

c=2 Here, f(n) = O (g(n)) - Big-O But, f(n) o(g(n)) - little-o If f(n) = 2n & g(n) = n2, and c = 3, then f(n) = o(n2) Ex-13 : Let f(n) = 3n + 2 , g(n) = n2 and c = 6 Show that 3n+2 = o(n2) Note : For non-negative functions, f(n) and g(n), f(n) is little o of g(n), if and only if, f(n) = O (g(n)) and f(n) ( g(n) ) [ strict upper bound, no lower bound] 12 1.7 Little-Omega Notation : Def : For non-negative functions f(n) and g(n), if there exists an integer n0, and a constant c > 0 such that

for all integers n > no 0 <= c g(n) < f(n), then f(n) is Little- () of g(n). This is denoted as : f(n) = (g(n)) Note : Consider f(n), g(n) and h(n) are non-negative functions. here, f(n) = (g(n)) and g(n) = (h(n)) imply f(n) = (h(n)) 13 Ex-14 : Let f(n) = 3n + 2, g(n) = n and c = 3 Show that 3n+2 = (n) Note : For non-negative functions, f(n) and g(n), f(n) is little of g(n), if and only if f(n) = (g(n)) and f(n) ( g(n) ) [ strict lower bound, no upper bound] Ex-15 : Find the (n2) of (1/2) n2 - 3n.

Show that (1/2) n2 - 3n = (n2). Find C1 and C2. * * * * * 14 2. Standard Notations & Common Functions 2.1 Monotonicity : A function f(n) is monotonically increasing if m <= n implies f(m) <= f(n). A function f(n) is monotonically

decreasing if m <= n implies f(m) >= f(n). A function f(n) is strictly increasing if m < n implies f(m) < f(n). A function f(n) is strictly decreasing if m < n implies f(m) > f(n). 15 2.2 Floors & Ceilings: For any real number x, we denote the greatest integer less than or equal to x by x, (read as the floor of x) and the least integer greater than or equal to x by x, (read as the ceiling of x). For all real x, we have x1 < x x x < x+1

For any integer n, we have n/2 + n/2 = n .(2) .(1) Ex-16 : If x = 2.34 then Find the floor and Ceiling of x. 16 2.3 Modular Arithmetic: For any integer a and any positive integer n, the value a mod n is the remainder (or residue) of the quotient a/ n. Here, a mod n = a - na/n Ex-17 : Let a = 25 & n = 7,

Find the value of a mod n. 2.4 Exponentials : For all real a > 0, m, and n, we have a) a0 = 1 b) a1 = a c) a-1 = 1/a d) (am)n = amn e) (am)n = (an)m f) am an = am+n 17 2.5 Polynomials : Given a nonnegative integer d, a polynomial in n of degree d is a function p(n) of the form : d p(n) = a ai ni i=0 where the constants a0, a1, ., ad are the coefficients of the polynomial and ad 0.

2.6 Logarithms : The following are some of the notations : a) lg n = log2n b) ln n = logen c) lgkn = (lg n)k d) lg lg n = lg (lg n) 18 For all real a, b, c > 0, and n, we have e) a = blogb a f) logc(ab) = logca + logcb g) logban = n log ba h) logba = logca / logcb i) logb(1/a) = - logba j) logba = 1 / logab

k) alogbc = clogba A simple series expansion is : Ln(1+x) = x (x2/2) + (x3/3) - (x4/4) + (x5/5) - Here |x| < 1. 19 2.7 Factorials : The notation n! is defined for integers n 0 as n! = 1 if n = 0 = n. (n-1)! if n > 0 Thus, n! = 1.2.3n 2.8 Functional Iteration : We use the notation f(i)(n) to denote the function

f(n) iteratively applied i times to an initial value of n. Formally, let f(n) be a function over the reals. 20 For non-negative integers i, we recursively define f(i)(n) = n = f ( f(i-1)(n) ) if i = 0 if i > 0 Ex-18 : Let f(n) = 2n. g(n) = 2n+3 Then find the values of f(i)(n), g(i)(n) ? 2.9 The Iterated Logarithmic Function : The notation lg*n (read as log star of n) to denote The iterated logarithm, defined as :

Let lg(i)n be the logarithm function applied i times in succession, starting with argument n. 21 i.e., log(0)n = n log(1)n = log n log(2)n = log (log n) log(3)n = log (log (log n)) log(k+1)n = log (log(k)n) Thus we define the iterated logarithm function as : Log *n : = 0 , if n <= 1 : = 1 + Log * (log n), if n > 1. lg*2 = 1,

lg*16 = 3, lg*4 = 2 lg*65536 = 4 lg*(265536) = 5 22 The table for x, log star x is as follows : X : (-,1] Lg* x : 0 (1,2] (2,4] (4,16] (16,65536] (65536, 265536]

1 2 3 4 5 2.10 Fibonacci Numbers : Def : F0 = 0, F1 = 1, Fi = Fi-1 + Fi-2 for i 2 Thus, each fibonacci number is the sum of its previous two numbers. Ex : 0,1,1,2,3,5,8,13,21,34, Find the next five fibonacci numbers. 23

Golden Ratio : Fibonacci Numbers are related to the golden Ratio 1 and its conjugate 2, which are the two roots of the equation : x2 = x + 1 The values of 1 and 2 are : 1 = (1 + 5) /2 = 1.618 (Golden Ratio) 2 = (1 - 5) /2 = - 0.618 Let x = 2, y = (1 + 5) = (1 + 2.236) = 3.236 Draw a rectangle for (x,y), (x,y-x), 24 The relationship between FN and GR : In the above diagram, we can see that

y/x = x / (y-x) ..(1) In Fibonacci Sequence : For large values of n, we have Fn / Fn-1 = Fn-1 / Fn-2 ..(2) 25 But, Fn = Fn-1 + Fn-2 Fn-2 = Fn Fn-1 So, Fn / Fn-1 = Fn-1 / Fn-2 Fn / Fn-1 = Fn-1 / (Fn - Fn-1) If we replace, Fn with y and Fn-1 with x, we have y / x = x / (y x)

which is Golden Ratio. Compute any number in Fibonacci Sequence : Fn = n / 5 where F0 = 0, F1 = 1, F2 = 1, F3 = 2,.. * * * * * 26 3. Recurrences & Solutions of Recurrence Equations : 3.1 Divide-and-Conquer :

Divide : the problem into a number of subproblems that are smaller instances of the same problem. Conquer : the subproblems by solving them recursively Combine : the solutions to the subproblems into the solution for the original problem. 27 3.2 Recurrences : A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs. Ex-19 : The recurrence equation for Fibonacci is : F0 = 0, F1 = 1 Fi = Fi-1 + Fi-2 for i 2 Ex-20 :

Find the value of the recurrence equation g(0) = 0 g(n) = g(n-1) + 2n 1 using iteration. 28 3.3 Recurrence Equation : A homogeneous recurrence equation is written as : a0tn + a1tn-1 + . . . . + aktn-k = 0. Ex-21 : tn 3tn-1 4tn-2 = 0, for n >= 2. {Initial condition: t0=0, t1=1} Characteristic equation: xn 3x(n-1) 4x(n-2) = 0, or, x(n-2) [x2 3x 4] = 0,

or, x2 3x 4 = 0, or, x2 + x 4x 4 = 0, or, x(x+1) 4(x+1) = 0, or, (x+1)(x-4) = 0, Therefore, roots are, x = -1, 4. 29 So, the general solution of the given recurrence equation is: tn = c1*(-1)n + c2*(4n) Use t0 = c1 + c2 = 0, and t1 = -c1 + 4c2 = 1. Solve for c1 and c2, c1 = -(1/5), c2 = (1/5). So, the particular solution is: tn = (1/5)[4n (-1)n] = (4n) NOTE : The general solution for the original

recurrence equation is: tn = i=1kcirin 30 Inhomogeneous recurrence equation a0tn + a1tn-1 + . . . . + aktn-k = bnp(n), where b is a constant and p(n) is a polynomial of order n. Note : Homogenize the given equation to an equivalent homogeneous recurrence equation form. Ex-22 : Solve tn 2tn-1 = 3n. The concerned Homogeneous Equation is : tn+1 5tn + 6tn-1 = 0 Characteristic equation:

0. x2 5 x + 6 = General solution of the given RE is: 31 Ex-23 : Solve tn 2tn-1 = n. .(1) Replace n with n+1 tn+1 2tn = n+1 .(2) Subtract (1) from (2) : tn+1 3tn + 2tn-1 = 1 Replace n with n+1 tn+2 3tn+1 + 2tn = 1

.(3) ..(4) Subtract (3) from (4). tn+2 4tn+1 + 5tn - 2tn-1 = 0 ..(5) Now it is a homogeneous recurrence equation 32 3.4 Analysis of Insertion Sort : Input: A sequence of n numbers _a1, a2, . . . , an_. Output: A permutation (reordering) a1, a2, . . . , an of the input sequence such that a1< a2 < . . . < an Ex-23:

524613 254613245613 245613 124563 123456 INSERTION-SORT(A) 1) for j 2 to n 2) do key A[ j ] 4) i j - 1 5) While i> 0 and A[i] > key 6) do A[i+1] A[i] 3)/* Insert A[ j ] into the sorted 7) ii-1 sequence A[1 . . j 1]. */ 8) A[i+1] key 33

Statement No 1 2 3 4 C1 C2 0 C4 Cost Times n n-1 n1

n-1 5 C5 tj j=2 to n 6 C6 (tj-1) j = 2 to n 7 C7 (tj-1)

j = 2 to n 8 C8 n-1 34 The running time of the algorithm is (cost of statement) (no. of times statement is for all statements executed) Let T (n) = running time of INSERTION-SORT. T (n) = c1 n + c2 (n 1) + c4 (n 1) +

C5 tj + C6 (tj - 1 ) + C7 (tj - 1 ) + j=2 to n j=2 to n j=2 to n c8 (n 1). 35 Best case: The array is already sorted. Always find that A[i ] key upon the first time the while loop test is run (when i = j 1). All t j are 1. Running time is T (n) = c1n + c2(n 1) + c4(n 1) + c5(n 1) + c8(n 1)

= (c1 + c2 + c4 + c5 + c8)n (c2 + c4 + c5 + c8) Can express T (n) as an +b for constants a and b (that depend on the statement costs ci ) T (n) is a linear function of n. 36 Worst case: The array is in reverse sorted order. Always find that A[i ] > key in while loop test. Have to compare key with all elements to the left of the j th position compare with j 1 elements. Since the while loop exits because i reaches 0, there the j 1 tests tj = j . tj = j j=2 to n j=2 to n and (tj -1) j=2 to n

= (j - 1) j=2 to n Here j = [n(n+1)/2] - 1 j=2 to n 37 Letting k = j 1, we see that (j 1) = k = n(n-1)/2 j=2 to n k=1 to n-1 So, Running Time is : T (n) = c1n + c2(n 1) + c4(n 1) + C5 [n(n+1)/2 - 1] + C6 [n(n-1)/2] + C7 [n(n-1)/2] + c8 (n 1) = [c5/2 + c6/2 + c7/2] n2 + [c1 + c2 + c4 + C5/2 c6/2 c7/2 + c8] n [c2+c4+ c5+c8] Can express T (n) as an2 + bn + c for constants a, b, c (that

again depend on statement costs) T (n) is a quadratic function of n. 38 3.5 Recurrence Relations : A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely : a0, a1, a2, , an-1, for all integers n with n n0, where no is a nonnegative integer. Ex-24 : Is an = 3n, the solution of the recurrence relation, where an = 2. an-1 an-2. for n = 2,3,4 Ex-25 : Is an = 5, the solution of the recurrence relation, where an = 2. an-1 an-2. for n = 2,3,4 39

Ex-26 : Some one deposits Rs. 10,000 in a savings account at a bank yielding 5% per year with interest compounded annually. How much money will be in the account after years. 30 Ex-27 : Let an denote the number of bit strings of length n that do not have two consecutive 0s (valid strings). Find a recurrence relation and give initial conditions for the sequence {an}. 40 Ex-28 : What is the solution of the recurrence relation for the following.

an = an-1 + 2an-2 with a0 = 2 and a1 = 7. Find its Characteristic Equation. Ex-29 : Prove that the following is explicit formula for Fibonacci Numbers. fn= (1/5)[(1+5)/2]n - (1/5)[(1-5)/2]n Find its Characteristic Equation. 41 Ex-30 : Find the solution of recurrence relation an = 6an-1 - 9an-2 with a0 = 1 and a1 = 6. The Characteristic Equation is : r2 -6r+9=0 The only root is 3. Hence the solution to the RR is : an = c1 3n + c2 n 3n The Value of C1 = 1 and C2 = 1 Solution : an = 3n + n 3n

42 3.6 Solving Recurrences : Ex-31 : Find number of calls for a plain recursive Fibonacci To compute the Fibonacci numbers fn, f0 = 0, f1 = 1, and fn = fn1 + fn2, for n > 1. Denote by cn = #calls to compute fn. c2 = 2, c3 = 4 = 22, c4 = 8 = 23 Following the recursion: cn = cn1 + cn2 + 2 = . So, the value of cn is O(2n). 43 a) The Substitution Method The substitution method for solving recurrences consists of two steps:

1 Guess the form of the solution. 2 Use mathematical induction to find constants in the form and show that the solution works. We substitute the guessed solution for the function when applying the inductive hypothesis to smaller values. Hence, the name substitution method. We can use the substitution method to establish either upper or lower bounds on a recurrence. 44 Ex-32 : Solve T(n) = 2T(n/2) + n Solution : Guess T(n) cn log n for some constant c (that is, T(n) = O(n log n)) Base case: we need to show that our guess holds for some base case (not necessarily n = 1, some small n is ok). Ok, since function constant for small constant n. Assume holds for n/2:

T(n/2) c. (n/2) log(n/2) Prove that holds for n: T(n) cn log n , if c >=1. 45 Ex-33 : Solve T(n) = 2 1 <= n < 3 = 3. T( n/3 ) + n n >= 3 Prove that T(n) = O(n log n) for all n >= m. Here we have to show that T(n) <= c n log n Observe T(n) = 3 T ( n/3 ) + n <= 3. c n/3 log n/3 + n

<= 3. c (n/3) (log n 1) + n = c n log n c n + n But, T(n) <= c n log n, if (- cn + n) <= 0 implies c >= 1 Let m = 3 implies n = 3. 46 Here T(3) < = 3 c implies c >= T(3) / 3 But, T(3) = 9 implies C >= 3 Case-1 : Since T(3) = 3 . T( n/3) + 3 = 9 cn log n = 3.3 log 3 = 9 proved. Case -2 : Let n > 3. T(n) = 3. T( n/3) + n <= 3.3. n/3. log n/3 + n <= 9. n/3. ( log n 1) + n = 3 n (log n 1 ) + n = 3 n log n 3 n + n = 3 n log n 2 n

<= 3 n log n proved 47 b) The Recurrence-Tree Method A recursion tree is useful for visualizing what happens when a recurrence is iterated. It diagrams the tree of recursive calls and the amount of work done at each call. solving recurrences : expanding the recurrence into a tree summing the cost at each level applying the substitution method. Ex-34 : Solve T(n) = 2T(n/2) + n2. 48

The recursion tree for this recurrence has the following form, which has the solution O(n2). T(n) = 2T(n/2) + n2. n2 n2 (n/2)2 (n/2)2 n2/2 (n/4)2 (n/4)2

n2 /4 (n/8)2 (n/8)2 . n2 /8 49 Ex-35 : Draw the Recurrence Tree for the following. T(n) = 3T(n/4) + cn2. cn2 c(n/4)2

c(n/16)2 cn2 c(n/4)2 c(n/16)2 c(n/4)2 c(n/16)2 (3/16)cn2 (3/16) 2cn2 The last term here is : (3/16) i cn2 The above recurrence Tree has the order of O(n2)

50 Ex-36 : Draw the Recurrence Tree for the following. T(n) = 8T(n/2) + n2. [T(1)=1] T(n) = n2 + 8 T(n/2) = n2 + 8 [ (n/2)2 + 8. T(n/22) ] = n2 + 8 (n2/4) + 82 T(n/22) = n2 + 2 n2 + 82 T(n/22) = . = n2 + 2 n2 + 22 n2 + 83 T(n/23) = = n2 + 2 n2 + 22 n2 + 23 n2 + .. + 8i T(1) Here, n/2i = 1 implies i = log n Therefore, last term = 8log n 51 Here, T(n) =

n2 + 2 n2 + 22 n2 + 23 n2 + .. + 2log n-1 n2 + 8log n = 2k n2 + 8log n k = 0 to log n 1 = n2 2k + (23)log n k = 0 to log n 1 Here, The first term is of the order (n).n).). (23)log n = (2log n)3 = n3

Therefore T(n) = n2 (n).n).) 52

Recently Viewed Presentations

  • Tech Day 2017 21st Century Skills: Using technology

    Tech Day 2017 21st Century Skills: Using technology

    Uses for the Classroom. Talking to students in another country in language class. Playing Kahoot! quizzes with other classes. Allowing students to call into class when they're not able to get to school (because of illness, disabilities, snow, etc.)
  • ORGANOGRAM (Organization Chart) Freight Systems Co. Ltd. (LLC)

    ORGANOGRAM (Organization Chart) Freight Systems Co. Ltd. (LLC)

    Head Count: 03 FREIGHT SYSTEMS. Sushant. Malik (Head - MENA, NA, Europe ,Pakistan & COE) Viji. John . Regional Manager - Middle East. Prasad . Gopinath
  • Start on the Bates Home Page - Bates College

    Start on the Bates Home Page - Bates College

    First Click the Quad and then Garnet Gateway. Sign In to the Garnet Gateway Using. Your . User Id (your Bates ID Number) and your previously selected . PIN. Click on Employee Menu to Begin. Put your mouse pointer over...
  • Zestaw narzędzi szkoleniowych w zakresie GPP7.2.

    Zestaw narzędzi szkoleniowych w zakresie GPP7.2.

    niezadrukowany papier używany do pisania, drukowania i kopiowania (maks. gramatura: 170 g/m2) Produkty nieobjęte zakresem. notatniki. bloki rysunkowe. kalendarze. instrukcje obsługi. Moduł 7.2 — Papier do kopiowania i papier graficzny.
  • IB History Internal Assessment

    IB History Internal Assessment

    - See example 2) Or…you can write a narrative - See example * History IA * Part B SHOW THE ORIGINS OF EACH STATEMENT: Laver argued that Stalin was manipulative….., The Five-year plan was well organized (Laver, 45) This is...
  • 4 - storage.googleapis.com

    4 - storage.googleapis.com

    Proteoglycans are made of a protein core with glycosaminoglycans hanging off from the core (see handout) Structural Elements of Connective Tissue. Ground substance. Medium through which solutes diffuse between blood capillaries and cells. Components:
  • Transition Metals and Coordination Chemistry

    Transition Metals and Coordination Chemistry

    Transition Metals and Coordination Chemistry - Ch. 19 2. Which of the following can act as a chelate? Circle all that apply. a. NH 2 CH 2 CH 2 NH. 2. b. C 2 O 4. 2-. c. NH 2...
  • Lecture 18 Circulatory System I 21-1  Matrix between

    Lecture 18 Circulatory System I 21-1 Matrix between

    Circulatory System I Blood Matrix between the cells is liquid Hemopoiesis Process of formation of blood cells Tissue found in marrow cavity and spongy bone Yellow Red Blood Vessel Structure Arteries Elastic, muscular, arterioles, capillaries Capillaries Most of exchange between...