University questions
Download 0.58 Mb.
|
|
1) only one disk can be moved from one peg to another peg at a time. 2) A disk can be placed only on top of a larger one . 3) A disk can be moved from top only.
void Towerof Hanoi(int n, String from, String using, String to) { if(n>0) { Towerof Hanoi(n-1, from, to, using); System.out.println(“Move disk ”+n+” from ”+from+” to ”+to); Towerof Hanoi(n-1, using, from, to); } }
There are 2 recursive call for n-1 disks and one constant time operation to move a disk from ‘from’ peg to ‘to’ peg. Let it be k1. Therefore, T(n) = 2 T(n-1) + k1 T(0) = k2 , a constant. T(1) = 2 k2 + k1 T(2) = 4 k2 + 2k1 + k1 T(2) = 8 k2 + 4k1 + 2k1 + k1 Coefficient of k1=2n Coefficient of k2=2n-1 Time complexity is O(2n)
Give the algorithm to compute factorial of n recursively. (May/June 2012) Recursive Algorithm for Factorial Function When it came to teaching recursion in programming languages in the 1980s and 1990s, the factorial function n!nn! was the classic example to explain the concept. Usually left unexplained, in a mathematical paper or book one might encounter an explanation for the n!nn! shorthand for this function along the lines of
(with 0!=1010!=1) while a computer programming book might say something like n!=1×2×…×(n-1)×nn12normal-…n1nn!=1\times 2\times\ldots\times(n-1)\times n (with the same assignment for zero factorial). Either of these suggests implementation with some kind of FOR loop. The recurrence relation n!=(n-1)!nnn1nn!=(n-1)!n with n>1n1n>1 and 1!=1111!=1 suggests a recursive implementation. Call the recursive factorial algorithm with an integer N. Test if N <= 0. If so, return 1. If not, then call the recursive factorial algorithm with N - 1, multiply the result by N and return that value. The algorithm calls itself and some mechanism is necessary for keeping track of the state of the computation. Here’s an implementation in the PASCAL programming language from Koffman’s 1981 book: FUNCTION FACTORIAL (N: INTEGER): INTEGER (* RECURSIVE COMPUTATION OF N FACTORIAL *) BEGIN (* TEST FOR STOPPING STATE *) IF N <= 0 THEN FACTORIAL := 1 ELSE FACTORIAL := N * FACTORIAL(N - 1) END; (* FACTORIAL *) Depending on the implementation, what would happen the first time FACTORIAL(N) calls itself is that the memory address of the function together with n-1n1n-1 would be pushed on to the stack. The next time n-2n2n-2 would be pushed on the stack, and so on and so forth until 0 is reached. At this point, the last instance of the function returns, the next-to-last instance pops a 1 off the stack and multiplies it by 2, the next-to-next-to-last instance pops a 2 off the stack and multiplies it by 3, pushes a 6, and so on and so forth until the first instance pops (n-1)!n1(n-1)! off the stack and multiplies it by nnn. The following table illustrates a sample run starting with N = 7:
This kind of recursion can exhaust memory (for stack space) well before any computations are performed. However, in this specific application, because factorials grow super exponetially, the bounding for integer capacity is usually far more restricting than the memory capacity. For example, using 32-bit unsigned integers and guesstimating each function call requires 16 bytes, the computation of 13! would require just 208 bytes on the stack, but the result would require 33 bits, overflowing a 32-bit unsigned integer variable. Therefore input sizes should be limited to fit within the bounds of memory and integer capacity. Find time complexity and space complexity of the following problems. Factorial using recursion and compute nth Fibonacci number using iterative statements. (4+4) (Nov/Dec 2012) Factorial - O(n) Fibonacci - O(φn) What is the worst case and average case efficiency of binary search? (May/June 2012) Algorithm BinSearch(a,n,x) //Given an array a[1:n] of elements in non decreasing // order, n>0, determine whether x is present { low : = 1; high : = n; while (low < high) do { mid : = [(low+high)/2]; if(x < a[mid]) then high:= mid-1; else if (x >a[mid]) then low:=mid + 1; else return mid; } return 0; } Time Complexity: O(logn) Explain the asymptotic notations in detail. (Nov/Dec 2012) (16) The asymptotic notation “Big on” (O). The function f(n) = O(g(n)) iff there exist positive constants C and no such that f(n)<=C * g(n) for all n, n ³n0. 
The asymptotic notation “Omega” (Ω). The function f(n) =W (g(n)) iff there exist positive constant C and no such that f(n) >=C * g(n) for all n, n ³ n0. 
The asymptotic notation “theta” (Q). Directory: snsct -> files -> CW 588ee3e3bee40 CW 588ee3e3bee40 -> University questions files -> Here are 2 diodes for each of the three sets of windings in the stator. The two diodes are facing in opposite directions, one with its north pole facing the windings and the other with its south pole facing the windings files -> Charging System Download 0.58 Mb. Share with your friends:
|