Algorithm Analysis and Design Lecture

Material-----All Chapters

Chapter One

Introduction to Algorithm

1 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

What is Algorithm ?
• Definition of Algorithm:
• An algorithm is a sequence of explicit instruction for
 Solving a problem,
 Obtaining required output
 Any legitimate input in a finite amount of time.
• It is commonly used for
data processing,
 calculation and
other related computer and mathematical operations.
• An algorithm is also used to manipulate data in various ways, such as
inserting a new data item, searching for a particular item or sorting an
item.

2 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Properties of Algorithm:

 An algorithm must possess the following properties for any problem

 Finiteness: The algorithm must always terminate after a finite number
of steps.
 Definiteness: Each step must be precisely defined
 Input: An algorithm has zero or more inputs, from a set of objects.
 Output: An algorithm has one or more outputs, which have a
specified relation to the inputs.
 Effectiveness: All operations to be performed must be sufficiently
basic that they can be done exactly and in finite length.

3 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Why we study algorithm ?

 We need to answer “what is the main task of computer

scientists “?
 The study of algorithms is the foundation (cornerstone)
of computer science.
 It can be recognized as the core of computer science.
 Computer programs would not exist without
algorithms.


4 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

cont.
 Computers becoming an essential part of our
professional & personal life‘s, studying algorithms
becomes a necessity, more so for computer science and
engineers.

 Another reason for studying algorithms is that if we know

a standard set of important algorithms, they further our
analytical skills & help us in developing new algorithms for
required applications.

5 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

6 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Fundamentals of Algorithmic Problem Solving
1. Understanding the problem :
 An input to an algorithm specifies an instance of the problem
the algorithm solves.
 It’s also important to specify exactly the range of instances
the algorithm needs to handle.
 Before this we have to clearly understand the problem
and clarify the doubts after leading the problems
description.
 Correct algorithm should work for all possible inputs.

7 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont.…
2. Ascertaining the capabilities of a computational Device:
 Assessing the device you have supports Sequential or parallel
processing because we will select sequential algorithms or parallel
algorithms
3. Choosing between exact and approximate problem solving:
Choosing either we are solving the problem exactly or solving it
approximately.
 1st there are certain problems like extracting square roots, solving
non-linear equations which cannot be solved exactly. (e.g. 𝜋)
 2nd, if the problem is complicated it slows the operations. E.g. traveling
salesman problem.
 3rd , this algorithm can be a part of a more sophisticated
algorithm that solves a problem exactly.
8 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Cont..
 Deciding on data structures
 Algorithm Design Techniques:
 Methods of specifying an Algorithm:
 A Pseudocode , which is a mixture of a natural language and
programming language like constructs.

9 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
4. Proving an Algorithm’s correctness:
A technique used for proving correctness s by mathematical induction
because an algorithm’s iterations provide a natural sequence of steps needed
for such proofs.
5. Analyzing an algorithm:
 There are two kinds of algorithm efficiency measurements: time and
space efficiency.
 Time efficiency indicates how fast the algorithm runs; space efficiency
indicates how much extra memory the algorithm needs.

10 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
6. Coding an algorithm:
 Programming the algorithm by using some rogramming
language.
 Formal verification is done for small programs.
 Validity is done thru testing and debugging.

11 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 Fundamentals of Analysis of Algorithm
 Algorithm is step by step procedure is designed to perform an
operation with finite number of steps to perform for particular
operation.
 It is a formula or set of steps for solving particular problems.
 To be an algorithm, as set of rules must be implemented and put
clear stopping point.

12 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 Algorithm Analysis
 Analysis of algorithms means to investigate an algorithm’s
efficiency with respect to resources:
 Running Time ( time efficiency ) and
 Memory Space ( space efficiency )
 Time being more critical than space, we concentrate on Time
efficiency of algorithms.

13 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
 We use a hypothetical model with following assumptions
• Total time taken by the algorithm is given as a function on its input
size
• Logical units are identified as one step
• Every step require 1 unit of time
• Total time taken = Total Num. of steps executed

14 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
 Running time Depends on
 Single Vs Multi processor
 Read/write Speed to/from memory
 32 bit Vs 64 bit
 Input

15 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Example

