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

Great Mind Challenge 2009

Create your own WebBrowser

You can create your own web browser in just 7 lines of code. To see how to create it,


visit http://vivekvenkatesh.blogspot.com/


Have fun.

Wonderful Message from 3 idiots

Well it has been a while since i had written my last post. Now the 2010 has born and once again the same routine of life going on... I had been wondering from my early teenage whether there would be a movie lambasting the Indian Education "System" and its outrageous effects on children, its harmful effect on the minds of young buds. Then came the Aamir khan's Taare Zameen Par which deeply moved me and still remains the favorite of all hindi movies i have watched. The subject dealt in it was mainly about Dyslexia and how it had a pathetic impact on a young child's education, and the converse of how 'Education System' added fuel to the fire by making the child's life even worser(rather than lending a helping hand). Aamir Khan has to be appreciated for taking such a great subject in his movie. What I like about Aamir khan's movies is that most of his films will have a great and touching message in it, and he continues to prove it with his latest blockbuster "3 idiots" , partially adapted from Chetan Bhagat's "Five point Someone."

The subject of "Quality of Indian higher Education System" forms the core of this movie. Gone are those days when movies only contained romance between the hero and the heroine, a action sequence, dream songs.. The film revolves around 3 friends who do their higher education at "Imperial College of Engineering." The story has been perfectly furnished so as to vindicate their stand on 'Adulterated Higher Education System'. It clearly proves how engineering colleges today teach their students to "GET ONLY MARKS" rather than inculcating zeal and ardor in students to reasearch, and innovate in their field. The movie also clearly potrays the Pressure on current day students to perform. They have been moulded right from their childhood with this on their head "Perfom or Perish". Such a thought will no way help in one's betterment, instead abet them only to get marks and not to get the real essence of education. Soon after the movie the debate on Quality of higher education has started. Only such a kind of debates for a long time will bring about change that is necessary.

I would really like to thank Aamir Khan for taking another Episode on Education system and it will surely send a message to parents to allow their children pursue a career of their Interest(not only Engineering enggg engg, doctor). Hats off to the entire team.

I hope there will soon be a facebook, a twitter, a Google, an I PHONE, an XBOX completely made in India....




Travelling on the road to success,
Vivek Venkatesh

Microprocessor AK RAY BURCHANDI

Hello friends here is the embedded document of "Advanced Microprocessors and peripherals by AK ray and Burchandi." I could not find the PDF version of the book so far.. so i ve embedded the book from GOOGLE BOOKS with Limited preview. (contains Minimum mode operation of 8086 b/w the pages 20 to 25, and maximum mode taken away in the limited preview.)


Here is the book

Top GPA scorers 3rd semester

CSE 2 toppers:

The top ten GPA scorers of CSE 2 is given below (GPA not to be disclosed), in the order of their ranks.

(Rank, Name)

1. Srividhya D

2. Santhosh Kumar S

3. Srividhya V

4. Ragavendhar S, Vaijayanthimala G

5. Thamizhendi GP

6. Vivek Venkatesh G

7. Sneha Hariharan

8. Saranya B

9. Sindhuja B

10. Sriguna K, Ramya P, Shakthi Sheshadri, Sangeetha S

