DEPARTMENT OF
B.Tech (5 Sem) – II
th
COMPUTER SCIENCE
Design and Analysis of
Algorithms AND ENGINEERING
AGCS-21501
Tutorial Sheet 1
1. What is a data structure? Why do we need data structures? Discuss the applications of
a. Array
b. Stack
c. Queue
d. Linked List
e. Priority Queue
2. What are the various steps to write an algorithm? What are the properties of a good
algorithm? Do we need to have basic understanding of any Programming Language
before writing any algorithm?
3. What is the difference between
a. Algorithm and Flow chart
b. Algorithm and Program
4. What is brute force approach for solving a problem? What kind of problems can it solve?
What are its advantages? Discuss the example of finding a number in an array and
sorting a list of 10 numbers.
5. What are the application areas of algorithms? Discuss the applications of algorithms in
a. Computer Programming
b. Image Processing
c. Medical Science
d. Scientific Research
6. Write an algorithm for the following situations
a. Going home from college (consider the time for leaving the college).
b. Booking a movie ticket online.
7. What is meant by the efficiency of algorithm? Suppose you have 2 algorithms Algo1 and
Algo2 both for the same problem. Algo1 has O(n2) time complexity and Algo2 has O(n
log n) time complexity? Algo1 rums on machine with speed 106 Instructions/sec and
Algo2 runs on machine with speed 103 Instructions/sec. Calculate the completion time of
each algorithm when n=10000. Also calculate the time when n=1000000.
8. Sort the following list of numbers in ascending order using Insertion Sort.
a. 12,5,4,32,56,4,12,14,48,15,65,84,55,24
b. 12,51,235,145,144,155,84,23,54,88,54,99,35
9. What is meant by the complexity of an Algorithm? What is meant by the time and space
complexity? How is time complexity measured? How is space complexity measured?
Find the time and space complexity of the following codes
a. int x,y
sum=x+y
PRINT sum
if sum>10
PRINT Sum greater than 10
else
PRINT Sum less than 10
b. for i=1 to n
do PRINT “HELLO”
end for
for j=1 to n
do PRINT “HI”
for k = 1 to m
do PRINT “ACET”
end for end for.
c. FUN()
{
int i, j; for(i=1
to n) PRINT
“Hello”
}
d. FUN()
{
int i, j;
for(i=1 to n)
for (j=1 to n)
PRINT “ACET”
}
e. FUN()
{
int i=1;
for(i=1,i2<=n,i++)
PRINT “Hi”
}
f. FUN()
{i=1,s=1;
while(s<=n)
{ i++;
s=s+i;
PRINT “ACET”;
}
}
g. FUN()
{
int i, j, k, n;
for (i=1,i<=n;i++)
{
for (j=1,j<=i, j++)
{
for ( k=1;k<=100; k++)
PRINT “HI”;
}
}
}
h. FUN()
{int i, j, k, n;
for (i=1;i<=n;i++)
{
for (j=1;j<=i2;j++)
{
for (k=1;k<=n/2;k++)
{PRINT “Hi”;}
}
}
}
i. FUN()
{ for (i=1;i<n;i=i*2)
PRINT “Hi”:
}
j. FUN()
{ while (n>1)
n=n/2;
}
k. FUN()
int i,j,k;
for (i=n/2,i<=n,i++)
{
for (j=1,j<=n,j=j*2)
{
for (k=1;k<=n;k=k*2)
PRINT “Hi”;
}
}
10. For the following codes find the O notation
a. Is 2n+1 = O(2n)
b. Is 22n != O(2n)
c. 2n3+5n+17 = O(n3)
d. 27n2+16n+25=O(n2)
e. 2n+6n2+3n= O(2n)
f. 5*2n + 3n + 5 = O(2n)