16 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Memory space (space efficiency)
 Concerned with the use of main memory (often RAM) while the
algorithm is being carried out.
 There are up to four aspects of memory usage to consider:
 The amount of memory needed.
1. To hold the code for the algorithm
2. For the input data.
3. For any output data.
4. As working space during the calculation.

17 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Units for Measuring Run Time
 Wecan simply use some standard unit of time
measurement-As
 Second,
 Millisecond,
 Microsecond
 Nanosecond
 and so on-
 to measure the running time of a program implementing the
algorithm.
18 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Cont.
 There are obvious drawbacks to such an approach. They are
1. Dependence on the speed of a particular computer
2. Dependence on the quality of a program implementing the
algorithm
3. The compiler used in generating the machine code
4. The difficulty of clocking the actual running time of the
program.
 So to measure algorithm efficiency, we should have a metric that
does not depend on these inessential /extraneous factors.
19 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Cont..
 1st
approach is to count the number of times each of the
algorithm's operations is executed. This approach is both
difficult and unnecessary.
 The main objective is to identify the most important
operation of the algorithm, called the basic operation, the
operation contributing the most to the total running time,
and compute the number of times the basic operation is
executed.
 As a rule, it is not difficult to identify the basic operation of
an algorithm.
20 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Worst Case, Best Case and Average Case Efficiencies
It is reasonable to measure an algorithm's efficiency as a
function of a parameter indicating the size of the algorithm's
input.
 But there are many algorithms for which running time depend
not only on an input size but also on the specifics of a
particular input.

21 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
Example, Sequential search
 This is a straightforward algorithm that searches for a given
item (some search key K) in a list of n elements.
 by checking successive elements of the list until either a match
with the search key is found or the list is exhausted.
 Here is the algorithm's pseudo code, in which, for simplicity, a
list is implemented as an

22 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Algorithm - Sequential Search (A [0...n -1], K)
 //Searches for a given value in a given array by sequential search //
 Input: An array A[0..n -1] and a search key K
 //Output: Returns the index of the first element of A that matches K//
 or - 1 if there are no matching elements
 for (i = 0;i<n;i++)
 {
 if(a[i] == k)
 {
 return (k)
 }
 else
 return(i)
 }
23 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Worst case efficiency
 For which the algorithm runs the longest among all possible
inputs of that size.
 In the worst case, when there are no matching elements or
the first matching element happens to be the last one on
the list,
 The algorithm makes the largest number of key comparisons
among all possible inputs of size n:

 Cworst (n) = n.
24 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
 Cont..

 Given input array a[20];

 Searching for k=26 or 100
 Worst case= n
 We have to compare 20 times to get match or 1

12 2 4 56 34 56 7 8 10 44 5 1 00 14 77 88 55 96 45 26

25 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
 The worst-case analysis provides very important
information about an algorithm's efficiency.
 In other words, it guarantees that for any instance of size
n, the running time will not exceed C worst (n) its running
time on the worst-case inputs.

26 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Best case Efficiency
 In Best case scenario with an input (or inputs) of size n for which
the algorithm runs the fastest among all possible inputs of
that size.
 We can analyze the best case efficiency
 First, determine the kind of inputs for which the count C (n) will be
the smallest among all possible inputs of size n.
 (Note that the best case does not mean the smallest input; it
means the input of size n for which the algorithm runs the
fastest.)
27 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Cont..
 Then determine the value of C (n) on these most
convenient inputs.
 Example- for sequential search,
 best-case inputs will be lists of size n with their first
elements equal to a search key;
 accordingly, Cbest(n) = 1.

28 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 Cont..
 Given input array a[20];
 Searching for k=12
 Worst case= n=20
 We have to compare only once to get match

12 2 4 56 34 56 7 8 10 44 5 1 00 14 77 88 55 96 45 26

29 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Average case efficiency
 It yields the information about an algorithm and an algorithms
behavior on a typical and random input.
 To analyze the algorithm's average-case efficiency, we must
make some assumptions about possible inputs of size n.
 The investigation of the average case efficiency is considerably
more difficult than investigation of the worst case and best case
efficiency.

30 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont.
 It involves dividing all instances of size n .into several classes so
that for each instance of the class the number of times the
algorithm's basic operation is executed is the same.

 Then a probability distribution of inputs needs to be obtained

