Scribd
Upload
21 views

Daa Assignment1

This document outlines an assignment on designing and analyzing algorithms. It includes: 1. Defining algorithms and the criteria they must satisfy, such as being well-defined and having steps that are effective and efficient. 2. Explaining algorithm specification using pseudocode conventions and the algorithm design and analysis process. 3. Analyzing the time complexities of sequential search in the best, worst, and average cases and exploring space vs time complexity through examples. 4. Covering asymptotic notations like Big O, Big Ω, and Big θ and using them to analyze the time complexities of various algorithms.

Uploaded by

D.Sameer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
21 views

Daa Assignment1

This document outlines an assignment on designing and analyzing algorithms. It includes: 1. Defining algorithms and the criteria they must satisfy, such as being well-defined and having steps that are effective and efficient. 2. Explaining algorithm specification using pseudocode conventions and the algorithm design and analysis process. 3. Analyzing the time complexities of sequential search in the best, worst, and average cases and exploring space vs time complexity through examples. 4. Covering asymptotic notations like Big O, Big Ω, and Big θ and using them to analyze the time complexities of various algorithms.

Uploaded by

D.Sameer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

ASSIGNMENT1 : DESIGN AND ANALYSIS OF ALGORITHMS (21 CS 42)

Staff Name : Dr Sai Madhavi D Submission Date : 28-6-23


Introduction
1. Define algorithm. Discuss the criteria’s that an algorithm must satisfy with an example
2. explain Algorithm specification : Pseudocode conventions.
3. Explain Algorithm design and analysis process with figure
4. Define best case, worst case and average case efficiency. Write the algorithm and give
these efficiencies for sequential search
5. Explain space complexity and time complexity with an example
6. Consider the following algorithm.

i) What does the algorithm compute?


ii) What is basic operation?
iii) What is the efficiency of this algorithm?

Asymptotic Notations
7. Explain asymptotic notations Big O, Big Ω and Big θ that are used to compare the order of
growth of an algorithm with example
8.
Prove the following statements. d. 100n + 5 =`O(n2)
2 2 2 3
a. n + 5n + 7 = Θ(n ) e. n + n = O(n )
2 2 2
b. 2 ½ n(n-1) 2= Θ(n ) f.3 5n2 + 3n +2 20 = O(n )
c. ½ n +3n= Θ(n ) g. n + 4n = Ω(n )
Mathematical Analysis of Non-Recursive Algorithms
9. Explain general plan of mathematical analysis of non-recursive
algorithms with example.
10. Write the algorithm to find maximum element in the given array and explain the
mathematical analysis of this non-recursive algorithm
11. Write the algorithm to check whether all the elements in the given array are distinct and
explain the mathematical analysis of this non- recursive algorithm. Derive its worst-case
time complexity
12. Write the algorithm to perform matrix multiplication and explain the mathematical
analysis of this non-recursive algorithm
Mathematical Analysis of Recursive Algorithms
13. Explain general plan of mathematical analysis of recursive algorithms
with example.
14. Illustrate mathematical analysis of recursive algorithm for Towers of
Hanoi OR Give the recursive algorithm to solve Tower of Hanoi problem. Show that the efficiency
of this algorithm is exponential
15. Illustrate mathematical analysis of recursive algorithm to find the
factorial of a given number
16. State the recursive algorithm to count the bits of a decimal number in its binary
representation. Give its mathematical analysis

You might also like