Aksum Institute of Technology

Faculty of Electrical and Computer Engineering

Department of Computer Engineering

Digital Notes on Design and Analysis of Algorithms

Compiled By: Haftom Aregawi

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

1
 Course description:

 This course teaches techniques for designing efficient algorithms and analyzing their
performance. Students learn common algorithmic strategies and complexity analysis to solve
computational problems effectively.

Course Objectives:

 At the end of this course, students will be able to

 Analyze and compare the performance of algorithms by using mathematical techniques.

 Apply algorithm design paradigms to solve problems efficiently.

 Understand advanced data structures and their effect on performance.

 Classify problems based on complexity and hardness (P, NP, NP-Complete).

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

1
 1. Unit One: Introduction (Week 1 – Week 2)

1.1. Algorithm
1.2. Pseudo-code for expressing algorithms
1.3. Performance Analysis-Space complexity
1.4. Time complexity
1.5. Asymptotic Notation- Big oh-notation
1.6. Omega notation
1.7. Theta notation and little oh-notation
1.8. Probabilistic Analysis
1.9. Amortized Analysis

Description:

Objectives:

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

2
Algorithm:
An algorithm is a finite sequence of instructions, each of which has a clear meaning and
can be performed with a finite amount of effort in a finite length of time. No matter
what the input values may be, an algorithm terminates after executing a finite number
of instructions. Algorithms are not just computer programs; they are abstract, step-by-step
procedures.

Example: Find the largest number in an array:

1. Assume first number is largest.

2. Compare with the next number.
3. Replace largest if next number is bigger.
4. Repeat until end.
5. Output largest.

An algorithm should have the following characteristics:

 Unambiguous: Algorithm should be clear and unambiguous. Each of its steps

(or phases), and their inputs/outputs should be clear and must lead to only one
meaning.
 Input: An algorithm should have 0 or more well-defined inputs.
 Output: An algorithm should have 1 or more well-defined outputs, and should
match the desired output.
 Finiteness: Algorithms must terminate after a finite number of steps.
 Feasibility: Should be feasible with the available resources.
 Independent: An algorithm should have step-by-step directions, which should
be independent of any programming code.

Algorithm for problem solving:

The main steps for Problem Solving are:

 Problem definition
 Algorithm design / Algorithm specification
 Algorithm analysis
 Implementation
 Testing
 [Maintenance]
Pseudo-code for expressing algorithms:

Algorithm Specification: Algorithm can be described in three ways.

1. Natural language like English: When this way is choused care should be taken, we should ensure
that each & every statement is definite.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

3
2. Graphic representation called flowchart: This method will work well when the algorithm is
small and simple.

3. Pseudo-code Method: In this method, we should typically describe algorithms as program, which
resembles language like C and C++

Pseudo-code: High-level description of an algorithm.

 More structured than plain English.
 Less detailed than a program.
 Preferred notation for describing algorithms.
 Hides program design issues.

Example of Pseudo-code: To find the max element of an array

Performance Analysis:
The performance of a program is the amount of computer memory and time needed to run a program. We
use two approaches to determine the performance of a program. One is analytical, and the other
experimental. In performance analysis we use analytical methods, while in performance measurement we
conduct experiments.

Why Analyze Algorithms?

With ever-increasing computer speeds, one might ask why we still need to analyze algorithms. The answer lies in
scalability. A poor algorithm on a fast machine will almost always be outperformed by a superior algorithm on a
slower machine for large inputs. Algorithm analysis gives us a mathematical way to predict and compare the
performance of different algorithms without having to implement and run them.

Complexity Analysis: We analyze two main types of resources:

 Time Complexity: The amount of computational time the algorithm needs to run.
 Space Complexity: The amount of memory the algorithm needs to run.

We are primarily interested in the growth rate of these resources as the input size (n) increases.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

4
The complexity function f(n) for certain cases are:

 Best Case: Minimum time required for program execution.

 Average Case: Average time required for program execution.
 Worst Case: Maximum time required for program execution.

Asymptotic Notations:
Asymptotic notations are mathematical tools used to describe the running time of an algorithm in
relation to the input size .

 Big O (O): Represents the upper bound of an algorithm's running time. It describes the
worst-case scenario. For example, if we say an algorithm has a time complexity of O(n²),
it means the running time grows at most quadratically with the input size.

 Big Omega (Ω): Represents the lower bound of an algorithm's running time. It describes
the best-case scenario.

 Big Theta (Θ): Represents the tight bound of an algorithm's running time. It means the
algorithm's running time is bounded both above and below by the same function. For

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

5
 instance, if an algorithm is Θ(n log n), it will grow proportionally to n log n for large
inputs, no better and no worse .

 Little Oh Notation: The little Oh is denoted as o. It is defined as : Let, f(n} and g(n} be the
non-negative functions then

Common Asymptotic Notations: Following is a list of some common asymptotic notations

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

6
Probabilistic Analysis:
It is the use of probability in the analysis of problems.

In order to perform a probabilistic analysis, we must use knowledge of, or make assumptions
about, the distribution of the inputs. Then we analyze our algorithm, computing an average-case
running time, where we take the average over the distribution of the possible inputs.

Amortized Analysis:

In an amortized analysis, we average the time required to perform a sequence of datastructure

operations over all the operations performed. With amortized analysis, we can show that the
average cost of an operation is small, if we average over a sequence of operations, even though a
single operation within the sequence might be expensive. Amortized analysis differs from
average-case analysis in that probability is not involved; an amortized analysis guarantees the
average performance of each operation in the worst case.

