DAA NOTES

Design& Analysis Of Algorithm

UNIT-I 1. Define Algorithm.
An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time.

 2. Write about Notion of Algorithm.
· Problem
· Algorithm
· Input Computer Output

 3. Write a short note on Algorithm Design and Analysis of Process.
Understand the problem
Decide on
Computational Device
Exact Vs Approximate Algorithms
Data Structures
Algorithm Design Techniques
Design an algorithms
Prove Correctness
Analyze the Algorithm
Code the Algorithm

 4. What are the 2 kinds of Algorithm Efficiency
Time Efficiency-How fast your algorithm runs?
Spce Efficiency-How much extra memory your algorithm needs?

 5. How can you specify Algorithms?
Algorithms can be specified in a natural language or pseudo code.

 6. What is Pseudo Code?
Pseudo Code is a mixture of Natural Language and Programming Language Constructs such as functions, loops, decision making statements..etc

  7. What are the Important Problem Types?
Sorting
Searching
String Processing
Graph Problem
Cominatorial Problem
Geometric Problem
Numerical Problem

  8. How can you Classify Algorithms ?
Among several ways to classify algorithms, the 2 principal alternatives are · To group algorithms according to types of problem they solve
· To group algorithms according to underlying design techniques they are based upon

  9. Write the Euclid Algorithm
Algorithm Euclid(m,n)
Step 1: While n not equal do
Step 2: r = m mod r
Step 3: m=n
Step 4: n=r
Step 5: return n

  10. What is Sorting Problem?
Sorting algorithm is rearrange the items of a given list in descending/ascending order. Sorting algorithms classified into
Stable Sorting Algorithm
Non-Stable Algorithm

  11.What is Searching Problem?
Finding a given value, called search key in a given set. Searching Algorithms needs more memory space and sorted array.

  12. What is Graph Problem?
Graph is a collection of edges and vertices. G=(V,E). For eg. Traversal Algorithms, Shortest Path Algorithm, Graph Coloring Problem