13C- Design and Analysis of Algorithms

Unit II
Divide and Conquer: General Method, Binary Search, Merge sort, Quick sort. Basic traversal
and search techniques: Techniques for Binary trees - Techniques for Graphs.
Divide-and-conquer
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.
This algorithm consists of two parts:
Divide : Divide the problem into a number of sub problems. The sub problems are solved
recursively.
Conquer : The solution to the original problem is then formed from the solutions to the sub
problems (patching together the answers).
ALGORITHM

Algorithm DAndC(P)
{
if Small(P) return S(P);
else {

divide P into smaller instances P1, P2, …, Pk, k1;

Apply DAndC to each of these subproblems;

return Combine(DAndC(P1), DAndC(P2),…, DAndC(Pk));

}
}
SMALL (P) is a Boolean valued function which determines whether the input size is small
enough so that the answer can be computed without splitting.
The computing time of DAndC is

 g ( n)
T ( n)  
T ( n1 )  T ( n2 )  ...  T (nk )  f (n)
– T(n) is the time for Divde_Conquer on any input size n.
– g(n) is the time to compute the answer directly (for small inputs)
– f(n) is the time for dividing P and combining the solutions.

1
Applications of Divide and conquer Algorithm:
 Binary search,
 Quick sort,
 Merge sort,
 Strassen’s matrix multiplication.
Binary Search (simplest application of divide-and-conquer)

1. This algorithm finds the position of a specified input value (the search "key") within an array
sorted by key value.
2. In each step, the algorithm compares the search key value with the key value of the middle
element of the array.
3. If the keys match, then a matching element has been found and its index, or position, is
returned.
4. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats
its action on the sub-array to the left of the middle element or, if the search key is greater, then
the algorithm repeats on sub array to the right of the middle element.
5. If the search element is less than the minimum position element or greater than the maximum
position element then this algorithm returns not found.
Algorithm BINSRCH (a, n, x)

// determine whether „x‟ is present, and if so, set j such that x = a(j) else return j
{
low :=1 ; high :=n ;
while (low < high) do
{
mid :=|(low + high)/2|
if (x < a [mid]) then high:=mid – 1;
else if (x > a [mid]) then low:= mid + 1
else return mid;
}
return 0; }

2
Conditions for when to apply Binary Search in a Data Structure:
 The data structure must be sorted.
 Access to any element of the data structure takes constant time.

Example: Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and target = 23

Analysis

Space Complexity O(1)

3
Time Complexity

Case Time Complexity

Best Case O(1)

Average Case O(logn)

Worst Case O(logn)

Merge Sort
It is one of the most popular and efficient sorting algorithm. It divides the given list into
two equal halves, calls itself for the two halves and then merges the two sorted halves. We have
to define the merge() function to perform the merging.
The sub-lists are divided again and again into halves until the list cannot be divided
further. Then we combine the pair of one element lists into two-element lists, sorting them in the
process. The sorted two-element pairs is merged into the four-element lists, and so on until we
get the sorted list.
Algorithm MergeSort(low, high)

//a(low : high) is a global array to be sorted

if (low < high) then

//Divide P into subproblems

//find where to split the set

mid :=[(low + high)/2];

//Solve the subproblems

MergeSort (low, mid);

MergeSort (mid + 1, high);

// combine the results

MERGE(low, mid, high) ;

} }

4
Example

Time Complexity

Case Time Complexity

Best Case O(n*logn)

Average Case O(n*logn)

Worst Case O(n*logn)

Space Complexity O(n)

5
Quick sort
It is a fast sorting algorithm used to sort a list of elements. Quick sort algorithm is
invented by C. A. R. Hoare.
The quick sort algorithm attempts to separate the list of elements into two parts and then sort
each part recursively. That means it use divide and conquer strategy. In quick sort, the partition
of the list is performed based on the element called pivot. Here pivot element is one of the
elements in the list.
The list is divided into two partitions such that "all elements to the left of pivot are smaller than
the pivot and all elements to the right of pivot are greater than or equal to the pivot".

Step by Step Process