Three most common techniques used in amortized analysis:

 Aggregate Analysis: in which we determine an upper bound T(n) on the total cost of a
sequence of n operations. The average cost per operation is then T(n)/n. We take the
average cost as the amortized cost of each operation
 Accounting method: When there is more than one type of operation, each type of
operation may have a different amortized cost. The accounting method overcharges some
operations early in the sequence, storing the overcharge as ―prepaid credit‖ on specific
objects in the data structure. Later in the sequence, the credit pays for operations that are
charged less than they actually cost.
 Potential method - The potential method maintains the credit as the ―potential energy‖
of the data structure as a whole instead of associating the credit with individual objects
within the data structure. The potential method, which is like the accounting method in
that we determine the amortized cost of each operation and may overcharge operations
early on to compensate for undercharges later

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

7
2. Unit Two: Divide and Conquer (Week 3 – Week 4)

2.1. General method

2.2. Applications-Binary search
2.3. Quick sort, Merge sort
2.4. Strassen‘s matrix multiplication.

Description:

Objectives:

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

8
General Method:
Divide and conquer is a design strategy which is well known to breaking down efficiency
barriers. When the method applies, it often leads to a large improvement in time complexity. For
example, from O (n2) to O (n log n) to sort the elements.

Divide and conquer strategy is as follows: divide the problem instance into two or more smaller
instances of the same problem, solve the smaller instances recursively, and assemble the
solutions to form a solution of the original instance. The recursion stops when an instance is
reached which is too small to divide. When dividing the instance, one can either use whatever
division comes most easily to hand or invest time in making the division carefully so that the
assembly is simplified.

It works in three steps:

 Divide: The main problem is broken down into smaller, identical sub-problems.
 Conquer: The sub-problems are solved recursively. If a sub-problem is small enough (a
base case), it is solved directly.
 Combine: The solutions to the sub-problems are combined to create a solution to the
original problem.

Applications of Divide and conquer rule or algorithm:

 Binary search,
 Quick sort,
AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
9
  Merge sort,
 Strassen‘s matrix multiplication

Binary Search:

 Problem: Find a given element x in a sorted array.

 Algorithm:

 Compare x with the middle element.

 If x matches the middle element, we return the middle index.
 If x is greater than the middle element, then x can only lie in the right half sub-array. So,
we apply the algorithm recursively to the right half.
 Else ( x is smaller), we apply the algorithm recursively to the left half .
 Time Complexity: O(log n) in the worst case. This is a massive improvement over linear
search's O(n) for large n.

Recursive Binary Search Algorithm

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

10
 Iterative Binary Search Algorithm

Merge Sort:

 Algorithm :

 Divide: Divide the n-element sequence to be sorted into two sub-sequences

of n/2 elements each.
 Conquer: Sort the two sub-sequences recursively using merge sort.
 Combine: Merge the two sorted sub-sequences to produce the sorted answer.
 Analysis: The recurrence is T(n) = 2T(n/2) + Θ(n). By the Master Theorem, this solves
to Θ(n log n) in all cases (best, worst, average).

Quick Sort:

 Algorithm:

 Divide: Pick an element, called a pivot, from the array. 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 (this is the partitioning step).
 Conquer: 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.
 Combine: This step is trivial, as the array is sorted in place.
AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
11
  Analysis:

o Worst-case: O(n²). This happens when the pivot is always the smallest or largest
element (e.g., on an already sorted array).
o Average/Best-case: Θ(n log n).

Strassen’s Matrix Multiplication:

 Standard Algorithm: Multiplying two n x n matrices takes Θ(n³) time.

 Strassen's Idea: It uses a divide-and-conquer approach to multiply two 2x2 matrices using
only 7 multiplications instead of 8, at the cost of some extra additions .
 Complexity: This leads to a recurrence of T(n) = 7T(n/2) + Θ(n²), which solves to
approximately Θ(n^2.807), which is better than Θ(n³).
.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

12
 3. Unit Three: Searching and Traversal Techniques (Week 5 – Week 6)

3.1. Efficient non - recursive binary tree traversal algorithm

3.2. Disjoint set operations, union and find algorithms
3.3. Spanning trees
3.4. Graph traversals - Breadth first search and Depth first search,
3.5. AND / OR graphs
3.6. Game trees
3.7. Connected Components
3.8. Bi - connected components.
3.9. Disjoint Sets- disjoint set operations
3.10. Union and find algorithms

Description:

Objectives:

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

13
Searching and Traversal Techniques:

Non recursive Inorder traversal algorithm:

1. Start from the root. Let‘s it is current.

2. If current is not NULL. Push the node on to stack.
3. Move to left child of current and go to step 2.
4. If current is NULL, and stack is not empty, pop node from the stack.
5. Print the node value and change current to right child of current.
6. Go to step 2.

So we go on traversing all left node. As we visit the node. We will put that node into
[Link] need to visit parent after the child and as we will encounter parent first when
start from root. it's case for LIFO :) and hence the stack). Once we reach NULL node. We will
take the node at the top of the stack. Last node which we visited, Print it.

Check if there is right child to that node. If yes, move right child to stack and again start
traversing left child node and put them on to stack. Once we have traversed all nodes. Our stack
will be empty.

Non recursive postorder traversal algorithm:

Left node. Right node and last parent node.

1.1 Create an empty stack

2.1 Do Following while root is not NULL

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

14
 a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child is at top of stack, then
