University questions
Download 135.38 Kb.
|
- Navigate this page:
- DEPARTMENT OF COMPUTER SIENCE AND ENGINEERING (UG PG) Second Year Computer Science and Engineering, 4 th Semester UNIVERSITY QUESTIONS
- UNIT I - INTRODUCTION PART - A
- Worst Case Analysis (Usually Done)
- Average Case Analysis (Sometimes done)
- Best Case Analysis (Bogus)
- Unit II - BRUTE FORCE AND DIVIDE-AND-CONQUER PART - A
- Knapsack problem
- Unit III - DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE PART – A
- Unit V - COPING WITH THE LIMITATIONS OF ALGORITHM PART – A
- back tracking
- 8 – queens problem
- search techniques
|
S   NS COLLEGE OF TECHNOLOGY
(An Autonomous Institution) COIMBATORE – 35
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.
Linear search, also known as sequential search, is a process that checks every element in the list sequentially until the desired element is found. The computational complexity for linear search is O(n), making it generally much less efficient than binary search (O(log n)). But when list items can be arranged in order from greatest to least and the probabilities appear as geometric distribution (f (x)=(1-p) x-1p, x=1,2), then linear search can have the potential to be notably faster than binary search.
The time complexity of an algorithm is the amount of computer time it needs to run to completion. The space complexity of an algorithm is the amount of memory it needs to run to completion.
A recurrence equation is an equation or inequality that describes a function in terms of its value on smaller inputs.
It is used to describe the limiting behavior of a function when the argument tends towards a particular value (often infinity), usually in terms of simpler functions. In computational complexity theory, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size.
Once an algorithm has been devised it become necessary to show that it works it computer the correct to all possible, legal input. One simply way is to code into a program. However converting the algorithm into program is a time consuming process. Hence, it is essential to be reasonably sure about the effectiveness of the algorithm before it is coded. This process, at the algorithm level, is called "validation".
Definition: f :N→≥0 is even-tually non-decreasing if there is an integer n 0 so that f ( n ) ≤ f ( n +1) for n ≥ n 0. Definition: Let b ≥ 2beaninte-ger. f is b-smooth if it is even-tually non-decreasing and f ( bn ) ∈ O ( f ( n )). That is, there are n 0 and c so that f ( bn ) t ( n )= {a if n =1 {4 t ( n / 2 ) + bn otherwise, Show t ( n )isΘ( n 2 ).
A program is the expression of an algorithm in a programming language. Sometimes works such as procedure, function and subroutine are used synonymously program.
The time complexity of an algorithm is the amount of computer time it needs to run to completion. The space complexity of an algorithm is the amount of memory it needs to run to completion.
Guess a bound and then use mathematical induction to prove our guess correct.
Best case efficiency is the minimum number of steps that an algorithm can take any collection of data values. PART - B
There are 3 pegs ‘from’ , ‘using ‘ and ‘to’. Some disks of different sizes are given which can slide onto any peg . Initially all of those are in ‘from’peg in order of size with largest disk at the bottom and smallest disk at the top. We have to move all the disks from ‘from’ peg to ‘to’ peg . At the end ,’to’ peg will have disks in the same order of size . There are some rules : 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)
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.
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)
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). The function f(n) =q (g(n)) iff there exist positive constant C1, C2, and no such that C1 g(n) <= f(n) <= C2 g(n) for all n, n ³ n0.
Nonrecursive Algorithms:
Example: Selection sort Input: An array A[0..n-1]
min ← i
for j = i + 1 to n – 1 do if A[j] < A[min] min ← j swap A[i] and A[min] basic operation: comparison Inner loop: n-1 S(i) =∑1 = (n-1) – (i + 1) + 1 = n – 1 - i j = i+1 Outer loop: n-2 n-2 n-2 n-2 Op = ∑ S(i) = ∑ (n – 1 – i) = ∑ (n – 1) - ∑ i i = 0 i = 0 i = 0 i = 0 Basic formula: n ∑ i = n(n+1) / 2 i = 0 Op = (n – 1 )(n -1 ) – (n-2)(n-1)/2 = (n – 1) [2(n – 1) – (n – 2)] / 2 = = (n – 1) n / 2 = O(n2)
Recursive Algorithms: Steps in mathematical analysis of recursive algorithms:
Important recurrence types: Linear: One (constant) operation reduces problem size by one. T(n) = T(n-1) + c T(1) = d Solution: T(n) = (n-1)c + d Quadratic: A pass through input reduces problem size by one. T(n) = T(n-1) + cn
Logarithmic: One (constant) operation reduces problem size by half. T(n) = T(n/2) + c
n log n: A pass through input reduces problem size by half. T(n) = 2T(n/2) + cn
n! = n*(n-1)! 0! = 1 T(n) = T(n-1) + 1 T(1) = 1 Telescoping: T(n) = T(n-1) + 1
Add the equations and cross equal terms on opposite sides: T(n) = T(1) + (n-1) = n
T(n) = T(n/2) + 1 T(n/2) = T(n/4) + 1 … T(2) = T(1) + 1 Add the equations and cross equal terms on opposite sides: T(n) = T(1) + log(n) = O(log(n)) Master Theorem: A general divide-and-conquer recurrence T(n) = aT(n/b) + f (n), where f (n) Î Θ(nk) a < bk : T(n) Î Θ(nk) a = bk : T(n) Î Θ(nk log n ) a > bk : T(n) Î Θ(n (log b a)) Note: the same results hold with O instead of Θ.
Time and Space Complexity: Goals:
This laboratory exercise introduces some principles of algorithm effectiveness, including the amount of time and memory required for the algorithm. Big-O notation is introduced to provide an informal measure of the time or space required by an algorithm. These ideas are applied to the linear and binary search algorithms, discussed in the lab on searching. In considering the solution to a problem, it is natural to ask how effective that solution might be. Also, when comparing solutions, one might wonder if one solution were better than another. Altogether, one might use many criteria to evaluate such solutions, including: Accuracy: Of course, any program should produce correct answers. (If we were satisfied with wrong results, it is trivial to produce many such answers very quickly.) However, it may not be immediately clear just how accurate results should be in a specific instance. For example, one algorithm may be simple to program and may run quickly, but it only may be accurate to 5 decimal places. A second algorithm may be more complex and much slower, but may give 15 place accuracy. If 5-place accuracy is adequate for a specific application, the first algorithm is the better choice. However, if 10 or 12 place accuracy is required, the slower algorithm must be used. Efficiency: Efficiency can be measured in many ways: programmer time, algorithm execution time, memory used, and so on. If a program is to be used once, then programmer time may be a major consideration, and a simple algorithm might be preferred. If a program is to be used many times, however, then it may be worth spending more development time with a complex algorithm, so the procedure will run very quickly. Use of Memory: One algorithm may require more computer memory in which to execute. If space is a scarce resource, then the amount of space an algorithm requires should be taken into consideration when comparing algorithms. Ease of Modification: It is common practice to modify old programs to solve new problems. A very obscure algorithm that is difficult to understand, therefore. is usually less desirable than one which can be easily read and modified. For this laboratory exercise, we focus on algorithm execution time.
For successful search Best case O(1) Worst Case O(n) Average case O(n) For Unsuccessful search Best case O(n) Worst Case O(n) Average case O(n) Solve the following recurrence realtions (Nov/Dec 2012) (4+4) T(n)= T(n)= Where a and c are constants O(logn)
O(nlogn)
The difference between Big Oh, Big Omega and Big Theta. This is written not from the mathematical point of view, but the information technology point of view, so there won’t be any mathematical things in this article. I also will not handle complexity in greater detail than necessary. Algorithm complexity studies the limiting behaviour of algorithms as the input n approaches infinity. There are three main complexity classes in which algorithms can be placed: Oh, Omega and Theta. Two of them, Oh and Omega can be divided in subclasses: Big-Oh and Little-Oh and Big-Omega and Little-Omega. This article describes an easy but useful mnemonic that can be used to differentiate between the three main classes.
This one helps if you know that the letter is not actually a capital ‘o’, but the Greek capital Omicron. The Omicron looks deceptively much like the capital ‘o’: O. The mnenomic lies in the name of the Greek letter. To access the mnemonic, Omicron should be read as O-micron. Extended to a sentence, you get: ‘… is micro compared to … as n approaches infinity’. Let’s take, for example, the following notation: f(n) € (g(n)) Using the mnenomic, the following can be read: “The function f is micro compared to g as n approaches infinity.” This means that, as n approaches infinity, f is asymptotically bounded above by g(up to a constant factor).
Be mindful that this means that f(n) could very well equal g(n) for some constant factor as n approaches infinity. If the two should not be equal, use the tighter o (Little-Oh). I use the same mnemonic for this one as for the Big-Oh, but as the hole in the letter is tighter, it reminds me that o describes a tighter bound which is strictly smaller than its bound.
This mnemonic is a bit easier since the Greek letter is already used. To access it, read the Omega as O-mega. Extended to a sentence form, you can read ‘… is mega compared to … as n approaches infinity.’ Let’s take, for example, the following notation: f(n) € (g(n)) Using the mnemonic, the following can be read: “The function f is mega compared to g as n approaches infinity.” This means that, as n approaches infinity, f is asymptotically bounded below by g(up to a constant factor). Or: f(n) € g(n) k as n approaches infinity. Be mindful that this means that f(n) could very well equal g(n) for some constant factor as n approaches infinity. If the two should not be equal, use the tighter (Little-Omega). I use the same mnemonic for this one as for the Big-Omega, but as the hole in the letter is smaller, it reminds me that w describes a tighter bound which is strictly smaller than its ñ bound. This corresponds with the definition of f(n) € w (g(n)): f(n) asymptotically dominates g(n), or, more mathematically: f(n) > g(n) . k. Big-Theta: There’s no real mnemonic for this one, but when f(n) grows just as fast as g(n) asymptotically, then f(n) € (g(n)). Should the other two mnemonics fail, then the function you’re trying to evaluate is most likely in this class. Informally, use this when the asymptotic growth of two functions is equal. As there’s no such thing as Little-Theta, there’s no confusion possible on which to use.
We can have three cases to analyze an algorithm: 1) Worst Case 2) Average Case 3) Best Case Let us consider the following implementation of Linear Search.
Worst Case Analysis (Usually Done) In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched (x in the above code) is not present in the array. When x is not present, the search() functions compares it with all the elements of arr[] one by one. Therefore, the worst case time complexity of linear search would be Average Case Analysis (Sometimes done) In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of x not being present in array). So we sum all the cases and divide the sum by (n+1). Following is the value of average case time complexity. Average Case Time = 
= 
= 
Best Case Analysis (Bogus) In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location. The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be Unit II - BRUTE FORCE AND DIVIDE-AND-CONQUER PART - A
Compare x with the middle name in the book. If x comes before y, recursively look for x in the first half. Otherwise recursively look for x in the second half. The search is finished when the beginning and end of the list are within one. Best case Performance – O(1) Average Case Performance – O(log n) Worst Case Performance – O(log n)
Given a function to compute on ‘n’ inputs the divide-and-comquer strategy suggests splitting the inputs in to’k’ distinct susbsets, 1
The general rule is that program i is stored on tape Ti mod m .on any given tape the programs are stored in nondecreasing order of their lengths Greedy method control abstraction for the ordering paradigm Algorithm store(n,m) { J=0; For i=1 to n do { Write(“append program”,I,”to permutation for tape”,j); J=(j+1) mod m; } } PART - B
Unit III - DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE PART – A
PART - B
Unit V - COPING WITH THE LIMITATIONS OF ALGORITHM PART – A
PART - B
SNSCT – Department of Compute Science and Engineering Page Directory: snsct -> files -> CW 588ee3e3bee40 files -> Charging System CW 588ee3e3bee40 -> University questions Download 135.38 Kb. Share with your friends:
|
