lOMoARcPSD|38490560
Daa unit 1 notes
Computer Engineering (Savitribai Phule Pune University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Nayna Sawant ()
, lOMoARcPSD|38490560
DAA@Unit-1[INTRODUCTION]
DAA 1ST UNIT DETAILS
UNIT I :
Introduction: Algorithm, Pseudo code for expressing algorithms, Performance Analysis-Space complexity,
Time complexity, Asymptotic Notation- Big oh notation, Omega notation, Theta notation and Little oh
notation ,Probabilistic analysis, Amortized analysis
set III B.Tech. II Semester Regular Examinations, April/May -2013
1 a Define an algorithm. What are the different criteria that satisfy the algorithm?
b Explain how algorithms performance is analysed? Describe Asymptotic notation?
2 a What are the different techniques to represent an algorithm. Explain.
b Give an algorithm to solve the towers of Hanoi problem.
3 a Write an algorithm to find the sum of individual digits of a given number.
b Explain the different looping statements used in pseudo code conventions.
4 a What is meant by recursion. Explain with example, the direct and indirect recursive
algorithms.
b List the advantages of pseudo code convention over flow charts.
set III B.Tech. II Semester Supplementary Examinations, January -2014
1 a Define the terms “Time complexity” and “Space complexity” of algorithms.
Give a notation for expressing such a complexity and explain the features of such a
notation.
b Explain in detail about Recursive algorithms with neat examples.
2 a Write an algorithm to find the sum of first n integers and Derive its time
complexity.
b Explain in detail about Amortized and Probabilistic analysis.
3 a Define Omega notation. Explain the terms involved in it. Give an Example.
b Explain the usefulness of the following functional operations on sets.
(i) MIN (ii) DELETE (iii) FIND (iv) UNION (v) INSERT
4 a Define Recursive algorithm. Explain in detail about Towers of Hanoi Algorithm with
example.
b Show that 9n3 + 12n4 + 100n22n = O(100n22n)
set III B.Tech. II Semester Regular/Supplementary Examinations, May/June -2014
1 a Explain in brief about Asymptotic Notations with examples
2 a Explain about Amortized analysis
b 3 2 3 n n
Prove3n + 2n = O(n) ; 3 !=O(2 )
3 a Define time and space complexity. Describe different notations used to represent these
complexities.
b Describe about Order of Growth with time function.
4 a How the performance can be analyzed ? Explain with the example.
b What is Randomizer? Give Cons and Pros
bphanikrishna.wordpress.com Page 1 of 36
Downloaded by Nayna Sawant ()
, lOMoARcPSD|38490560
DAA@Unit-1[INTRODUCTION]
set
1
2
3
4
bphanikrishna.wordpress.com Page 2 of 36
Downloaded by Nayna Sawant ()
, lOMoARcPSD|38490560
DAA@Unit-1[INTRODUCTION]
bphanikrishna.wordpress.com Page 3 of 36
Downloaded by Nayna Sawant ()
Daa unit 1 notes
Computer Engineering (Savitribai Phule Pune University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Nayna Sawant ()
, lOMoARcPSD|38490560
DAA@Unit-1[INTRODUCTION]
DAA 1ST UNIT DETAILS
UNIT I :
Introduction: Algorithm, Pseudo code for expressing algorithms, Performance Analysis-Space complexity,
Time complexity, Asymptotic Notation- Big oh notation, Omega notation, Theta notation and Little oh
notation ,Probabilistic analysis, Amortized analysis
set III B.Tech. II Semester Regular Examinations, April/May -2013
1 a Define an algorithm. What are the different criteria that satisfy the algorithm?
b Explain how algorithms performance is analysed? Describe Asymptotic notation?
2 a What are the different techniques to represent an algorithm. Explain.
b Give an algorithm to solve the towers of Hanoi problem.
3 a Write an algorithm to find the sum of individual digits of a given number.
b Explain the different looping statements used in pseudo code conventions.
4 a What is meant by recursion. Explain with example, the direct and indirect recursive
algorithms.
b List the advantages of pseudo code convention over flow charts.
set III B.Tech. II Semester Supplementary Examinations, January -2014
1 a Define the terms “Time complexity” and “Space complexity” of algorithms.
Give a notation for expressing such a complexity and explain the features of such a
notation.
b Explain in detail about Recursive algorithms with neat examples.
2 a Write an algorithm to find the sum of first n integers and Derive its time
complexity.
b Explain in detail about Amortized and Probabilistic analysis.
3 a Define Omega notation. Explain the terms involved in it. Give an Example.
b Explain the usefulness of the following functional operations on sets.
(i) MIN (ii) DELETE (iii) FIND (iv) UNION (v) INSERT
4 a Define Recursive algorithm. Explain in detail about Towers of Hanoi Algorithm with
example.
b Show that 9n3 + 12n4 + 100n22n = O(100n22n)
set III B.Tech. II Semester Regular/Supplementary Examinations, May/June -2014
1 a Explain in brief about Asymptotic Notations with examples
2 a Explain about Amortized analysis
b 3 2 3 n n
Prove3n + 2n = O(n) ; 3 !=O(2 )
3 a Define time and space complexity. Describe different notations used to represent these
complexities.
b Describe about Order of Growth with time function.
4 a How the performance can be analyzed ? Explain with the example.
b What is Randomizer? Give Cons and Pros
bphanikrishna.wordpress.com Page 1 of 36
Downloaded by Nayna Sawant ()
, lOMoARcPSD|38490560
DAA@Unit-1[INTRODUCTION]
set
1
2
3
4
bphanikrishna.wordpress.com Page 2 of 36
Downloaded by Nayna Sawant ()
, lOMoARcPSD|38490560
DAA@Unit-1[INTRODUCTION]
bphanikrishna.wordpress.com Page 3 of 36
Downloaded by Nayna Sawant ()