remove the right child from stack, push the root back and set root as root's right child.
Ia) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
Disjoint Sets: If Si and Sj, i≠j are two sets, then there is no element that is in both Si and Sj..
For example: n=10 elements can be partitioned into three disjoint sets,

Disjoint set Operations:

 Disjoint set Union
 Find(i)
Disjoint set Union: Means Combination of two disjoint sets elements. Form above example S1
U S2 ={1,7,8,9,5,2,10 }
For S1 U S2 tree representation, simply make one of the tree is a sub-tree of the other.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

15
Find: Given element i, find the set containing i.
Form above example:
Find(4)S3
Find(1)S1
Find(10)S2

Data representation of sets:

Tress can be accomplished easily if, with each set name, we keep a pointer to the root of the tree
representing that set.

For presenting the union and find algorithms, we ignore the set names and identify sets just by
the roots of the trees representing them.

For example: if we determine that element ‗i‘ is in a tree with root ‗j‘ has a pointer to entry ‗k‘
in the set name table, then the set name is just name[k]

For unite (adding or combine) to a particular set we use FindPointer function.

Example: If you wish to unite to Si and Sj then we wish to unite the tree with roots

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

16
FindPointer (Si) and FindPointer (Sj)

FindPointeris a function that takes a set name and determines the root of the tree that
represents it.

For determining operations:

Find(i)1St determine the root of the tree and find its pointer to entry in setname table.

Union(i, j)Means union of two trees whose roots are i and j.

If set contains numbers 1 through n, we represents tree node

P[1:n].

nMaximum number of elements.

Each node represent in array

Find(i) by following the indices, starting at i until we reach a node with parent value -1.
Example: Find(6) start at 6 and then moves to 6‘s parent. Since P[3] is negative, we reached the root.

If n numbers of roots are there then the above algorithms are not useful for union and find.
For union of n treesUnion(1,2), Union(2,3), Union(3,4),…..Union(n-1,n).
For Find i in n treesFind(1), Find(2),….Find(n).
Time taken for the union (simple union) is O(1) (constant).
For the n-1 unionsO(n).

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

17
Time taken for the find for an element at level i of a tree is O(i).
For n finds O(n2).
To improve the performance of our union and find algorithms by avoiding the creation of degenerate
trees. For this we use a weighting rule for union(i, j)
Weighting rule for Union(i, j):
If the number of nodes in the tree with root ‗i‘ is less than the tree with root ‗j‘, then make ‗j‘ the
parent of ‗i‘; otherwise make ‗i‘ the parent of ‗j‘.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

18
Lemma: Let T be a tree with m nodes created as a result of a sequence of unions each performed
using WeightedUnion. The height of T is no greater than
|log2 m|+1.

Collapsing rule: If ‗j‘ is a node on the path from ‗i‘ to its root and p[i]≠root[i], then set p[j] to
root[i].

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

19
Collapsing find algorithm is used to perform find operation on the tree created by Weighted
Union.
For example: Tree created by using Weighted Union

Now process the following eight finds: Find(8), Find(8),……….Find(8)

If SimpleFind is used, each Find(8) requires going up three parent link fields for a total of 24
moves to process all eight finds.
When CollapsingFind is uised the first Find(8) requires going up three links and then resetting two
links. Total 13 movies requies for process all eight finds.

Spanning Tree:-
Let G=(V<E) be an undirected connected graph. A sub graph t=(V,E1) of G is a spanning tree of G
iff t is a tree.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

20
Spanning Trees have many applications.
Example:-
It can be used to obtain an independent set of circuit equations for an electric network.
Any connected graph with n vertices must have at least n-1 edges and all connected graphs with
n-1 edges are trees. If nodes of G represent cities and the edges represent possible
communication links connecting two cities, then the minimum number of links needed to
connect the n cities is n-1.
There are two basic algorithms for finding minimum-cost spanning trees, and both are greedy
algorithms
Prim‘s Algorithm
Kruskal‘s Algorithm

Prim’s Algorithm: Start with any one node in the spanning tree, and repeatedly add the cheapest
edge, and the node it leads to, for which the node is not already in the spanning tree.

Kruskal’s Algorithm: Start with no nodes or edges in the spanning tree, and repeatedly add the
cheapest edge that does not create a cycle.

Connected Component:

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

21
Connected component of a graph can be obtained by using BFST (Breadth first search and
traversal) and DFST (Dept first search and traversal). It is also called the spanning tree.

BFST (Breadth first search and traversal):

 In BFS we start at a vertex V mark it as reached (visited).

 The vertex V is at this time said to be unexplored (not yet discovered).
 A vertex is said to been explored (discovered) by visiting all vertices adjacent from it.
 All unvisited vertices adjacent from V are visited next.
 The first vertex on this list is the next to be explored.
 Exploration continues until no unexplored vertex is left.
 These operations can be performed by using Queue.

This is also called connected graph or spanning tree. Spanning trees obtained using BFS then it
called breadth first spanning trees.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

22
DFST(Dept first search and traversal).:
 Dfs different from bfs

 The exploration of a vertex v is suspended (stopped) as soon as a new vertex is reached.

 In this the exploration of the new vertex (example v) begins; this new vertex has been
explored, the exploration of v continues.
 Note: exploration start at the new vertex which is not visited in other vertex exploring
and choose nearest path for exploring next or adjacent vertex.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

23
 AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
24
A graph G is biconnected, iff (if and only if) it contains no articulation point (joint or junction).
A vertex v in a connected graph G is an articulation point, if and only if (iff) the deletion of
vertex v together with all edges incident to v disconnects the graph into two or more none empty
components.