or assumed so that the expected value of the basic operation's
count can then be derived.

31 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
all posible case time
 Average case =
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐𝑎𝑠𝑒𝑠
 Let us assume Key k is Likely to be a1 a2 a3 ….. an
1
 P(k=ai)= since all the elements have equal probability
𝑛
𝑛 1
Ava= 𝑖=1 𝑃𝑖𝑎𝑖 and Pi= so
𝑛
1 𝑛 𝑛 𝑛+1
= ∗ 𝑖=1 𝑎𝑖 ane 𝑖=1 𝑎𝑖 =n( )
𝑛 2
1 𝑛+1
= *n( )
𝑛 2
𝒏+𝟏 𝑛
= ∈ 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑙𝑎𝑟𝑔𝑒 𝑛
𝟐 2
32 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Asymptotic Notations
 Asymptotic notation is a way of comparing functions that
ignores
 constant factors
 small input sizes.
 Three notations used to compare orders of growth of an
algorithm ‘s basic operation count are
1. Big Oh- O notation
2. Big Omega- Ω notation
3. Big Theta- Θ notation

33 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Big Oh- O notation (Asymptotic Upper Bound)

 A function t(n) is said to be in

O(g(n)), denoted t(n)∈ O(g(n)),
if t(n) is bounded above by
some constant multiple of
g(n) for all large n, i.e., if there
exist some positive constant c
and some nonnegative integer n0
such that (n) ≤ cg(n) for all n
≥ n0

34 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Big Omega- Ω notation
 A function t (n) is said to be in
Ω (g(n)), denoted t(n)∈ Ω (g
(n)), if t (n) is bounded below
by some constant multiple of g
(n) for all large n, i.e., if there
exist some positive constant c
and some nonnegative integer n0
such that t(n) ≥ cg(n) for all n
≥ n0

35 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Big Theta- Θ notation
 A function t (n) is said to be in Θ
(g (n)), denoted t(n)∈ Θ (g (n)),
if t (n) is bounded both above and
below by some constant multiple
of g (n) for all large n,
 i.e., if there exist some positive
constant c1 and c2 and some
nonnegative integer n0 such that
 c2 g (n) ≤ t (n) ≤ c1 g (n) for
all n ≥ n0

36 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Common Asymptotic functions

Function Name
1 Constant
log n Logarithmic
n linear
n log n n log n
n2 Quadratic
n3 Cubic
2n Exponential
37 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
 Linear/Sequential Techniques

38 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Contents..
 Sorting
 Bubble Sort
 Insertion Sort
 Selection Sort
 Searching
 Linear Searching

39 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

2. Linear/Sequential Techniques

1. Linear/Sequential Techniques is examining each element of

the list until the element in the list.
Is Sorted in sorting Algorithms
Found in Searching Algorithms

40 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Sorting
 Arranging elements in a list or collection in ascending or descending order of
some property.
Example 2 6 5 3 1 4
1 2 3 4 5 6 in ascending order value
6 5 4 3 2 1 in descending order value
Sorting Examples in real life
In hotel reservation system
Peoples may need to sort hotels by
price
Star
Number of available beds

41 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

2.1 Sorting Algorithms
1. Bubble sort
Bubble sort is a simple sorting algorithm.
This sorting algorithm is comparison-based algorithm in which
each pair of adjacent elements is compared and the elements
are swapped if they are not in order.
Bubble sort takes Ο(n2) time so we're keeping it short and
precise.

42 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
 We take an unsorted array for our example.

43 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Bubble sort Algorithm
Bubble(List,N)
Where list is an array of N elements
Step 1 : Declare array for i = 0,1,2….N-1
Step 2: Declare J = i+1 to N-1
Step 3:
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
Step 4 : end of the step 2 for loop
Step 5 : end of the step 1 for loop
Step 6: print the sorted Array
44 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Pseudo code
begin Bubble Sort(A,n) T(n)=(n-1)*(n-1)*c
for k<-1 to n-1
=cn2-2cn +1
for i = 0 to n-1
if list[i] > list[j] =O(n2)
temp = a[i]
a[i] = a[j]
a[j] = temp;
end if
end for
return list

45 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

2. Insertion sort

46 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..