In Quick sort algorithm, partitioning of the list is performed using following steps...
Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in the list).
Step 2 - Define two variables i and j. Set i and j to first and last elements of the list respectively.
Step 3 - Increment i until list[i] > pivot then stop.
Step 4 - Decrement j until list[j] < pivot then stop.
Step 5 - If i < j then exchange list[i] and list[j].
Step 6 - Repeat steps 3,4 & 5 until i > j.
Step 7 - Exchange the pivot element with list[j] element.

6
7
Quick Sort Pseudocode
procedure quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure

Basic traversal and search techniques:

Two categories of techniques:
1.Examining every node in the given object (i.e) Traversal Methods
- Can be applied only to binary trees
2. May not examine all vertices.(i.e) Search methods
- Can be applied for Graphs
Binary Trees
A binary tree is a finite set of nodes that is either empty or consists of a root and two
disjoint binary trees called the left and right subtrees.
Binary Tree Traversal Methods:
Traversing a tree means visiting and outputting the value of each node in a particular order.
Inorder => Left, Root, Right.
Preorder => Root, Left, Right.
Post order => Left, Right, Root.
Preorder Traversal:
The applications of preorder traversal include -
 It is used to create a copy of the tree.
 It can also be used to get the prefix expression of an expression tree.
Algorithm

8
Until all nodes of the tree are not visited
Step 1 - Visit the root node
Step 2 - Traverse the left subtree recursively.
Step 3 - Traverse the right subtree recursively.

So, the output of the preorder traversal of the above tree is - A → B → D → E → C → F → G

Inorder Traversal:
The applications of Inorder traversal includes -
o It is used to get the BST nodes in increasing order.
o It can also be used to get the prefix expression of an expression tree.

Algorithm
Until all nodes of the tree are not visited
Step 1 - Traverse the left subtree recursively.
Step 2 - Visit the root node.
Step 3 - Traverse the right subtree recursively.

9
Output of the inorder traversal of the above tree is - D→B→E→A→F→C→G
Postorder Traversal:
The applications of postorder traversal include -
 It is used to delete the tree.
 It can also be used to get the postfix expression of an expression tree.
Algorithm
Until all nodes of the tree are not visited
Step 1 - Traverse the left subtree recursively.
Step 2 - Traverse the right subtree recursively.
Step 3 - Visit the root node

Output of the postorder traversal of the above tree is D → E → B → F → G → C → A

10
Graph Traversals :
Graph traversal is a technique used for a searching vertex in a graph.
The graph traversal is also used to decide the order of vertices is visited in the search process.
A graph traversal finds the edges to be used in the search process without creating loops.
There are two common ways of traversing a graph:

 Breadth-first search uses a queue to keep track of vertices that still need to be visited.
 Depth-first search uses a stack (can also implement it recursively).

DFS (Depth First Search):

 Step 1 - Define a Stack of size total number of vertices in the graph.

 Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on
to the Stack.
 Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top
of stack and push it on to the stack.
 Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is
at the top of the stack.
 Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex
from the stack.
 Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
 Step 7 - When stack becomes Empty, then produce final spanning tree by removing
unused edges from the graph

Depth first search: Strategy

1. A depth first search of a graph differs from a breadth first search in that the
exploration of a vertex v is suspended as soon as a new vertex is reached.
2. At this time the exploration of the new vertex u begins.
3. When this new vertex has been explored, we continue to explore v.
4. The search terminates when all reached vertices have been fully explored.

11
BFS (Breadth First Search)

BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph
without loops. We use Queue data structure with maximum size of total number of vertices in the
graph to implement BFS traversal.

 Step 1 - Define a Queue of size total number of vertices in the graph.

 Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into
the Queue.
 Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the
Queue and insert them into the Queue.
 Step 4 - When there is no new vertex to be visited from the vertex which is at front of the
Queue then delete that vertex.
 Step 5 - Repeat steps 3 and 4 until queue becomes empty.
 Step 6 - When queue becomes empty, then produce final spanning tree by removing
unused edges from the graph

Breadth-first search: Strategy

1. choose a starting vertex v, which is unexplored
2. Visit all vertices adjacent to v
3. These are new unexplored vertices and now v is explored
4. First vertex in this list is the next to be explored
5. Exploration continues until the queue is empty

******************************************************************************

12