DESIGN AND ANALYSIS OF

ALGORITHMS

INTRODUCTION

Dr. V.Sireesha
Dept. of CSE
 Why to Study DAA course?
 Programming is becoming a highly in-demand
skill for software developers with advancement
and innovation in technology.

 Design and Analysis of Algorithms is the

core course in computer science and in depth
understanding of this course is very much
important especially when you are into
development/programming domain where you
build efficient software systems and applications.
 Why to Study DAA course?
 This core course covers the good principles of algorithm design, analysis of
algorithm and fundamental data structures.

 This course helps to learn how to analyze algorithms and estimate their
worst case and average case behavior.

 It determines how to apply their theoretical knowledge in practice.

 The different algorithm design techniques introduced in this course helps

in reducing the time and space complexities for performing a given
operation.

 It includes all topics of algorithm, asymptotic analysis, algorithm control

structure, recurrence, master method, recursion tree method, divide and
conquer, binary search, merge sort, Greedy Algorithm, Dynamic
Programming, lower bound theory, Complexity Theory.
What is DAA?

 Design and Analysis of Algorithm deals

with how to design various algorithms
and how to analyze them. After designing
and analyzing, we need to choose the best
algorithm that takes the least time and
the least memory and then implement it
as a program.
 What is the need for Algorithms?
 To understand the basic idea of the problem.
 To find an approach to solve the problem.
 To improve the efficiency of existing techniques.
 To understand the basic principles of designing the
algorithms.
 To compare the performance of the algorithm with
respect to other techniques.
 It is the best method of description without describing the
implementation detail.
 The Algorithm gives a clear description of requirements
and goal of the problem to the designer.
 A good design can produce a good solution.
 What is the need for Algorithms?

 To understand the flow of the problem.

 To measure the behavior (or performance) of the
methods in all cases (best cases, worst cases, average
cases)
 With the help of an algorithm, we can also identify the
resources (memory, input-output) cycles required by the
algorithm.
 To understand the principle of designing.
 We can measure and analyze the complexity (time and
space) of the problems concerning input size without
implementing and running it; it will reduce the cost of
design.
 Analysis of algorithm

 The analysis is a process of estimating the

efficiency of an algorithm. There are two
fundamental parameters based on which we
can analysis the algorithm:
 Space Complexity: The space complexity
can be understood as the amount of space
required by an algorithm to run to
completion.
 Time Complexity: Time complexity is a
function of input size n that refers to the
amount of time needed by an algorithm to
run to completion.
 Analysis of algorithm
Example:
 Suppose there is a problem to solve in Computer Science, and in general, we solve a
program by writing a program. If you want to write a program in
some programming language like C, then before writing a program, it is necessary to
write a blueprint in an informal language.
 Or in other words, you should describe what you want to include in your code in
an English-like language for it to be more readable and understandable before
implementing it, which is nothing but the concept of Algorithm.
 In general, if there is a problem P1, then it may have many solutions, such that each
of these solutions is regarded as an algorithm. So, there may be many algorithms
such as A1,A2,A3, …, An.
 Before you implement any algorithm as a program, it is better to find out which
among these algorithms are good in terms of time and memory.
 It would be best to analyze every algorithm in terms of Time that relates to which
one could execute faster and Memory corresponding to which one will take less
memory.
 So, the Design and Analysis of Algorithm talks about how to design various
algorithms and how to analyze them. After designing and analyzing, choose the best
algorithm that takes the least time and the least memory and then implement it as
a program in C.
 Analysis of algorithm
 In this course, we will be focusing more on time rather
than space because time is instead a more limiting
parameter in terms of the hardware. It is not easy to
take a computer and change its speed. So, if we are
running an algorithm on a particular platform, we are
more or less stuck with the performance that platform
can give us in terms of speed.
 However, on the other hand, memory is relatively more
flexible. We can increase the memory as when required
by simply adding a memory card. So, we will focus on
time than that of the space.
 The running time is measured in terms of a particular
piece of hardware, not a robust measure. When we run
the same algorithm on a different computer or use
different programming languages, we will encounter that
the same algorithm takes a different time.
 Analysis of algorithm
Generally, we make three types of analysis, which is as follows:
 Worst-case time complexity: For 'n' input size, the worst-case
time complexity can be defined as the maximum amount of time
needed by an algorithm to complete its execution. Thus, it is
nothing but a function defined by the maximum number of steps
performed on an instance having an input size of n.
 Average case time complexity: For 'n' input size, the average-
case time complexity can be defined as the average amount of time
needed by an algorithm to complete its execution. Thus, it is
nothing but a function defined by the average number of steps
performed on an instance having an input size of n.
 Best case time complexity: For 'n' input size, the best-case
time complexity can be defined as the minimum amount of time
needed by an algorithm to complete its execution. Thus, it is
nothing but a function defined by the minimum number of steps
performed on an instance having an input size of n.
 Algorithm Design Techniques
Divide and Conquer Approach:
 It is a top-down approach. The algorithms which follow the divide &
conquer techniques involve three steps:
 Divide the original problem into a set of subproblems.
 Solve every subproblem individually, recursively.
 Combine the solution of the subproblems (top level) into a
