Design and
Analysis of
Algorithms
By
Baidyanath Sou
Dept. of Computer science.
J.K. College
CHAPTER 1:
INTRODUCTION
• What is an Algorithm
• Steps in Designing and
Implementing an Algorithm
• Important Problem Types
• Fundamental Data Structures
2
ALGORITHM
• A sequence of unambiguous
instructions for solving a
problem, i.e. for obtaining
the required output for any
legitimate input in
a finite amount of time
3
Important points
• Non-ambiguity
• Range of inputs
• The same algorithm can be
represented in different ways
• Several algorithms for solving the
same problem
4
gcd(m,n)
while n ≠0 do 1. t ← min (m ,n)
r ← m mod n
m←n 2. if m % t = 0 goto 3,
n ←r
return m else goto
4
3. if n % t = 0 return
t,
else goto
4
5
Understand the problem
Decide on computational means
Exact vs approximate solution
Data structures
Algorithm design technique
Design an algorithm
Prove correctness
Analyze the algorithm
Code the algorithm
6
What does it mean to
understand the problem?
• What are the problem objects?
• What are the operations applied to the
objects?
Deciding on computational
means
• How the objects would be represented?
• How the operations would be
implemented?
7
Design an algorithm
• Build a computational model of
the solving process
Prove correctness
• Correct output for every
legitimate input in finite time
• Based on correct math formula
• By induction 8
Analyze the algorithm
Efficiency: time and space
Simplicity
Generality: range of inputs, special
cases
Optimality:
no other algorithm can do better
Coding
How the objects and operations in the
algorithm are represented in the 9
Important problem
types
• Sorting
• Searching
• String processing
• Graph problems
• Combinatorial problems
• Geometric problems
• Numerical problems
10
Fundamental data structures
Linear data structures
• Array
• Linked list
• Stack
• Queue
Operations: search, delete, insert
Implementation: static, dynamic
11
Fundamental data structures
Non-linear data structures
• Graphs
• Trees : connected graph without cycles
• Rooted trees
• Ordered trees
• Binary trees
Graph representation: adjacency lists,
adjacency matrix
Tree representation: as graphs; binary
nodes 12
Fundamental data structures
Sets, Bags, Dictionaries
• Set: unordered collection of distinct elements
Operations: membership, union,
intersection
Representation: bit string; linear structure
• Bag: unordered collection,
elements may be repeated
• Dictionary: a bag with operations search,
add, delete
13
Conclusion
• Algorithm classification
• By types of problems
• By design technique
• Design techniques
• a general approach to solving
problems
14