The presence of articulation points in a connected graph can be an undesirable(un wanted)

feature in many cases.
For example
if G1Communication network with
Vertex communication stations.
EdgesCommunication lines.
Then the failure of a communication station I that is an articulation point, then we loss the
communication in between other stations. F
Form graph G1

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

25
If the graph is bi-connected graph (means no articulation point) then if any station i fails, we can
still communicate between every two stations not including station i.

There is an efficient algorithm to test whether a connected graph is bi-connected. If the case of
graphs that are not bi-connected, this algorithm will identify all the articulation points.

Once it has been determined that a connected graph G is not bi-connected, it may be desirable
(suitable) to determine a set of edges whose inclusion makes the graph bi-connected.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

26
 4. Unit Four: Greedy Method (Week 7 – Week 9)

4.1. General method,

4.2. Applications
4.3. Job sequencing with deadlines
4.4. 0/1 knapsack problem
4.5. Minimum cost spanning trees
4.6. Single source shortest path problem

Description:

Objectives:

 Understand the greedy-choice property and its implications.

 Apply greedy strategies to solve optimization problems.
 Design and analyze greedy algorithms for MST (Kruskal, Prim) and shortest
paths (Dijkstra).
 Differentiate between greedy and other paradigms.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

27
A greedy algorithm makes the choice that seems best at the exact moment, without considering
future implications. It hopes that this series of locally optimal choices will lead to a globally
optimal solution. This strategy works for problems with two key properties:

1. Greedy Choice Property: A global (overall) optimal solution can be reached by making a
locally optimal (best) choice.
2. Optimal Substructure: An optimal solution to the problem contains within it optimal
solutions to sub-problems.

Feasible solution: Most problems have n inputs and its solution contains a subset of inputs that
satisfies a given constraint (condition). Any subset that satisfies the constraint is called feasible
solution.

Optimal solution: To find a feasible solution that either maximizes or minimizes a given
objective function. A feasible solution that does this is called optimal solution.

The greedy method suggests that an algorithm works in stages, considering one input at a time.
At each stage, a decision is made regarding whether a particular input is in an optimal solution.

Greedy algorithms neither postpone nor revise the decisions (ie., no back tracking).

Example: Kruskal‘s minimal spanning tree. Select an edge from a sorted list, check, decide, and
never visit it again.

Application of Greedy Method:

 Job sequencing with deadline

 0/1 knapsack problem
 Minimum cost spanning trees
 Single source shortest path problem.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

28
Selection Function, that selects an input from a[] and removes it. The selected input‘s value
is assigned to x.
Feasible Boolean-valued function that determines whether x can be included into the
solution vector.
Union function that combines x with solution and updates the objective function.

Knapsack problem:

The knapsack problem or rucksack (bag) problem is a problem in combinatorial optimization:

Given a set of items, each with a mass and a value, determine the number of each item to include
in a collection so that the total weight is less than or equal to a given limit and the total value is
as large as possible.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

29
There are two versions of the problems

1. 0/1 knapsack problem

2. Fractional Knapsack problem
a. Bounded Knapsack problem.
b. Unbounded Knapsack problem.

Solutions to knapsack problems

 Brute-force approach: Solve the problem with a straight forward algorithm

 Greedy Algorithm: Keep taking most valuable items until maximum weight is reached
or taking the largest value of each item by calculating vi=valuei/Sizei
 Dynamic Programming: Solve each sub problem once and store their solutions in an
array.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

30
Ex: Consider 3 objects whose profits and weights are defined as
(P1, P2, P3) = ( 25, 24, 15 )
W1, W2, W3) = ( 18, 15, 10 )
n=3number of objects
m=20Bag capacity

Consider a knapsack of capacity 20. Determine the optimum strategy for placing the objects in to
the knapsack. The problem can be solved by the greedy approach where in the inputs are
arranged according to selection process (greedy strategy) and solve the problem in stages. The
various greedy strategies for the problem could be as follows.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

31
 AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
32
 AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
33
Single Source Shortest Paths:

 Graphs can be used to represent the highway structure of a state or country with vertices
representing cities and edges representing sections of highway.
 The edges have assigned weights which may be either the distance between the 2 cities
connected by the edge or the average time to drive along that section of highway.
 For example if A motorist wishing to drive from city A to B then we must answer the
following questions
 Is there a path from A to B
 If there is more than one path from A to B which is the shortest path
 The length of a path is defined to be the sum of the weights of the edges on that path.
AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
34
Given a directed graph G(V,E) with weight edge w(u,v). e have to find a shortest path from
source vertex S∈v to every other vertex v1∈ v-s.


 To find SSSP for directed graphs G(V,E) there are two different algorithms.

 Bellman-Ford Algorithm
 Dijkstra‘s algorithm

 Bellman-Ford Algorithm: allow –ve weight edges in input graph. This algorithm either
finds a shortest path form source vertex S∈V to other vertex v∈V or detect a –ve weight
cycles in G, hence no solution. If there is no negative weight cycles are reachable form
source vertex S∈V to every other vertex v∈V

 Dijkstra‘s algorithm: allows only +ve weight edges in the input graph and finds a shortest
path from source vertex S∈V to every other vertex v∈V.

 Consider the above directed graph, if node 1 is the source vertex, then shortest path from
1 to 2 is 1,4,5,2. The length is 10+15+20=45.

 To formulate a greedy based algorithm to generate the shortest paths, we must conceive
of a multistage solution to the problem and also of an optimization measure.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

