note : Question 1 DAA assignment

there is a space before the expression "s<-s+i"

DAA Assignment Questions

Question 1


Consider the algorithm :
Algorithm mystery(n)
//Input : A non negative integer
s<-0
for i<-1 to n do
s<-s+i
return s

a) What does this algorithm compute ?
b)What is its basic operation ?
c)How many times is the basic operation executed ?
d)What is the efficiency class of the algorithm ?
e)Suggest an improvement if possible.

Question 2

Consider the following recursive algorithm
ALGORITHM S(n)
//Input: A positive integer n
//Output: The sum of the first n cubes
if n = 1 return 1
else return S(n - 1) + n * n * n
a. Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed.
b. How does this algorithm compare with the straightforward non-recursive algorithm for computing this sum?


Question 3

How many comparisons will be made by the Brute Force technique for each of the following cases :
1) Binary text of 1000 zeros.
Patterns:
a) 00001 b) 10100 c) 10001

Question 4

Consider the problem of counting in a given text , the no. of substrings that start with 'a' and end with 'b'.Design a Brute Force algorithm for this problem and determine its efficiency class

Software Engineering Slides (1-6)

daa slides

daa lab manual

networking slides

os & graphics lab manual