Overall CSE Department toppers(Rank #1 to #15)

1. Srividhya D

2. Gnanalakshmi R

3. Kalaivani N

4. Ayshwarya S

5. Jeyachitra K

6. Aroon Kumar G

7. Santhosh Kumar S

8. Srividhya V

9. Anitha K

10. Aishvarya K

11. Ragavendhar S, Vaijayanthimala G

12. Deenan Ravindra

13. Jeevitha S, Thamizhendi GP

14. Vivek Venkatesh G, Indhuja R

15. Mohana S, Nivetha R, Dhilhip Kumar P, Indhu G


Statistics

CSE 2

Total number of Students appeared - 64

Female Pass percentage - 65%(approx)

Male Pass percentage - 46%(approx)

Overall Pass percentage - 53.33%

OVERALL STATISTICS(including CSE 1, CSE 2)

Total number of Students appeared - 128 (

Female Pass percentage - 71.69%

Male Pass percentage - 45.33 %

Overall Pass percentage - 56.25%


(source - data,statistics analysed and sorted by my software.)

Disclaimer

1. The data entered here are subject to errors however carefully it has been analyzed . The data are entered only to give statistics and not to hurt anyone's sentiments.

2. These results are subject to change after reevaluation.

Interprocess Communication, Shared Memory, Process State

Interprocess Communication (IPC)

1. Mechanism for processes to communicate and to synchronize their actions.
2. Message system – processes communicate with each other without resorting to shared variables.
3. IPC facility provides two operations:
1. send(message) – message size fixed or variable
2. receive(message)
4. If P and Q wish to communicate, they need to:
1. establish a communication link between them
2. exchange messages via send/receive
5. Implementation of communication link
1. physical (e.g., shared memory, hardware bus)
2. logical (e.g., logical properties)

Direct Communication

I. Processes must name each other explicitly:

a. send (P, message) – send a message to process P

b. receive(Q, message) – receive a message from process Q

II. Properties of communication link

a. Links are established automatically

b. A link is associated with exactly one pair of communicating processes

c. Between each pair there exists exactly one link

d. The link may be unidirectional, but is usually bi-directional

Indirect Communication

1. Messages are directed and received from mailboxes (also referred to as ports)
1. Each mailbox has a unique id
2. Processes can communicate only if they share a mailbox.
2. Properties of communication link
1. Link established only if processes share a common mailbox
2. A link may be associated with many processes
3. Each pair of processes may share several communication links
4. Link may be unidirectional or bi-directional
3. Operations
1. create a new mailbox
2. send and receive messages through mailbox
3. destroy a mailbox
4. Primitives are defined as:

send(A, message) – send a message to mailbox A

receive(A, message) – receive a message from mailbox A

1. Mailbox sharing
1. P1, P2, and P3 share mailbox A
2. P1, sends; P2 and P3 receive
3. Who gets the message?
2. Solutions
1. Allow a link to be associated with at most two processes
2. Allow only one process at a time to execute a receive operation
3. Allow the system to select arbitrarily the receiver. Sender is notified who the receiver was.

Synchronization

1. Message passing may be either blocking or non-blocking
2. Blocking is considered synchronous
1. Blocking send has the sender block until the message is received
2. Blocking receive has the receiver block until a message is available
3. Non-blocking is considered asynchronous
1. Non-blocking send has the sender send the message and continue
2. Non-blocking receive has the receiver receive a valid message or null

Buffering

Queue of messages attached to the link; implemented in one of three ways

1. Zero capacity – 0 messages
Sender must wait for receiver (rendezvous)

2. Bounded capacity – finite length of n messages
Sender must wait if link full

3. Unbounded capacity – infinite length
Sender never waits

Shared Memory

In computing, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors. Using memory for communication inside a single program, for example among its multiple threads, is generally not referred to as shared memory.

In computer hardware, shared memory refers to a (typically) large block of random access memory that can be accessed by several different central processing units (CPUs) in a multiple-processor computer system.

A shared memory system is relatively easy to program since all processors share a single view of data and the communication between processors can be as fast as memory accesses to a same location.

The issue with shared memory systems is that many CPUs need fast access to memory and will likely cache memory, which has two complications:

* CPU-to-memory connection becomes a bottleneck. Shared memory computers cannot scale very well. Most of them have ten or fewer processors.

* Cache coherence: Whenever one cache is updated with information that may be used by other processors, the change needs to be reflected to the other processors, otherwise the different processors will be working with incoherent data (see cache coherence and memory coherence). Such coherence protocols can, when they work well, provide extremely high-performance access to shared information between multiple processors. On the other hand they can sometimes become overloaded and become a bottleneck to performance.

The alternatives to shared memory are distributed memory and distributed shared memory, each having a similar set of issues.

Process State

1. As a process executes, it changes state

a. new: The process is being created

b. running: Instructions are being executed

c. waiting: The process is waiting for some event to occur

d. ready: The process is waiting to be assigned to a processor

e. terminated: The process has finished execution

I hope this is useful for your assignment.