47 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Pseudo code
I value hole
1 2 1
1 2 0
2 4 2
2 4 1
3 1 3
3 1 2
3 1 1
3 1 0
4 5 4
4 5 3
5 3 5 Cont’
48 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
2.2 Searching
A search algorithm is the step-by-step procedure used to
locate specific data among a collection of data.
It is considered a fundamental procedure in computing.
In computer science, searching for data, the difference
between a fast application and a slower one often lies in the
use of the proper search algorithm.
There are two types of searching algorithms are focusing to
study that linear search and binary search.

49 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Linear search or Sequential Search
Linear search is a very simple search algorithm.
In this type of search, a sequential search is made over all items
one by one.
Every item is checked and if a match is found then that
particular item is returned, otherwise the search continues
till the end of the data collection.

50 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Linear search

 Example Searching for 33 from the given array

51 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
Linear Search (Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then goes to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

52 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 Chapter three
Divide and Conquer Technique

53 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Divide and Conquer Technique
Many algorithms are recursive in nature to solve a given
problem recursively dealing with sub-problems.
In divide and conquer approach, a problem is divided into
smaller problems, then the smaller problems are solved
independently,
Finally the solutions of smaller problems are combined into a
solution for the large problem.

54 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
 Generally, divide-and-conquer algorithms have three parts
Divide the problem into a number of sub-problems that are
smaller instances of the same problem.
Conquer the sub-problems by solving them recursively. If
they are small enough, solve the sub-problems as base cases.
Combine the solutions to the sub-problems into the
solution for the original problem.

55 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Pros and cons of Divide and Conquer Approach
Supports parallelism as sub-problems are independent.
Hence, an algorithm, which is designed using this technique, can
run on the multiprocessor system or in different machines
simultaneously.
In this approach, most of the algorithms are designed using
recursion, hence memory management is very high.
For recursive function stack is used, where function state needs
to be stored.

56 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Application of Divide and Conquer Approach
 Following are some problems, which are solved using divide and
conquer approach.
Finding the maximum and minimum of a sequence of numbers
Strassen’s matrix multiplication
Merge sort
Binary search
Quick search

57 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

1. Merge Sort
Merge Sort is a Divide and Conquer algorithm.
It divides input array in two halves, calls itself for the
two halves and then merges the two sorted halves.
The merge () function is used for merging two
halves.

58 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

59 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Merge algorithm
• # get the Array • # Divide the Array • # Merging Array
• m = n/2 • if(L[i] <= R[j]
• cin>> n;
• L[i = 1 to m] and • A[i] = L[i]
• for(i=1;i<n;i++) R[j=m+1 … n] • i= i + 1
• { • for(i=1 to m) • else
• cin>>A[i]; • L[i] = A[i] • A[i] = R[j]
• for(j=m+1 to n]
• } • j= j + 1
• R[j] = A[j]

60 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

2. Binary search
Binary search is a fast search algorithm works on the principle of divide
and conquer.
Binary search looks for a particular item by comparing the middle most item
of the collection.
If a match occurs, then the index of item is returned. If the middle item is
greater than the item, then the item is searched in the sub-array to the left of
the middle item.
Otherwise, the item is searched for in the sub-array to the right of the middle
item.
This process continues on the sub-array as well until the size of the sub-array
reduces to zero.

61 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

How Binary Search Works?
For a binary search to work, it is mandatory for the target array
to be sorted.
The following is our sorted array and let us assume that we
need to search the location of value 31 using binary search.

62 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
First, we shall determine half of the array by using this formula

mid = low + high / 2

Here it is, 0 + (9 - 0) / 2 = 4 (integer value of 4.5). So, 4 is the
mid of the array.

63 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont.
Now we compare the value stored at location 4, with the value
being searched, i.e. 31.
We find that the value at location 4 is 27, which is not a match.
As the value is greater than 27 and we have a sorted array, so
we also know that the target value must be in the upper
portion of the array.

64 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
We change our low to mid + 1 and find the new mid value again.

mid =Low+ high / 2

Our new mid is 7 now. We compare the value stored at location

7 with our target value 31.

The value stored at location 7 is not a match, rather it is more than what we
are looking for. So, the value must be in the lower part from this location.

65 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find
that it is a match.


66 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
We compare the value stored at location 5 with our target
[Link] find that it is a match.

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the
count of comparisons to be made to very less numbers.

67 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Pseudocode :
• Procedure binary_search • if A[midPoint] = x
• A ← sorted array
• n ← size of array • EXIT: x found at location
• x ← value to be searched midPoint
•
• Set lowerBound = 1 •
• Set upperBound = n • if A[midPoint] < x
•
• while x not found • set lowerBound = midPoint + 1
• if upperBound < lowerBound • if A[midPoint] > x
• EXIT: x does not exists.
• set midPoint = lowerBound + ( upperBound - • set upperBound = midPoint - 1
lowerBound ) / 2 • end while
•
• end procedure
•

68 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

3. Quick Sort Algorithm
Quick sort is a divide and conquer algorithm.
Quick sort first divides a large array into two smaller sub-
arrays: the low elements and the high elements.
Quick sort can then recursively sort the sub-arrays.

69 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont.…
1. Pick an element, called a pivot, from the array.
2. Partitioning: reorder the array so that all elements with values less than
the pivot come before the pivot, while all elements with values greater
than the pivot come after it (equal values can go either way).
After this partitioning, the pivot is in its final position. This is called the
partition operation.
3. Recursively apply the above steps to the sub-array of elements with
smaller values and separately to the sub-array of elements with greater
values

70 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

71 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
 Chapter 4
Dynamic Programming

72 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Chapter 4
Dynamic Programming is also used in optimization problems.
Like divide-and-conquer method, Dynamic Programming solves problems
by combining the solutions of sub problems.
Moreover, Dynamic Programming algorithm solves each sub-problem just
once and then saves its answer in a table, thereby avoiding the work of
re-computing the answer every time.
Two main properties of a problem suggest that the given problem can be
solved using Dynamic Programming.
These properties are overlapping sub-problems and optimal
substructure.

73 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Dynamic Programming
 is a method for solving a complex problem by breaking it down into a
collection of simpler subproblems, solving each of those subproblems just
once, and storing their solutions using a memory-based data structure (array,
map, etc.).
 Each of the subproblem solutions is indexed in some way, typically based on
the values of its input parameters, so as to facilitate its lookup.
 So the next time the same subproblem occurs, instead of recomputing its
solution, one simply looks up the previously computed solution, thereby saving
computation time.
 This technique of storing solutions to subproblems instead of recomputing
them is called memorization.

74 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Overlapping Sub-Problems

 Similar to Divide-and-Conquer approach, Dynamic Programming also

combines solutions to sub-problems.
 It is mainly used where the solution of one sub-problem is needed
repeatedly.
 The computed solutions are stored in a table, so that these don’t have to
be re-computed.
 Hence, this technique is needed where overlapping sub-problem exists.
 For example, Binary Search does not have overlapping sub-problem.
Whereas recursive program of Fibonacci numbers have many
overlapping sub-problems.

75 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Steps of Dynamic Programming Approach

 Dynamic Programming algorithm is designed using the

following four steps −
Characterize the structure of an optimal solution.
Recursively define the value of an optimal solution.
Compute the value of an optimal solution, typically in a
bottom-up fashion.
Construct an optimal solution from the computed
information.

76 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Applications of Dynamic Programming Approach
Matrix Chain Multiplication
Longest Common Subsequence
Travelling Salesman Problem
Computing Binomial coefficient
Floyd–Warshall algorithm

77 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 DC Vs DP

78 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont..
The intuition behind dynamic programming is that
we trade space for time, i.e. to say that
instead of calculating all the states taking a lot of
time but no space, we take up space to store
the results of all the sub-problems to save time
later.

79 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Warshall’s algorithm
The Floyd–Warshall algorithm is an algorithm for finding
shortest paths in a weighted graph
Also known as All Pair Shortest Path Graph Algorithm
Computes the transitive closure of a relation in a graph vertex
Alternatively: all paths in a directed graph
Example of transitive closure:

80 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

81 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
82 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
 Example calculate the shortest path for all pairs

1 2 3 4
1 0 3 ∞ 7
A0
2 8 0 2 ∞
3 5 ∞ 0 1
4 2 ∞ ∞ 0

83 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 To find A1 take the 1st raw and column as it is from A0 and the diagonals will be 0

1 2 3 4
The calculate A1
1 0 3 ∞ 7 (Min(A0 [2,3] OR A0 [2,1] + A0 [1,3])
2 8 0 2 15
2 8+ ∞
3 5 8 0 1
4 2 5 0 0 Min(A0 [2,4] OR A0 [2,1] + A0 [1,4])
∞ 8+ 7=15
(Min(A0 [4,2] OR A0 [4,1] + A0 [1,2]) Min(A0 [3,2] OR A0 [3,1] + A0 [1,2])
∞ 2+3 =5 ∞ 5+ 3=8
• Min(A0 [4,3] OR A0 [4,1] + A0 [1,3])
0 2+ ∞ Min(A0 [3,4] OR A0 [3,1] + A0 [1,4])
1 5+ 7=12

84 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 To find A2 take the 2nd raw and column as it is from A1 and the diagonals will be 0

1 2 3 4
The calculate A2
1 0 3 5 7 (Min(A1 [1,3] OR A1 [1,2] + A1 [2,3])
2 8 0 2 15
∞ 3+2=5
3 5 8 0 1
4 2 5 7 0 Min(A1 [1,4] OR A1 [1,2] + A1 [2,4])
7 3+ 15=18
(Min(A1 [4,1] OR A1 [4,2] + A1 [2,1]) Min(A1 [3,1] OR A1 [3,2] + A1 [2,1])
2 2+8 =10 5 8+ 8=16
• Min(A1 [4,3] OR A1 [4,1] + A1 [1,3])
∞ 5+2=7 Min(A1 [3,4] OR A1 [3,2] + A1 [2,4])
1 8+ 15=23

85 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 To find A3 take the 3nd raw and column as it is from A2 and the diagonals will be 0

1 2 3 4
The calculate A3
1 0 3 5 6 (Min(A2 [1,2] OR A2 [1,3] + A2 [3,2])
2 7 0 2 3
3 5+8=13
3 5 8 0 1
4 2 5 7 0 Min(A2 [1,4] OR A2 [1,3] + A2 [3,4])
7 5+1=6
The calculate A1 (2,3)
(Min(A2 [4,1] OR A2 [4,3] + A2 [3,1]) Min(A2 [2,1] OR A2 [2,3] + A2 [3,1])
2 7+0=7 8 2+5=7
• Min(A2 [4,2] OR A2 [4,3] + A2 [3,2]) Min(A2 [2,4] OR A2 [2,3] + A2 [3,4])
5 7+6=13
15 2+ 1=3

86 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 To find A4 take the 3nd raw and column as it is from A3 and the diagonals will be 0

The calculate A4
1 2 3 4
1 0 3 5 6 (Min(A3 [1,2] OR A3 [1,4] + A3 [4,2])
2 5 0 2 3 3 6+5=11
3 3 6 0 1
Min(A3 [1,3] OR A3 [1,4] + A3 [4,3])
4 2 5 7 0
5 6+7=12
The calculate A1 (2,3)
(Min(A3 [3,1] OR A3 [3,4] + A3 [4,1]) Min(A3 [2,1] OR A3 [2,4] + A3 [4,1])
5 1+2 =3 7 3+2=5
• Min(A3 [3,2] OR A3 [3,4] + A3[4,2]) Min(A3 [2,3] OR A3 [2,4] + A3 [4,3])
8 1+5=6
2 3+0

87 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Check whether the last solution is correct or not.

A4.

1 2 3 4
1 0 3 5 6
2 5 0 2 3
3 3 6 0 1
4 2 5 7 0

88 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Assignment (2)

89 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 Chapter – Five
Graph Algorithms

90 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Introduction to Greedy Algorithms
A greedy algorithm, as the name suggests, always makes the
choice that seems to be the best at that moment.
This means that it makes a locally-optimal choice in the hope
that this choice will lead to a globally-optimal solution.
However, generally greedy algorithms do not provide globally
optimized solutions.
A greedy algorithm is an algorithmic paradigm that follows the
problem solving heuristic of making the locally optimal choice
at each stage with the hope of finding a global optimum.
91 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Cont..
 In general, greedy algorithms have five components:
A candidate set, from which is set of solution is created
A selection function, which chooses the best candidate to be
added to the solution
A feasibility function, that is used to determine if a candidate
can be used to contribute to a solution
An objective function, which assigns a value to a solution, or a
partial solution, and
A solution function, which will indicate when we have
discovered a complete solution

92 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Advantages and Disadvantages of Greedy Algorithm
Finding solution is quite easy with a greedy algorithm for a problem.
Analyzing the run time for greedy algorithms will generally be much
easier than for other techniques (like Divide and conquer).
The difficult part is that for greedy algorithms you have to work
much harder to understand correctness issues. Even with the
correct algorithm, it is hard to prove why it is correct. Proving that
a greedy algorithm is correct is more of an art than a science.

93 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

List of Algorithms based on Greedy Algorithm
The greedy algorithm is quite powerful and works
well for a wide range of problems.
Many algorithms can be viewed as applications of
the Greedy algorithms, such as :
Dijkstra's algorithm
Minimal Spanning Tree Algorithm

94 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Minimum spanning tree
What is spanning tree?
Is a tree that can be generated from a given graph.
All vertices must include with n-1 edges from the given graph.
No cycle in tree
Example Graph G=(V,E)
Where V={1,2,3,4,5,6}
E={(1,2)(2,3)(3,4)(4,5)(5,6)(6,1)}

95 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Generating MST

S
A B C

96 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont.…
Tree s is sub set of graph G
Where S=(V’,G’)
V’=V and edge E’=n-1

 How to calculate possible spanning tree

 E c V- number of cycles
 Where E is number of edges
 V is vertex and c combination
97 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Cont..
Assume that we weighted graph so we try to find the shortest MSP
example
Graph A B C

Cost =13 cost= 9 Cost=14

98 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Cont.…
But is difficult to find out the minimum spanning tree
But three ways to find out
1st way is generating all the possible spanning tree’s and
select a tree with minimum cost.
But it is long and time taking even some times difficult
2nd way is using greedy algorithm
 Primes Algorithm
 Kruskal's algorithm

99 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Prim's Algorithm
Prims algorithm says
1st just select the min cost edge
Always select the minimum cost edge
But make sure that it is connected to
the previous selected vertices

100 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 1
10 28

2
6

14

16
25 7

24

3
18
5

12
22
4

101 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Example

1
1
1

1
10 10
10 10

6
6
6

25 25
25

3
5
5
5

12
22 22

44
4
102 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
 1

1
10 10

2
6

6
14

16 7 16
25 25

3
5

5
12 12
22 22
44

44
Cost = 99
103 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Kruskal's Algorithm
 Always select edge with minimum cost even it is not connected to
the previous
 Example the same example Now the next smaller

1
edge is 18 but we will not
10 select that because it
1

makes cycle. No cycle in

2
10 28
tree.

6
14
16 from greedy rules A
2
6

7
25 feasibility function will
14 reject using this

3
16
7 Next 24 but we will not

5
25
12
24 22
use that b/c of cycle.
3

4
18
5

22
12
Cost = 99
4

104 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Can we apply both the greedy algorithm’s to the following
un-connected graph

No prim’s
Kruskal’s might work
Because Kruskal’s might give
tree not for the whole but
individually.

105 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

What if there is no given weight?

A ? B A 6 B

4 5 4 5

D ? C D 4 C

2 3 2 3
E

E
106 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Example for students. Using Kruskal’s

2
A

B
2

B
3 2

B
3
3
E E
3 E 3
4 3
4

4
4

C
D

C
D

5
C

Cost= 12 Cost= 12

107 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Dijkstra's algorithm

Dijkstra's algorithm will work for both directed and

undirected graphs
But it doesn’t work with Negative edges.
Single source shortest path algorithm.

108 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 Dijkstra algorithm will generate the following information

109 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

110 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Cont..
 To find the shortest path from a given vertex we need algorithm. Which is
greedy algorithm. Dijkstra's algorithm
 Procedure.

111 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

112 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
113 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
114 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
115 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
116 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
117 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
118 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
119 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
120 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
121 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
122 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
123 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
124 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
125 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
126 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
127 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
128 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
129 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
130 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Example 2 on Dijkstra's algorithm
45

1 50 10 3

2
35

10
20
30

4 15 5 3 6
131 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020
Let’s go…

Starting Vertex 1
2 50 50 45 45 45
3 45 45 45 45 45
4 10 10 10 10 10
5
∞ 25 25 25 25

6 ∞ ∞ ∞ ∞ ∞

132 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Assignment (2)

1 3

2
8 4

10 7
1 3
2

-5

5 15 4

133 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 Graph traversal Algorithm

134 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Graph traversals
For traversal we have to know the following two terms
Visiting a vertex : going into a particular vertex in graph
Exploring a vertex : this refers to when we are at a particular
vertex then visiting all adjacent vertices.
We will discuss both algorithms for traversals
BFS
DFS

135 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

BFS.
 Select vertex 1 as starting vertex, but there is no rule
which one will be selected as star vertex.
 BFS
 So it can be any vertex
 SELECT 1 as starting
 Start exploring 1 visit all adjacent
vertices
 1,5,4,2 order doesn't mater
 It can be 1,2,4,5 then explore 2
 1,2,4,5,7,3,6 finished no
unvisited vertex.

136 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

BFS.
 DFS

Lets use the same start 1

 1, then explore it
 1,2 but still there are other adjacent
but don’t visit them just explore next
vertex which is 2
 Once you have reach a new vertex just
explore it.
 1,2,3, the explore 3 there is nothing
 1,2,3,6,7,5,4,

137 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Example 2
 BFS
 1,2,3,4,5,6,7
 Thislevel based search or lever order on a
binary tree.
 this as Level Order traversal

 DFS
 1,2,4,5,3,6,7
 This level based search or lever order on
a binary tree.
 this as pre-Order traversal

138 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Example 3 using data structure

139 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

BFS
 lets use Queue
1
 Start from 1,
 Insert one in the queue 1 4 2

draw V1
 Perform repeating steps
 Take 1 from queue start
explore

 BFS

140 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

BFS
 Now 1 is completely 1 4 2 3
explored since there is
no unexplored adjacent .
 select vertex to
explore from the queue
that is vertex 4
 And 4 is completely
explored.

 BFS

141 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

BFS
 Now 1 select vertex to 1 4 2 3 5 8 7
explore which is 2
 Who are the adjacent
vertices to 2
 3,5,7,8 I can explore in
any order.
 Cheek the it is already
explored
 And now 2 completed
 BFS

142 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

BFS
1 4 2 3 5 8 7 10 9
 Select next vertex to explore
from the queue 3
 3 is completely explored
 And select next from the queue 5
 Any adjacent to 5?
 yes 8,7 and 6

 BFS

143 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

BFS
 And select next from the queue 1 4 2 3 5 8 7 10 9 6
5
 Any adjacent to 5?
 yes 8,7 and 6 BUT 8 and 7 are
already visited. Just only 6.
 Next vertex from queue is 8 and
explore it. But already visited
 The same to the remaining
vertices 7,10,9,6

144 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Some additional valid BFS

 1,2,4,8,5,7,3,6,10,9
 5,2,8,7,6,3,1,9,10,4
 etc

145 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

DFS
 lets use stack
 Start from 1, and
explore 1
 Then visit 4 by suspend
1 & start explore 4
 Go to 3 & explore it by
suspend 4 4
 From 3 we can go to 10 1
 And now there is no
adjacent of 10
 DFS

146 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

DFS
 So if there is no further
exploration go back & continue
exploration from the stack.
 Take 3 from the stack & Explore it
go to 9
 Explore 9 by suspend 3 again 32
 but noting, 44
 go back and take 3 then explore it 11
 Then got 2 and
 explore 2 now we don’t suspend 3
since no more unvisited adjacent .
 Explore 8 but suspend 2
 DFS

147 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

DFS
 Go to 7 and suspend 8
5
 Explore 7 and Go to 5
7
 Explore 5 by suspend 7 and go 88
to 6. 22
 Explore 6 by suspend 5 44
11

This is the DFS Spanning tree

 DFS

148 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

Some other possible DFS for the same graph

1.1,2,8,7,5,6,3,9,10,4
2.3,4,1,2,5,6,7,8,10,9

149 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020

 END

150 Prepared By :-ESAYAS FANTA(RVU CS DEPARTMENT) 5/12/2020