Posts
SJF
main()
{
int b[10],p[10],t[10],w[10],n,i,j,tot=0;
float avg;
printf("\n Enter the number of Process:");
scanf("%d",&n);
for(i=0;i
{
printf("\n Enter the process no:");
scanf("%d",&p[i]);
printf("\n Enter the burst no:");
scanf("%d",&b[i]);
}
for(i=0;i
{
for(j=i+1;j
{
if(b[i]>b[j])
{
int temp;
temp=p[i];
p[i] = p[j];
p[j] = temp;
temp = b[i];
b[i] = b[j];
b[j] = temp;
}
}
}
w[0] = 0;
t[0] = b[0];
for(i=1;i
{
w[i] = t[i-1];
t[i] = w[i] + b[i];
}
printf("\n\n Gantt Chart");
printf("\n\n_______________________________________________________________");
printf("\n| P%d\t|",p[0]);
for(i=1; i
printf("P%d\t|",p[i]);
printf("\n---------------------------------------------------------------\n");
printf("%d",w[0]);
printf("\t%d",t[0]);
for(i=1;i
printf("\t%d",t[i]);
printf("\n\n");
printf("\n Process \t Burst Time \t Waiting Time \t Turnaround time");
printf("\n ------- \t ---------- \t ------------ \t ---------------\n");
for(i=0;i
{
printf("\n P%d \t %d \t %d \t %d ",p[i],b[i],w[i],t[i]);
tot = tot + w[i];
}
avg = (float)tot/n;
printf("\n\n The average waiting time is %f",avg);
}
Priority Scheduling
main()
{
int b[10],p[10],t[10],w[10],prior[10],n,i,j,tot=0;
float avg;
printf("\n Enter the number of Process:");
scanf("%d",&n);
for(i=0;i
{
printf("\n Enter the process no:");
scanf("%d",&p[i]);
printf("\n Enter the burst no:");
scanf("%d",&b[i]);
printf("\n Enter the Priority:");
scanf("%d",&prior[i]);
}
for(i=0;i
{
for(j=i+1;j
{
if(prior[i]>prior[j])
{
int temp;
temp = prior[i];
prior[i] = prior[j];
prior[j] = temp;
temp=p[i];
p[i] = p[j];
p[j] = temp;
temp = b[i];
b[i] = b[j];
b[j] = temp;
}
}
}
w[0] = 0;
t[0] = b[0];
for(i=1;i
{
w[i] = t[i-1];
t[i] = w[i] + b[i];
}
printf("\n\n Gantt Chart");
printf("\n\n_______________________________________________________________");
printf("\n| P%d\t|",p[0]);
for(i=1;i
printf("P%d\t|",p[i]);
printf("\n---------------------------------------------------------------\n");
printf("%d",w[0]);
printf("\t%d",t[0]);
for(i=1;i
printf("\t%d",t[i]);
printf("\n\n");
printf("\n Process \t Burst Time \t Priority \t Waiting Time \t Turnaround time");
printf("\n ------- \t ---------- \t -------- \t ------------ \t ---------------\n");
for(i=0;i
{
printf("\n P%d \t %d \t %d \t %d \t %d ",p[i],b[i],prior[i],w[i],t[i]);
tot = tot + w[i];
}
avg = (float)tot/n;
printf("\n\n The average waiting time is %f",avg);
}
Tuesday, February 23, 2010
Thursday, February 4, 2010
daa imp questions
PART A
1) Waht is meant by optimal solution?
2) State knapsack problem
3) What is meant by divide and conquer strategy?
4) Write down the recurrence equation for binary search algorithm
5) Give two examples of real time problems that could be solved using greedy algorithm
6) Compare feasible and optimal solution
7) Give the time efficiency and drawback of merge sort algorithm
8) Write recursive algorithm to perform binary search
9) List out any two drawbacks of binary search algorithm
10) Give the recurrence equation for the worst case behaviour of merge sort
11) What is the time and space complexity of container loading problem
12) What is the time and space complexity of knapsack problem
13) What is meant by container loading problem
14) What is the time efficiency class of greedy algorithm for the knapsack problem? Justify ur answer
15) Compare the time complexity of straight method with divide and conquer method of finding the maximum and minimum
16) What are the merits of finding maximum and minimum using DAC?
17) What are the merits and demerits of binary search algorithm?
18) What are the merits and demerits of merge sort?
19) Write the pseudo code for container loading algorithm
20) Define feasibility
Part B
1) Write down the binary search algorithm and do the worst case analysis of the algorithm. Derive any intermediate formula used
2) Explain merge sort. How do you analyse it using divide and conquer principle
3) Explain merge sort with example
4) Differentiate sequential from binary search technique
5) Explain the working principle of merge sort with necessary algorithm, and simulate the algorithm with a non-trivial example
6) Write down the binary search algorithm that searches for an element in a sorted list and analyse it for its worst case behaviour. Derive all the intermediate results used
7) Solve the following instance of the knapsack problem by greedy algorithm
Item weight values
1 10 100
2 7 63
3 8 56
4 4 12
8) Give an detailed note on divide and conquer techniques
9) Write an algorithm for searching an element using binary search method. Give an example
10) Discuss the use of greedy method in solving knapsack problem
11) A) write a pseudo code for divide and conquer algorithm for merging two sorted arrays into a single sorted one. Explain with an example
b) set up an solve a recurrence relation for the number of key comparisons made by the above pseudo code.
12) How merge sort works for the following data set 100, 300.,150,450,250,350,200,400,500
13) Suppose you have 6 containers whose weights are 50, 10, 30,20,60,5 and ship whose capacity is 100. Find the optimal solution for the problem
14) Find an optimal solution to the knapsack instance n=7,m=15,(p1 ,p2)
(w1,w2,w3,w4,w5,w6,w7)=(2,3,5,7,1,4,1)
15) Find the maximum and minimum for the following set of elements using DAC technique.22
13
-5
-8
15
60
17
31
47
1) Waht is meant by optimal solution?
2) State knapsack problem
3) What is meant by divide and conquer strategy?
4) Write down the recurrence equation for binary search algorithm
5) Give two examples of real time problems that could be solved using greedy algorithm
6) Compare feasible and optimal solution
7) Give the time efficiency and drawback of merge sort algorithm
8) Write recursive algorithm to perform binary search
9) List out any two drawbacks of binary search algorithm
10) Give the recurrence equation for the worst case behaviour of merge sort
11) What is the time and space complexity of container loading problem
12) What is the time and space complexity of knapsack problem
13) What is meant by container loading problem
14) What is the time efficiency class of greedy algorithm for the knapsack problem? Justify ur answer
15) Compare the time complexity of straight method with divide and conquer method of finding the maximum and minimum
16) What are the merits of finding maximum and minimum using DAC?
17) What are the merits and demerits of binary search algorithm?
18) What are the merits and demerits of merge sort?
19) Write the pseudo code for container loading algorithm
20) Define feasibility
Part B
1) Write down the binary search algorithm and do the worst case analysis of the algorithm. Derive any intermediate formula used
2) Explain merge sort. How do you analyse it using divide and conquer principle
3) Explain merge sort with example
4) Differentiate sequential from binary search technique
5) Explain the working principle of merge sort with necessary algorithm, and simulate the algorithm with a non-trivial example
6) Write down the binary search algorithm that searches for an element in a sorted list and analyse it for its worst case behaviour. Derive all the intermediate results used
7) Solve the following instance of the knapsack problem by greedy algorithm
Item weight values
1 10 100
2 7 63
3 8 56
4 4 12
8) Give an detailed note on divide and conquer techniques
9) Write an algorithm for searching an element using binary search method. Give an example
10) Discuss the use of greedy method in solving knapsack problem
11) A) write a pseudo code for divide and conquer algorithm for merging two sorted arrays into a single sorted one. Explain with an example
b) set up an solve a recurrence relation for the number of key comparisons made by the above pseudo code.
12) How merge sort works for the following data set 100, 300.,150,450,250,350,200,400,500
13) Suppose you have 6 containers whose weights are 50, 10, 30,20,60,5 and ship whose capacity is 100. Find the optimal solution for the problem
14) Find an optimal solution to the knapsack instance n=7,m=15,(p1 ,p2)
(w1,w2,w3,w4,w5,w6,w7)=(2,3,5,7,1,4,1)
15) Find the maximum and minimum for the following set of elements using DAC technique.22
13
-5
-8
15
60
17
31
47
Wednesday, January 27, 2010
microprocessor qbank
MICROPROCESSORS AND MICROCONTROLLERS
PART A
SUBJECT CODE: CS2252
COMPUTER SCIENCE ENGINEERING IV SEMESTER/II YEAR
1) Define microporcessor
2) Define assembly language
3) Define machine language
4) Draw a microprocessor based system with bus architechture
5) Define system bus
6) Define operating system
7) Classify the signals of 8085
8) Define instruction cycle, machine cycle, T-state
9) Draw the logic diagram to generate control signals in 8085
10) List the flags in 8085
11) Define program counter
12) Define stack pointer
13) List the addressing modes of 8085
14) Classify the instructions in 8085
15) Define 1-byte, 2-byte and 3-byte instructions.
PART B
1) Draw the pin diagram of 8085 and explain the signals of 8085
2) Explain briefly the architecture of 8085
3) Explain the addressing modes of 8085
4) Explain the instruction set of 8085
5) Illustrate the steps and the timing diagram of dataflow for opcode fetch, memory read, momory write, I/O read, I/O write and interrupt acknowledge.
4:12 PM | Add a comment | Permalink | Blog it | Academic
PART A
SUBJECT CODE: CS2252
COMPUTER SCIENCE ENGINEERING IV SEMESTER/II YEAR
1) Define microporcessor
2) Define assembly language
3) Define machine language
4) Draw a microprocessor based system with bus architechture
5) Define system bus
6) Define operating system
7) Classify the signals of 8085
8) Define instruction cycle, machine cycle, T-state
9) Draw the logic diagram to generate control signals in 8085
10) List the flags in 8085
11) Define program counter
12) Define stack pointer
13) List the addressing modes of 8085
14) Classify the instructions in 8085
15) Define 1-byte, 2-byte and 3-byte instructions.
PART B
1) Draw the pin diagram of 8085 and explain the signals of 8085
2) Explain briefly the architecture of 8085
3) Explain the addressing modes of 8085
4) Explain the instruction set of 8085
5) Illustrate the steps and the timing diagram of dataflow for opcode fetch, memory read, momory write, I/O read, I/O write and interrupt acknowledge.
4:12 PM | Add a comment | Permalink | Blog it | Academic
Saturday, January 23, 2010
algorithm answers
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 we get T(n)=0(nlogn)
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 = 2k we get the roots as 2,2,1 and the time complexity as O(n log n)
9. There are two possible solutions, ω(n2 ) or O(n3).
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)
source: viveks blog
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 we get T(n)=0(nlogn)
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 = 2k we get the roots as 2,2,1 and the time complexity as O(n log n)
9. There are two possible solutions, ω(n2 ) or O(n3).
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)
source: viveks blog
Thursday, January 21, 2010
daa imp questions
(1) Write an algorithm for a given number n to generate the n’th number of the Fibonacci sequence.
-----May/June 2007
(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
-----May/June 2007
(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
os fifth exp
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);
}
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
{
if(c[i]==pat[j])
{
flag=0;
for(k=1;k
{
if(c[i+k]!=pat[k])
flag=1;
}
if(flag==0)
printf("\n The pattern %s is present in word %d", pat,count);
}
}
}
}
#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);
}
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
{
if(c[i]==pat[j])
{
flag=0;
for(k=1;k
{
if(c[i+k]!=pat[k])
flag=1;
}
if(flag==0)
printf("\n The pattern %s is present in word %d", pat,count);
}
}
}
}
Subscribe to:
Posts (Atom)