35
  This is possible by building the shortest paths one by one.

 As an optimization measure we can use the sum of the lengths of all paths so far
generated.

 If we have already constructed ‗i‘ shortest paths, then using this optimization measure,
the next path to be constructed should be the next shortest minimum length path.

 The greedy way to generate the shortest paths from Vo to the remaining vertices is to
generate these paths in non-decreasing order of path length.

 For this 1st, a shortest path of the nearest vertex is generated. Then a shortest path to the
2nd nearest vertex is generated and so on.

Minimum Cost Spanning Tree:

Spanning Tree: A Sub graph ‗n‘ of o graph ‗G‘ is called as a spanning tree if

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

36
 (i) It includes all the vertices of ‗G‘
(ii) It is a tree

Minimum cost spanning tree: For a given graph ‗G‘ there can be more than one spanning tree.
If weights are assigned to the edges of ‗G‘ then the spanning tree which has the minimum cost of
edges is called as minimal spanning tree.

The greedy method suggests that a minimum cost spanning tree can be obtained by contacting
the tree edge by edge. The next edge to be included in the tree is the edge that results in a
minimum increase in the some of the costs of the edges included so far.

There are two basic algorithms for finding minimum-cost spanning trees, and both are greedy
algorithms

Prim‘s Algorithm
Kruskal‘s Algorithm

Prim’s Algorithm: Start with any one node in the spanning tree, and repeatedly add the cheapest
edge, and the node it leads to, for which the node is not already in the spanning tree.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

37
 AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
38
 AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
39
 AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
40
 5. Unit Five: Dynamic Programming (Week 10 – Week 11)

5.1. General method

5.2. Applications-Matrix chain multiplication
5.3. Optimal binary search trees
5.4. 0/1 knapsack problem
5.5. All pairs shortest path problem
5.6. Travelling sales person problem
5.7. Reliability design

Description:

Objectives:

 Contrast dynamic programming with divide-and-conquer and greedy methods.

 Identify problems with overlapping sub-problems and optimal substructure.
 Develop DP solutions by defining states, recurrences, and base cases.
 Apply DP to classic problems: 0/1 Knapsack, LCS, Floyd-Warshall, Bellman-
Ford.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

41
Dynamic programming is a name, coined by Richard Bellman in 1955. Dynamic programming,
as greedy method, is a powerful algorithm design technique that can be used when the solution to
the problem may be viewed as the result of a sequence of decisions. In the greedy method we
make irrevocable decisions one at a time, using a greedy criterion. However, in dynamic
programming we examine the decision sequence to see whether an optimal decision sequence
contains optimal decision subsequence.

When optimal decision sequences contain optimal decision subsequences, we can establish
recurrence equations, called dynamic-programming recurrence equations, that enable us to solve
the problem in an efficient way.

Dynamic programming is based on the principle of optimality (also coined by Bellman). The
principle of optimality states that no matter whatever the initial state and initial decision are, the
remaining decision sequence must constitute an optimal decision sequence with regard to the
state resulting from the first decision. The principle implies that an optimal decision sequence is
comprised of optimal decision subsequences. Since the principle of optimality may not hold for
some formulations of some problems, it is necessary to verify that it does hold for the problem
being solved. Dynamic programming cannot be applied when this principle does not hold.

The steps in a dynamic programming solution are:


 Verify that the principle of optimality holds
 Set up the dynamic-programming recurrence equations
 Solve the dynamic-programming recurrence equations for the value of the optimal
solution.
 Perform a trace back step in which the solution itself is constructed.

Dynamic programming differs from the greedy method since the greedy method produces only
one feasible solution, which may or may not be optimal, while dynamic programming produces
all possible sub-problems at most once, one of which guaranteed to be optimal. Optimal
solutions to sub-problems are retained in a table, thereby avoiding the work of re-computing the
answer every time a sub-problem is encountered.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

42
The divide and conquer principle solve a large problem, by breaking it up into smaller problems
which can be solved independently. In dynamic programming this principle is carried to an
extreme: when we don't know exactly which smaller problems to solve, we simply solve them
all, then store the answers away in a table to be used later in solving larger problems. Care is to
be taken to avoid re-computing previously computed values, otherwise the recursive program
will have prohibitive complexity. In some cases, the solution can be improved and in other cases,
the dynamic programming technique is the best approach.

Two difficulties may arise in any application of dynamic programming:

1. It may not always be possible to combine the solutions of smaller problems to form the
solution of a larger one.
2. The number of small problems to solve may be un-acceptably large.

There is no characterized precisely which problems can be effectively solved with dynamic
programming; there are many hard problems for which it does not seen to be applicable, as well
as many easy problems for which it is less efficient than standard algorithms.

Multi Stage Graphs:

A multistage graph G = (V, E) is a directed graph in which the vertices are partitioned into k > 2
disjoint sets Vi, 1 < i < k. In addition, if <u, v> is an edge in E, then u E Vi and v E Vi+1 for
some i, 1 < i < k.

Let the vertex ‗s‘ is the source, and ‗t‘ the sink. Let c (i, j) be the cost of edge <i, j>. The cost of
a path from ‗s‘ to ‗t‘ is the sum of the costs of the edges on the path. The multistage graph
problem is to find a minimum cost path from ‗s‘ to ‗t‘. Each set Vi defines a stage in the graph.
Because of the constraints on E, every path from ‗s‘ to ‗t‘ starts in stage 1, goes to stage 2, then
to stage 3, then to stage 4, and so on, and eventually terminates in stage k.

