University questions
Download 0.58 Mb.
|
- Navigate this page:
- DEPARTMENT OF COMPUTER SIENCE AND ENGINEERING (UG PG) Second Year Computer Science and Engineering, 4 th Semester
- UNIT I - INTRODUCTION PART - A
|
S   NS COLLEGE OF TECHNOLOGY
(An Autonomous Institution) COIMBATORE – 35
Define Big ‘Oh’ notation. (May/June 2012) 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. What is meant by linear search? (May/June 2012) 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. Differentiate Time complexity from Space complexity. (Nov/Dec 2012) 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. What is a Recurrence Equation? (Apr/May 2010) A recurrence equation is an equation or inequality that describes a function in terms of its value on smaller inputs. What is the use of asymptotic notations? (Apr/May 2011) 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. Define algorithm validation. (Nov/Dec 2012) 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". State the smoothness rule. (Nov/Dec 2012) 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 ). What do you mean by algorithm? (May/June 2013) A program is the expression of an algorithm in a programming language. Sometimes works such as procedure, function and subroutine are used synonymously program. Define time efficiency and space efficiency. (May/June 2012) 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. What is called Substitution method? (May/June 2012) Guess a bound and then use mathematical induction to prove our guess correct. Forward substitution Backward substitution What is best case efficiency? (May/June 2012) Best case efficiency is the minimum number of steps that an algorithm can take any collection of data values. PART - B Discuss briefly the sequence of steps in designing and analyzing an algorithm. (6) (Apr/May 2011) Space complexity Time complexity Measuring input size Measuring running time Computing best, average and worst case Computing order of growth of algorithms Explain the necessary steps for analyzing the efficiency of recursive algorithm. Derive the recurrence relation for Tower of Hanoi problem. (10) (Apr/May 2011) 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 : 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:
|