solution of the whole original problem.
Greedy Technique: Greedy method is used to solve the
optimization problem. An optimization problem is one in which we
are given a set of input values, which are required either to be
maximized or minimized (known as objective), i.e. some constraints
or conditions.
 Greedy Algorithm always makes the choice (greedy criteria) looks
best at the moment, to optimize a given objective.
 The greedy algorithm doesn't always guarantee the optimal
solution however it generally produces a solution that is very close
in value to the optimal.
 Algorithm Design Techniques
 Dynamic Programming: Dynamic Programming is a bottom-up
approach we solve all possible small problems and then combine them
to obtain solutions for bigger problems.
 This is particularly helpful when the number of copying sub problems is
exponentially large. Dynamic Programming is frequently related
to Optimization Problems.
 Backtracking Algorithm: Backtracking Algorithm tries each
possibility until they find the right one. It is a depth-first search of the
set of possible solution. During the search, if an alternative doesn't
work, then backtrack to the choice point, the place which presented
different alternatives, and tries the next alternative.
 Branch and Bound: In Branch & Bound algorithm a given
subproblem, which cannot be bounded, has to be divided into at least
two new restricted subproblems. Branch and Bound algorithms can be
slow, however in the worst case they require effort that grows
exponentially with problem size, but in some cases we are lucky, and
the method coverage with much less effort.
 Course Objectives
1.Analyze the asymptotic performance of
algorithms

2.Apply algorithm design strategies to

solve science and engineering problems.
 SYLLABUS
UNIT – I:
Introduction: Introduction to Algorithm, algorithm
specification. Performance analysis: space complexity, time
complexity.Asymptotic notations, amortized analysis

UNIT – II:
Divide and Conquer: General method, binary search, finding
maximum and minimum, Merge sort, quick sort, performance
measurement, Masters theorem. The Greedy Method: The
general method, Knapsack problem, Job sequencing with
deadlines, minimum cost spanning trees, optimal Storage on
Tapes, Optimal Merge Patterns, single Source Shortest Paths,
network flows.
 SYLLABUS (CONTD)
UNIT – III:
Dynamic Programming: the general method, matrixchain multiplication
problem, multistage graph, All Pairs Shortest Paths, Optimal Binary Search
Trees (OBST), 0/1 Knapsack, Reliability Design, Traveling Salesman Problem,
Bi-connected Components and DFS, Longest Common Subsequence (LCS)
problem.
UNIT – IV:
Backtracking: General method, the 8-Queens Problem, Graph Coloring,
Hamiltonian Cycles, Knapsack Problem. Branch and Bound: The method,
0/1 Knapsack problem,Traveling Salesperson problem.
UNIT – V:
Tractable and intractable problems, Non-Deterministic search and sorting,
classes P, NP, NP-Complete, NP-Hard, Satisifiability (SAT), Cook’s theorem,
reductions, procedure for NP-Complete, clique decision problem, graph
coloring, node cover, Hamiltonian cycle,TSP.
 Learning Resources
1. Ellis Horowitz, Sartaj Sahani, Sanguthevar Rajasekaran,“ Fundamentals
of computer Algorithms”, Second edition (2008),Universities Press.
2. Thomas H. Cormen, Leiserson C.E, Rivest.R.L , Stein.C, Introduction
to Algorithm, 2nd edition (2001), MIT press, USA.
3. Michael T. Goodrich, Roberto Tamassia, Algorithm Design,
foundations, analysis, and internet examples, WIELEY student edition
(2006).
4. Aho, Hopcroft, Ulman, The Design and Analysis of Computer
Algorithms, (2000), Pearson Education.
5. Steven S.Skiena,The Algorithm Design Manual, Springer (1997)..
6. Algorithm Design, 1st Edition, Jon Kleinberg and Éva Tardos, Pearson.
7. https://ocw.mit.edu/courses/electrical-engineering-and-computer-
science/6-046j-design-and-analysis-of-algorithms-spring-
2015/index.htm.
8. http://openclassroom.stanford.edu/MainFolder/CoursePage.php?cour
se=IntroT oAlgorithms 9. http://nptel.ac.in/courses/106101060/
 Course Outcomes
1. Compare asymptotic behavior of functions
derived from algorithms.
2. Apply divide & conquer and greedy
algorithmic design paradigms to solve
problems.
3. Design algorithms using Dynamic
Programming strategy.
4. Design algorithms for problems using
backtracking and branch & bound
algorithm design techniques
5. Identify the complexity class of a given
problem
 Scheme of Evaluation
L:T:P(Hrs./week): 3:0:0 SEE Marks : 60 Course Code: U19PC430CS

Credits : 3 CIE Marks : 40 Duration of SEE: 3 Hours

1 No. of Internal : Max. Marks for each Internal :

2 30
Tests Test

2 No. of Assignments : Max. Marks for each :

3 5
Assignment

3 No. of Quizzes : Max. Marks for each Quiz :

3 5
Test

Duration of Internal Tests : 1 Hour 30 Minutes

Thank You