A dynamic programming formulation for a k-stage graph problem is obtained by first noticing
that every s to t path is the result of a sequence of k – 2 decisions. The ith decision involves
determining which vertex in vi+1, 1 < i < k - 2, is to be on the path. Let c (i, j) be the cost of the
path from source to destination. Then using the forward approach, we obtain:
cost (i, j) = min {c (j, l) + cost (i + 1, l)}

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

43
l c Vi + 1
<j, l> c E

Complexity Analysis:
The complexity analysis of the algorithm is fairly straightforward. Here, if G has ~E~ edges,
then the time for the first for loop is CJ ( V~ +~E ).

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

44
Example 1: Find the minimum cost path from s to t in the multistage graph of five stages shown
below. Do this first using forward approach and then using backward approach.

0/1 Knapsack Problem:

 Problem: Given n items, each with a weight w[i] and a value v[i], and a knapsack with
capacity W, what is the maximum value that can be carried? Unlike the fractional
version, an item must be taken entirely (1) or left behind (0).
 DP Formulation :

 Let dp[i][j] be the maximum value achievable using the first i items and a
capacity of j.
 Recurrence: dp[i][j] = max( dp[i-1][j] , dp[i-1][j - w[i]] + v[i] ) for j >= w[i].

 The first term means we don't take item i.

 The second term means we take item i, so we add its value and reduce the capacity.
 Base Case: dp[0][j] = 0 for all j.

Longest Common Subsequence (LCS):

 Problem: Given two sequences X and Y, find the longest subsequence that is common to
both .

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

45
  DP Formulation :

 Let L[i][j] be the length of the LCS of the first i characters of X and the
first j characters of Y.

 Recurrence:

 If X[i] == Y[j]: L[i][j] = L[i-1][j-1] + 1

 Else: L[i][j] = max( L[i-1][j], L[i][j-1] )

Floyd-Warshall Algorithm (All-Pairs Shortest Paths):

 Problem: Find the shortest paths between every pair of vertices in a weighted graph
(allowing negative weights but no negative cycles).
 DP Idea: Let dist[k][i][j] be the shortest path from i to j using only vertices from the
set {1, 2, ..., k} as intermediate vertices. The final solution is dist[n][i][j].
 Recurrence: dist[k][i][j] = min( dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j] ).

 This means either the best path using the first k-1 vertices is enough, or going
through k yields a shorter path.

Bellman-Ford Algorithm (Single-Source with Negative Weights):

 Problem: Find the shortest path from a source s to all other vertices, even when edges
have negative weights.
 DP Idea: Let dist[u][k] be the shortest path from s to u using at most k edges.
 Recurrence: dist[u][k] = min( dist[u][k-1], min over all edges (v,u) of ( dist[v][k-1] +
w(v,u) ) ).
 The algorithm runs for k = 1 to |V|-1 to find the best path.

Matrix Chain Multiplication:

Given a sequence of matrices A1, A2, A3, ..., An, find the best way (using the minimal number of
multiplications) to compute their product.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

46
  Minimize number of scalar multiplications
 Recurrence:
o M[i,j] = min(M[i,k] + M[k+1,j] + p[i-1]*p[k]*p[j])
 Algorithm:

Travelling sells person problem:

Let G = (V, E) be a directed graph with edge costs Cij. The variable cij is defined such that cij > 0 for
all I and j and cij = a if < i, j> o E. Let |V| = n and assume n > 1. A tour of G is a directed simple
cycle that includes every vertex in V. The cost of a tour is the sum of the cost of the edges on the
tour. The traveling sales person problem is to find a tour of minimum cost. The tour is to be a simple
path that starts and ends at vertex 1.

Let g (i, S) be the length of shortest path starting at vertex i, going through all vertices in S, and
terminating at vertex 1. The function g (1, V – {1}) is the length of an optimal salesperson tour. From
the principal of optimality it follows that:

g(1, V - {1 }) = 2 ~ k ~ n ~c1k ~ g ~ k, V ~ ~ 1, k ~~ ~

min

Generalizing equation 1, we obtain (for i o S)

g ( i, S ) = min{ci j

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

47
j ES

The Equation can be solved for g (1, V – 1}) if we know g (k, V – {1, k}) for all choices of k.

Example 1: For the following graph find minimum cost tour for the traveling salesperson
problem:

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

48
 6. Unit Six: Backtracking (Week 12 – Week 13)

6.1. General method

6.2. Applications-n-queen problem
6.3. Sum of subsets problem
6.4. Graph coloring
6.5. Hamiltonian cycles
6.6. Branch and Bound

Description:

Objectives:

 Understand the concept of state-space trees.

 Implement backtracking for problems with constraints.
 Apply Branch and Bound for optimization problems.
 Differentiate between BFS, DFS, and best-first search in the context of state-
space search.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

49
Backtracking: is a systematic method for finding all (or some) solutions to computational
problems, particularly constraint satisfaction problems. It incrementally builds candidates and
abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly
be extended to a valid solution.

It uses a Depth-First Search (DFS) of the state-space tree.

 N-Queens Problem: The goal is to place N chess queens on an N×N chessboard so that
no two queens threaten each other. The backtracking algorithm places queens one by one
in different columns, starting from the leftmost column. When placing a queen in a
column, it checks for clashes with already placed queens. If a clash is found, it backtracks
and returns false.
 Sum of Subsets: Given a set of positive integers and a target sum, find all subsets that
sum to the target.
 Graph Coloring: Given a graph, assign colors to vertices such that no two adjacent
