MGM and IV photos

Hi friends i have uploaded some photos taken during our IV,

You can also add if u wish to do so...





More photos to be uploaded soon..

DAA Solutions

1. Algorithm for nth number in Fibonacci series

Read n

f1 <- -1

f2 <-1

i <- 0

while i<=n

f3 <- f1+f2

f1 <- f2

f2 <- f3

i <-i + 1

End while

Display f3

3. Recursive function to find the factorial

FUNCTION FACTORIAL (N: INTEGER): INTEGER

BEGIN

(* TEST FOR STOPPING STATE *)

IF N <= 0 THEN

FACTORIAL := 1

ELSE

FACTORIAL := N * FACTORIAL(N - 1)

END

4. If lim f(n)/ g(n) = 0 then f(n) = O(g(n))

n->∞ = ∞ then f(n) = ω(g(n))

= constant then f(n) = θ(g(n))

Here

Lim n+n logn/ n.n^(1/2) if we apply L hoptial’s rule we get 0, therefore

n->∞

n+n log n = O (n.n^(1/2))

In this way computing the limit helps us in comparing the order of growth of 2 specific function.

5. Algorithm to find the number of binary digits

Recursive procedure:

Function F(X: integer)

{

If X= =0 or X= = 1 Then

Return 1;

Else

Return 1+ F(X/2);

}

End Function

Analysis:

T(n) = 1 + T(n/2)

Solving this recurrence equation by substitution method I get the roots as 1 and 1 and the efficiency class as O(log n)

If it is solved by Master method again we get it as O(log n)..

6. Linear search – In class notes

7. Algortihm for multiplication of two matrices

MATRIX-MULTIPLY(A, B)

1 n ← rows[A]

2 let C be an n × n matrix

3 for i ← 1 to n

4 do for j ← 1 to n

5 do ci j ← 0

6 for k ← 1 to n

7 do ci j ← ci j + aik · bkj

8 return C

8. substituting n = 2^k we get the roots as 2,2,1 and the time complexity as O(n log n)

9. There are two possible solutions, ω(n² ) or O(n³).

10. 1. Algorithm computes sum of squares of 1 to n numbers.

2. Basic operation(inside for loop)
3. basic operation executed 'n' times.
4. Efficiency class – O(n)

Disclaimer - The solutions here need not be right.

Download the Solution

Good day at MGM

Hi friends,

Today we had a splendid day out at MGM (so called Industrial Visit..lol), I hope this remains one of our memorable days....Lets hope we will have such great occasions in the future.. Soon let us plan to move out of Chennai and even out of TN if possible.....

I will soon upload photos here, and u can also upload if u wish to do so.......

Happy 2 see a very good cooperation from everyone.....


Traveling on the Road to Success,

G.Vivek Venkatesh

Simulation of "ls" and "grep" commands

Simulation of ls command

#include <stdio.h>

#include <sys/types.h>

#include <dirent.h>

main(int age, char *argv[])

{

DIR *dir;

struct dirent *rddir;

printf(“/n Enter directory with outoput command”);

dir=opeindir(argv[1]);

while((rddir=readdir(dir))!=NULL)

{

printf(“%s\t”,rddir->d_name);

}

closedir(dir);

}

Simulation of GREP command

#include <stdio.h>

#include <stdlib.h>

main()

{

FILE *fp;

char c[100], pat[10];

int l,i,j=0,count=0,len,k,flag=0;

printf("\n Enter the pattern");

scanf("%s", pat);

len=strlen(pat);

fp=fopen("nn.txt","r");

while(!feof(fp))

{

fscanf(fp,"%s",c);

l=strlen(c);

count++;

for(i=0;i<l;i++)

{

if(c[i]==pat[j])

{

flag=0;

for(k=1;k<len;k++)

{

if(c[i|k]!=pat[k])

{

flag=1;

}

if(flag==0)

printf("\n The Pattern %s is present in word %d",pat,count");

}

}

}

}

DAA Important Questions

(1) (1)Write an algorithm for a given number n to generate the n’th number of the Fibonacci sequence.

-----May/June 2007

(2) (2) (A) what is pseudo code? Explain with an example [ 8 marks ]

(B) Find the complexity C(n) of the algorithm for the worst, best and average case

{ evaluate average case complexity for n=3, where n is the number of inputs } [ 8 marks ]

(3) Write a recursive function to find the factorial of a number n ---> 2 mark
April/May 2008

(4) How does computing the limit help in comparing the order of growth of 2 specific function?
Compare the orders of growth of n+nlogn and n.n^(1/2)
April/May 2008

(5) Write an algorithm to find the number of binary digits in n's binary representation and analyse the same
---> 8 mark

(6) write an algorithm to search linearly for an element X in an ordered list of ‘n’ entries. What is the best , worst, average case analysis and justify your answer?

(7) Write an algorithm that finds the product of 2 matrices

-->2marks Nov/Dec 2004

(8) Solve the following recursive relation

Q(n) = n-1 + 2Q(n/2) and given Q(1) =0. Assume that Q is defined for all powers of 2

(9) Find the order of n^2 + logn

->2marks April/May 2005

(10) Consider the following algorithm

Mystery(n)

//Input: A non-negative integer n

S<-0

For i<-1 to n do

s<- s + i*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 this algorithm ?

e) Suggest improvements for this algorithm and justify your improvement by analysing its efficiency

May/June2009