vertices share the same color, using at most m colors.

Branch and Bound:

Branch and Bound is a general algorithm for finding optimal solutions to various optimization
problems, especially in combinatorial optimization. It is similar to backtracking but is used for
optimization. Instead of stopping when a solution is found, it continues to search for a better one.
It uses a breadth-first or least-cost-first search strategy.

Key Idea: It maintains a global variable for the best solution found so far (the bound). While
traversing the state-space tree, it computes a bound at each node. If the bound of a node is worse
than the current global best solution, that branch is pruned, as it cannot lead to a better solution
than the one we already have.

Applications of Backtracking:

 N Queens Problem
 Sum of subsets problem
 Graph coloring
AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
50
  Hamiltonian cycles.
N-Queens Problem:
It is a classic combinatorial problem. The eight queen‘s puzzle is the problem of placing eight
queens puzzle is the problem of placing eight queens on an 8×8 chessboard so that no two
queens attack each other. That is so that no two of them are on the same row, column, or
diagonal.

The 8-queens puzzle is an example of the more general n-queens problem of placing n queens on
an n×n chessboard.

Here queens can also be numbered 1 through 8

Each queen must be on a different row
Assume queen ‗i‘ is to be placed on row ‗i‘
All solutions to the 8-queens problem can therefore be represented a s s-tuples(x1, x2, x3—x8)
xi the column on which queen ‗i‘ is placed
si{1, 2, 3, 4, 5, 6, 7, 8}, 1 ≤ i ≤8
Therefore the solution space consists of 88 s-tuples.
The implicit constraints for this problem are that no two xi‘s can be the same column and no two
queens can be on the same diagonal.
By these two constraints the size of solution pace reduces from 88 tuples to 8! Tuples.
AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
51
Form example si(4,6,8,2,7,1,3,5)
In the same way for n-queens are to be placed on an n×n chessboard, the solution space consists
of all n! Permutations of n-tuples (1,2,----n).

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

52
Sum of Subsets Problem:

Given positive numbers wi 1 ≤ i ≤ n, & m, here sum of subsets problem is finding all subsets of w i
whose sums are m.

Definition: Given n distinct +ve numbers (usually called weights), desire (want) to find all
combinations of these numbers whose sums are m. this is called sum of subsets problem.

To formulate this problem by using either fixed sized tuples or variable sized tuples.

Backtracking solution uses the fixed size tuple strategy.

Graph Coloring:

Let G be a undirected graph and ‗m‘ be a given +ve integer. The graph coloring problem is
assigning colors to the vertices of an undirected graph with the restriction that no two adjacent
vertices are assigned the same color yet only ‗m‘ colors are used.
The optimization version calls for coloring a graph using the minimum number of coloring.
The decision version, known as K-coloring asks whether a graph is colorable using at most k-
colors.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

53
Hamiltonian Cycles:

 Def: Let G=(V, E) be a connected graph with n vertices. A Hamiltonian cycle is a round
trip path along n-edges of G that visits every vertex once & returns to its starting position.
 It is also called the Hamiltonian circuit.
 Hamiltonian circuit is a graph cycle (i.e., closed loop) through a graph that visits each
node exactly once.
 A graph possessing a Hamiltonian cycle is said to be Hamiltonian graph.
Example:

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

54
Branch & Bound:
Branch & Bound (B & B) is general algorithm (or Systematic method) for finding optimal
solution of various optimization problems, especially in discrete and combinatorial optimization.
 The B&B strategy is very similar to backtracking in that a state space tree is used to solve
a problem.
 The differences are that the B&B method
 Does not limit us to any particular way of traversing the tree.
 It is used only for optimization problem
 It is applicable to a wide variety of discrete combinatorial problem.
 B&B is rather general optimization technique that applies where the greedy method &
dynamic programming fail.
 It is much slower, indeed (truly), it often (rapidly) leads to exponential time complexities
in the worst case.
 The term B&B refers to all state space search methods in which all children of the ―E-
node‖ are generated before any other ―live node‖ can become the ―E-node‖
 Live node is a node that has been generated but whose children have not yet
AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)
55
 been generated.
 E-node is a live node whose children are currently being explored.
 Dead nodeis a generated node that is not to be expanded or explored any
further. All children of a dead node have already been expanded.


 Two graph search strategies, BFS & D-search (DFS) in which the exploration of a new
node cannot begin until the node currently being explored is fully explored.
 Both BFS & D-search (DFS) generalized to B&B strategies.
 BFSlike state space search will be called FIFO (First In First Out) search as the list
of live nodes is ―First-in-first-out‖ list (or queue).
 D-search (DFS)Like state space search will be called LIFO (Last In First Out)
search as the list of live nodes is a ―last-in-first-out‖ list (or stack).
 In backtracking, bounding function are used to help avoid the generation of sub-trees that
do not contain an answer node.
 We will use 3-types of search strategies in branch and bound
1) FIFO (First In First Out) search

2) LIFO (Last In First Out) search

3) LC (Least Count) search

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

56
 7. NP-Hard and NP-Complete problems: (Week 14 )

7.1. Basic concepts

7.2. Non-deterministic algorithms
7.3. NP - Hard
7.4. NP Complete classes
7.5. Cook‘s theorem.
Description:

Objectives:

 Classify problems as tractable or intractable.

 Explain the concepts of P, NP, NP-completeness, and NP-hard.
 Understand the use of reductions to prove NP-completeness.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

57
Deterministic and non-deterministic algorithms

Deterministic: The algorithm in which every operation is uniquely defined is called

deterministic algorithm.

Non-Deterministic: The algorithm in which the operations are not uniquely defined but are
limited to specific set of possibilities for every operation, such an algorithm is called non-
deterministic algorithm.

The non-deterministic algorithms use the following functions:

1. Choice: Arbitrarily chooses one of the element from given set.

2. Failure: Indicates an unsuccessful completion

3. Success: Indicates a successful completion

A non-deterministic algorithm terminates unsuccessfully if and only if there exists no set of

choices leading to a success signal. Whenever, there is a set of choices that leads to a successful
completion, then one such set of choices is selected and the algorithm terminates successfully.

In case the successful completion is not possible, then the complexity is O(1). In case of
successful signal completion then the time required is the minimum number of steps needed to
reach a successful completion of O(n) where n is the number of inputs.

The problems that are solved in polynomial time are called tractable problems and the problems
that require super polynomial time are called non-tractable problems. All deterministic
polynomial time algorithms are tractable and the non-deterministic polynomials are intractable.

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

58
Theory of NP-Completeness:
Show that may of the problems with no polynomial time algorithms are computational time
algorithms are computationally related.
There are two classes of non-polynomial time problems
1. NP-Hard

2. NP-Complete

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

59
NP Complete Problem: A problem that is NP-Complete can solved in polynomial time if and
only if (iff) all other NP-Complete problems can also be solved in polynomial time.

NP-Hard: Problem can be solved in polynomial time then all NP-Complete problems can be
solved in polynomial time.

All NP-Complete problems are NP-Hard but some NP-Hard problems are not known to be NP-
Complete.

The Classes NP-Hard & NP-Complete:

For measuring the complexity of an algorithm, we use the input length as the parameter. For
example, An algorithm A is of polynomial complexity p() such that the computing time of A is
O(p(n)) for every input of size n.

Decision problem/ Decision algorithm: Any problem for which the answer is either zero or one
is decision problem. Any algorithm for a decision problem is termed a decision algorithm.

Optimization problem/ Optimization algorithm: Any problem that involves the identification
of an optimal (either minimum or maximum) value of a given cost function is known as an
optimization problem. An optimization algorithm is used to solve an optimization problem.

P-) is the set of all decision problems solvable by deterministic algorithms in polynomial time.

NP-) is the set of all decision problems solvable by nondeterministic algorithms in polynomial
time.

Since deterministic algorithms are just a special case of nondeterministic, by this we concluded
that P ⊆ NP

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

60
The most famous unsolvable problems in Computer Science is Whether P=NP or P≠NP In
considering this problem, [Link] formulated the following question.

If there any single problem in NP, such that if we showed it to be in ‗P‘ then that would imply
that P=NP.

Cook answered this question with

Theorem: Satisfiability is in P if and only if (iff) P=NP -)Notation of Reducibility

Let L1 and L2 be problems, Problem L1 reduces to L2 (written L1 α L2) iff there is a way to
solve L1 by a deterministic polynomial time algorithm using a deterministic algorithm that
solves L2 in polynomial time

This implies that, if we have a polynomial time algorithm for L2, Then we can solve L1 in
polynomial time.

Here α-) is a transitive relation i.e., L1 α L2 and L2 α L3 then L1 α L3

A problem L is NP-Hard if and only if (iff) satisfiability reduces to L ie., Statisfiability α L A
problem L is NP-Complete if and only if (iff) L is NP-Hard and L Є NP

Most natural problems in NP are either in P or NP-complete.

Examples of NP-complete problems:

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

61
> Packing problems: SET-PACKING, INDEPENDENT-SET.
> Covering problems: SET-COVER, VERTEX-COVER.
> Sequencing problems: HAMILTONIAN-CYCLE, TSP.
> Partitioning problems: 3-COLOR, CLIQUE.
> Constraint satisfaction problems: SAT, 3-SAT.
> Numerical problems: SUBSET-SUM, PARTITION, KNAPSACK.

Cook’s Theorem: States that satisfiability is in P if and only if P=NP If P=NP then satisfiability
is in P
If satisfiability is in P, then P=NP
To do this
> A-) Any polynomial time nondeterministic decision algorithm.
I-)Input of that algorithm
Then formula Q(A, I), Such that Q is satisfiable iff ‗A’ has a successful termination with
Input I.
> If the length of ‗I‘ is ‗n’ and the time complexity of A is p(n) for some polynomial p()
then length of Q is O(p3(n) log n)=O(p4(n))
The time needed to construct Q is also O(p3(n) log n).
> A deterministic algorithm ‗Z’ to determine the outcome of ‗A‘ on any input ‗I‘
Algorithm Z computes ‗Q‘ and then uses a deterministic algorithm for the satisfiability
problem to determine whether ‗Q‘ is satisfiable.

> If O(q(m)) is the time needed to determine whether a formula of length ‗m‘ is
satisfiable then the complexity of ‗Z‘ is O(p3(n) log n + q(p3(n)log n)).
> If satisfiability is ‗p‘, then ‗q(m)‘ is a polynomial function of ‗m‘ and the
complexity of ‗Z‘ becomes ‗O(r(n))’ for some polynomial ‗r()’.

> Hence, if satisfiability is in p, then for every nondeterministic algorithm A in

NP, we can obtain a deterministic Z in p.
By this we shows that satisfiability is in p then P=NP

AKU| Design and Analysis of Algorithm – DAA Excellence through Perseverance!!(AKU)

62