Design and Analysis of Algorithms - DAA

(B Tech CSE – IV Semester – 4 Credits)

Dr. Radha Krishna Reddy P, MSc (CS), MTech (CSE), PhD (ECE),
Asst. Prof. in CSE, Manipal Institute of Technology / MAHE,
Research Collaborator - CISTER Research Center, ISEP, Porto, Portugal,
External Research Collaborator - CEDRIC Labs, CNAM, Paris, France.
[Link]@[Link]
 Syllabus

Module – 3:

• Divide And Conquer:

• Mergesort, Quicksort, Binary Tree Traversals and Related Properties, Multiplication of

Large Integers and Strassen’s Matrix Multiplication.

• Transform And Conquer:

• Presorting, Balanced Search Trees, Heaps and Heapsort, Problem Reduction

• Text Book 1: Chapter 5: 5.1-5.4, Chapter 6: 6.1, 6.3, 6.4, 6.6

DAA
Divide and Conquer – DAndC

• An important general technique for designing algorithms:

• Divide: a problem to be solved is broken into a number of subproblems of the
same form as the original problems;
• Conquer: the subproblems are then solved independently, usually recursively;
• Combine: finally, the solutions to the subproblems are combined to provide the
answer to the original problem.
• Use recurrences to analyze the running time of such algorithms.
DAA
Divide and Conquer

a problem of size n

subproblem 1 subproblem 2
of size n/2 of size n/2

a solution to a solution to
subproblem 1 subproblem 2

a solution to
the original problem
DAA
Divide and Conquer – Examples

• Sorting: merge sort and quicksort

• Binary Tree Traversal
• Multiplication of large integers
• Matrix multiplication: Strassen’s algorithm
• Closest-pair and convex-hull algorithms
• Binary search: decrease-by-half (or degenerate DAC).
DAA
Divide and Conquer – Master Method

The Master Theorem is a tool used to solve recurrence relations that arise in the analysis of
divide-and-conquer algorithms.

The Master Method is used for solving the following types of recurrence
𝑛
𝑇 (𝑛) = 𝑎 𝑇 ( ) + 𝑓 (𝑛)
𝑏
• n is the size of the problem and a is the number of subproblems in the recursion.

• n/b is the size of each subproblem, assuming all subproblems are essentially the same size.

• f (n) is the sum of the work done outside the recursive calls, which includes the sum of
dividing the problem and the sum of combining the solutions to the subproblems.
DAA
Divide and Conquer – Master Method

It is not possible always bound the function according to the requirement, so we make three
cases which will tell us what kind of bound we can apply on the function.
DAA
Divide and Conquer – Master Method

The master method is mainly derived from the recurrence tree method. If we draw the
recurrence tree of T(n) = aT(n/b) + f(n), we can see the root is f(n), and at all leaves is Θ(nc)
where c is 𝒍𝒐𝒈𝒃 𝒂. And the height of the recurrence tree is 𝒍𝒐𝒈𝒃 𝒏.
DAA
Divide and Conquer – Master Method

𝑙𝑜𝑔𝑏𝑎−𝜀 𝑙𝑜𝑔𝑏𝑎
Case1: If 𝑓(𝑛) = 𝑂(𝑛 ) for some constant ε >0, then it follows that 𝑇(𝑛) = Θ (𝑛 )

𝑛
Example: 𝑇 𝑛 = 8 𝑇 + 1000𝑛2 apply master theorem on it.
2

𝑛 𝑛
Solution: Compare 𝑇 𝑛 = 8 𝑇 + 1000𝑛2 with 𝑇 (𝑛) = 𝑎 𝑇 ( ) + 𝑓 (𝑛) a>= 1 and b>1
2 𝑏

𝑎 = 8, 𝑏 = 2, 𝑓 (𝑛) = 1000 𝑛2, 𝑙𝑜𝑔𝑏𝑎 = log28 = 3

𝑎−𝜀
𝑙𝑜𝑔
Put all the values in: 𝑓(𝑛) = 𝑂(𝑛 𝑏 )

1000 𝑛2 = 𝑂 (𝑛3−𝜀 )

If we choose ε=1, we get: 1000 𝑛2 = 𝑂 (𝑛3−1 ) = 𝑂 (𝑛2)

DAA
Divide and Conquer – Master Method

Since this equation holds, the first case of the master theorem applies to the given recurrence
𝑙𝑜𝑔𝑏𝑎
relation, thus resulting in the conclusion: 𝑇(𝑛) = Θ (𝑛 )

Therefore: 𝑇 (𝑛) = Θ (𝑛3)

Case 2: If it is true, for some constant k ≥ 0 that:

𝑎 𝑎
𝑙𝑜𝑔
F (n) = Θ (𝑛 𝑏 𝑙𝑜𝑔𝑛𝑘 ) then it follows that: T (n) = Θ (𝑛 𝑙𝑜𝑔𝑏 𝑙𝑜𝑔𝑛𝑘+1 )

𝑛
Example: T n = 2𝑇 + 10𝑛 , solve the recurrence by using the master method.
2
DAA
Divide and Conquer – Master Method

𝑛
Solution: As compare the given problem with 𝑇 (𝑛) = 𝑎 𝑇 ( ) + 𝑓 (𝑛) a>= 1 and b>1
𝑏

𝑎 = 2, 𝑏 = 2, 𝑘 = 0, 𝑓 (𝑛) = 10𝑛, 𝑙𝑜𝑔𝑏𝑎 = log22 = 1

𝑎
𝑙𝑜𝑔
Put all the values in f (n) = Θ (𝑛 𝑏 𝑙𝑜𝑔𝑛𝑘+1 ),

we will get 10𝑛 = Θ (𝑛1) = Θ (𝑛) which is true.

𝑎
Therefore: T (n) = Θ (𝑛 𝑙𝑜𝑔𝑏 𝑙𝑜𝑔𝑛𝑘+1 )

= Θ (n log n)
DAA
Divide and Conquer – Master Method

𝑎+ ε
Case 3: If it is true 𝑓(𝑛) = Ω (𝑛𝑙𝑜𝑔𝑏 ) for some constant ε >0 and it also true that:
𝑛
𝑎 𝑓( ) ≤ 𝑐𝑓(𝑛) for some constant c<1 for large value of n ,then : 𝑇 (𝑛) = Θ((𝑓 (𝑛))
𝑏

𝑛
Example: Solve the recurrence relation: 𝑇 𝑛 = 2𝑇 + 𝑛2
2

𝑛
Solution: Compare the given problem with 𝑇 (𝑛) = 𝑎 𝑇 ( ) + 𝑓 (𝑛) a>= 1 and b>1
𝑏

𝑎 = 2, 𝑏 = 2, 𝑓 (𝑛) = 𝑛2, 𝑙𝑜𝑔𝑏𝑎 = log22 = 1

DAA
Divide and Conquer – Master Method
𝑎+ε
Put all the values in f n = Ω (𝑛 𝑙𝑜𝑔𝑏 ) .

If we insert all the value in the above equation, we will get

+𝜀
𝑛2 = Ω(𝑛1 ) 𝑝𝑢𝑡 𝜀 = 1, then the equality will hold.
+1
𝑛2 = Ω(𝑛1 ) = Ω(𝑛2)

𝑛 𝑛2
Now we will also check the second condition: 2( )2 ≤ 𝑐𝑛2 ⇒ ≤ 𝑐𝑛2
2 2

𝑛2 𝑛2
If we will choose c =1/2, it is true: ≤ ∀ n ≥1
2 2

So it follows: 𝑇 (𝑛) = Θ ((𝑓 (𝑛))

𝑇 (𝑛) = Θ(𝑛2)
DAA
Divide and Conquer – Master Method

T(n) = a T(n/b) + f (n) where f(n)  (nd), d  0

Master Theorem: If a < bd, T(n)  (nd)

If a = bd, T(n)  (nd log n)

If a > bd, T(n)  (nlog b a )

Examples: T(n) = 4T(n/2) + n  T(n)  ? (n2)

T(n) = 4T(n/2) + n2  T(n)  ? (n2log n)

T(n) = 4T(n/2) + n3  T(n)  ? (n3)

DAA
Divide and Conquer – Merge Sort
• Split array A[0..n-1] into two about equal halves and make copies of each half in
arrays B and C.
• Sort arrays B and C recursively.
• Merge, sorted arrays B and C into array A as follows:
• Repeat the following until no elements remain in one of the arrays:
• compare the first elements in the remaining unprocessed portions of the
arrays
• copy the smaller of the two into A, while incrementing the index indicating the
unprocessed portion of that array
• Once all elements in one of the arrays are processed, copy the remaining
unprocessed elements from the other array into A.
DAA
Divide and Conquer – Merge Sort
DAA
Divide and Conquer – Merge Sort

Time complexity: Θ(p+q) = Θ(n) comparisons

DAA
Divide and Conquer – Merge Sort
8 3 2 9 7 1 5 4

8 3 2 9 7 1 5 4

8 3 2 9 71 5 4

8 3 2 9 7 1 5 4

3 8 2 9 1 7 4 5

2 3 8 9 1 4 5 7 85196247

1 2 3 4 5 7 8 9 Homework
DAA
Divide and Conquer – Merge Sort

• All cases have same efficiency: Θ(n log n)

T(n) = 2T(n/2) + Θ(n), T(1) = 0
• Number of comparisons in the worst case is close to theoretical minimum for
comparison-based sorting:
log2 n! ≈ n log2 n - 1.44n

• Space requirement: Θ(n) (not in-place)

• Can be implemented without recursion (bottom-up)

DAA
Divide and Conquer – Quick Sort

• Select a pivot (partitioning element) – here, the first element

• Rearrange the list so that
• all the elements in the first s positions are smaller than or equal to the pivot and
• all the elements in the remaining n-s positions are larger than or equal to the pivot
• Exchange the pivot with the last element in the first subarray (i.e., ) — the pivot is
now in its final position
• Sort the two subarrays recursively

A[i]p A[i]p
DAA
Divide and Conquer – Quick Sort
DAA
Divide and Conquer – Quick Sort
DAA
Divide and Conquer – Quick Sort
DAA
Divide and Conquer – Quick Sort – Example

We are given array of n integers to sort: 40 20 10 80 60 50 7 30 100

There are various ways of picking the

pivot element. In this example, we
will use the first element in the 40 20 10 80 60 50 7 30 100
array:
DAA
Divide and Conquer – Quick Sort – Example

Given a pivot, partition the elements of the array that the resulting array consists of:
1. One sub-array that contains elements >= pivot
2. Another sub-array that contains elements < pivot
• The sub-arrays are stored in the original data array.
• Partitioning through loops, swapping elements below/above pivot.
DAA
Divide and Conquer – Quick Sort – Example

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j
DAA
Divide and Conquer – Quick Sort – Example

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j
DAA
Divide and Conquer – Quick Sort – Example

pivot_index = 0 40 20 10 80 60 50 7 30 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j
DAA
Divide and Conquer – Quick Sort – Example

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j
DAA
Divide and Conquer – Quick Sort – Example

pivot_index = 0 40 20 10 30 60 50 7 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j
DAA
Divide and Conquer – Quick Sort – Example

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j
DAA
Divide and Conquer – Quick Sort – Example

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

pivot_index = 0 40 20 10 30 7 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j
DAA
Divide and Conquer – Quick Sort – Example

pivot_index = 4 7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

i j

7 20 10 30 40 50 60 80 100

[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]

DAA
Divide and Conquer – Quick Sort – Example

Homework
5 3 1 9 8 2 4 7

l = left index
r = right index
s = split position
DAA
Divide and Conquer – Quick Sort – Example
DAA
Divide and Conquer – Quick Sort

• Best case: split in the middle — C best(n)= 2Cbest(n/2) + n for n>1

• Worst case: sorted array! —
Cworst (n) = (n+1) + n + (n-1) + (n-2) + ……. + 3
= (n + 1)(n+2) - 3
2
• Average case: random arrays — Θ(n log n)
• Improvements:
• better pivot selection: median of three partitioning
• switch to insertion sort on small subfiles
• elimination of recursion
Apply quicksort to sort the list E, X, A,M, P, L, E in
These combine to 20-25% improvement alphabetical order. Draw the tree of the recursive
calls made.
DAA
Divide and Conquer – Binary Tree

Node / Vertex
A Root

B C
Left subtree
Right subtree
D E F G

Edges H I Leaves

J K L M N
DAA
Divide and Conquer – Binary Trees

• A binary tree T is a tree with finite set of nodes that is either empty
• or consists of a root and two disjoint binary trees (the left and right subtrees of
the root).
• A binary tree as a special case of an ordered tree.
T
• Since a binary tree is divided into
• the left subtree and the right subtree,
• many binary trees can be solved by applying DandC..
DAA
Divide and Conquer – Binary Tree

• Binary tree: Each node has at most 2 children (branching factor 2)

• Binary tree is
• A root (with data)
• A left subtree (may be empty)
• A right subtree (may be empty)

• Special Cases:
DAA
Divide and Conquer – Binary Tree

Recall: height of a tree = longest path from root to leaf (count edges)
DAA
Divide and Conquer – Binary Tree

For binary tree of height h:

• max # of leaves:
• max # of nodes:

• min # of leaves:
• min # of nodes:

For n nodes, the min height (best-case) is

the max height (worst-case) is
DAA
Divide and Conquer – Binary Tree

Internal node

External node

Binary Tree Extended Binary Tree

DAA
Divide and Conquer – Binary Tree

• The most important divide-and-conquer algorithms for binary trees are

• Preorder traversal - the root is visited before the left and right subtrees are visited
(in that order) .
• Inorder traversal - the root is visited after visiting its left subtree but before
visiting the right subtree, and
• Postorder traversal - the root is visited after visiting the left and right subtrees (in
that order).
• All three traversals visit nodes of a binary tree recursively, i.e., by visiting the tree’s
root and its left and right subtrees.
• They differ only when they visit the root node.
DAA
Divide and Conquer – Binary Tree
DAA
Divide and Conquer – Binary Tree

Homework for traversal

DAA
Divide and Conquer – Multiplication of Large Integers

• Modern cryptography, require manipulation of integers that are over 100 decimal
digits long.
• Such integers are too long to fit in a single word of a modern computer, they require
special treatment.
• Need for efficient manipulation of large integers.
• If we use the conventional pen-and-pencil algorithm for multiplying two n-digit
integers, we need a total of n2 digit multiplications.
• Divide-and-conquer can rescue us with fewer than n2 multiplications.
DAA
Divide and Conquer – Multiplication of Large Integers

• Example: two-digit integers

• 23 and 14
• 23 = 2 ∙ 101 + 3 ∙ 100 and 14 = 1 ∙ 101 + 4 ∙ 100
• Multiply 23 and 14,
• 23 ∗ 14 = 2 ∙ 101 + 3 ∙ 100 ∗ 1 ∙ 101 + 4 ∙ 100
= 2 ∗ 1 102 + 2 ∗ 4 + 3 ∗ 1 101 + (3 ∗ 4)100
• 2 ∗ 4 + 3 ∗ 1 = (2 + 3) ∗ (1 + 4) − 2 ∗ 1 − 3 ∗ 4.
DAA
Divide and Conquer – Multiplication of Large Integers

For n-digit integers it will be 𝑐 = 𝑐2 10𝑛 + 𝑐1 10𝑛/2 + 𝑐0

DAA
Divide and Conquer – Multiplication of Large Integers

• Consider the problem of multiplying two (large) n-digit integers represented by arrays
of their digits such as: A = 12345678901357986429 B = 87654321284820912836
• The grade-school algorithm:
• a1 a2 … an
b1 b2 … bn
(d10) d11d12 … d1n
• (d20) d21d22 … d2n
• …………………
• (dn0) dn1dn2 … dnn
• Efficiency: ?? one-digit multiplications n2
DAA
Divide and Conquer – Multiplication of Large Integers
A small example: A  B where A = 2135 and B = 4014
A = (21·102 + 35), B = (40 ·102 + 14)
So, A  B = (21 ·102 + 35)  (40 ·102 + 14) = 21  40 ·104 + (21  14 + 35  40) ·102 + 35  14

In general, if A = A1A2 and B = B1B2 (where A and B are n-digit, and A1, A2, B1, B2 are n / 2-
digit numbers),
A  B = A1  B1·10n + (A1  B2 + A2  B1) ·10n/2 + A2  B2

Recurrence for the number of one-digit multiplications M(n): M(n) = 4M(n/2), M(1) = 1

Solution: M(n) = n2
DAA
Divide and Conquer – Multiplication of Large Integers

• A  B = A1  B1·10n + (A1  B2 + A2  B1) ·10n/2 + A2  B2

• The idea is to decrease the number of multiplications from 4 to 3:

(A1 + A2 )  (B1 + B2 ) = A1  B1 + (A1  B2 + A2  B1) + A2  B2,

I.e., (A1  B2 + A2  B1) = (A1 + A2 )  (B1 + B2 ) - A1  B1 - A2  B2,

• which requires only 3 multiplications at the expense of (4-1=3) extra additions and
subtractions (2 adds and 2 subs – 1 add)
• Recurrence for the number of multiplications M(n): M(n) = 3M(n/2), M(1) = 1
• Solution: M(n) = 3log2n = nlog 23 ≈ n1.585
DAA
Divide and Conquer – Strassen’s Matrix Multiplication

• Consider two n by n matrices A and B

• Definition of AxB is n by n matrix C whose (i,j)-th entry is computed like this:
• consider row i of A and column j of B
• multiply together the first entries of the row and column, the second entries, etc.
• then add up all the products
• Number of scalar operations (multiplies and adds) in straightforward algorithm is O(n3).
• Can we do it faster?
DAA
Divide and Conquer – Strassen’s Matrix Multiplication

Strassen observed [1969] that the product of two matrices can be computed as
follows:

C00 C01 A00 A01 B00 B01

= *
C10 C11 A10 A11 B10 B11

M1 + M4 - M5 + M7 M3 + M5
=
M2 + M4 M1 + M3 - M2 + M6
DAA
Divide and Conquer – Strassen’s Matrix Multiplication

M1 = (A00 + A11)  (B00 + B11)

M2 = (A10 + A11)  B00

M3 = A00  (B01 - B11)

M4 = A11  (B10 - B00)

M5 = (A00 + A01)  B11

M6 = (A10 - A00)  (B00 + B01)

M7 = (A01 - A11)  (B10 + B11)

DAA
Divide and Conquer – Strassen’s Matrix Multiplication

If n is not a power of 2, matrices can be padded with zeros.

Number of multiplications: Recurrence for new algorithm is T(n) = 7T(n/2) + (n2)
Applying the Master Theorem to 𝑇(𝑛) = 𝑎 𝑇(𝑛/𝑏) + 𝑓(𝑛)
with 𝑎 = 7, 𝑏 = 2, 𝑎𝑛𝑑 𝑓(𝑛) = (𝑛2).
𝑎−𝜀 7−𝜀
𝑆𝑖𝑛𝑐𝑒 𝑓(𝑛) = 𝑙𝑜𝑔
𝑂(𝑛 𝑏 ) = 𝑂(𝑛𝑙𝑜𝑔2 ),
case a) applies and we get
𝑎
𝑇 𝑛 =  𝑛 𝑙𝑜𝑔𝑏

7 .
= (𝑛 𝑙𝑜𝑔2 ) = 𝑂(𝑛2 807).
DAA
Divide and Conquer – Strassen’s Matrix Multiplication

• Not always practical

• constant factor is larger than for naïve method
• specially designed methods are better on sparse matrices
• issues of numerical (in)stability
• recursion uses lots of space
• Not the fastest known method
• Fastest known is O(n2.376)
• Best known lower bound is (n2)
DAA
Divide and Conquer – Strassen’s Matrix Multiplication

12 34 3 4
𝐴= 𝐵=
22 10 2 1
 Syllabus

Module – 3:

• Divide And Conquer:

• Mergesort, Quicksort, Binary Tree Traversals and Related Properties, Multiplication of

Large Integers and Strassen’s Matrix Multiplication.

• Transform And Conquer:

• Presorting, Balanced Search Trees, Heaps and Heapsort, Problem Reduction

• Text Book 1: Chapter 5: 5.1-5.4, Chapter 6: 6.1, 6.3, 6.4, 6.6

DAA
Transform and Conquer

This group of techniques solves a problem by transformation.

• Transformed into:
• a simpler/more convenient instance [e.g. sorted] of the same problem - instance
simplification
• a different representation of the same instance [eg different data structure] -
representation change
• a different problem for which an algorithm is already available - problem reduction
• Solve the problem in the Conquering stage.
DAA
Transform and Conquer Presorting

Computing Least Common Multiple Heapsort

Counting paths in a graph Horners rule
Reducing to Optimization problems Binary Exponentiation
Reducing to Graph problems
DAA
Transform and Conquer - Presorting
• Solve a problem’s instance by transforming it into another simpler/easier instance of
the same problem
Presorting: Many problems involving lists are easier when list is sorted,
• searching
• computing the median (selection problem)
• checking if all elements are distinct (element uniqueness)
• Also:
• Topological sorting helps solving some problems for DAGs.
• Presorting is used in many geometric algorithms.
DAA
Transform and Conquer - Presorting

• Efficiency of algorithms involving sorting depends on efficiency of sorting.

• Theorem (see Sec. 11.2): log2 n!  n log2 n comparisons are necessary in the worst
case to sort a list of size n by any comparison-based algorithm.

• Note: About nlog2 n comparisons are also sufficient to sort array of size n (by
mergesort).
DAA
Transform and Conquer - Presorting

Problem: Search for a given K in A[0..n-1]

• Presorting-based algorithm:
• Stage 1 Sort the array by an efficient sorting algorithm
• Stage 2 Apply binary search
• Efficiency: Θ(nlog n) + O(log n) = Θ(nlog n)
• Good or bad?
• Why do we have our dictionaries, telephone directories, etc. sorted?
DAA
Transform and Conquer - Presorting
Checking element uniqueness in an array
• The brute-force algorithm compares pairs of the array’s elements until either two
equal elements were found or no more pairs were left.
• Efficiency: O(n2)
DAA
Transform and Conquer - Presorting

• Presorting-based algorithm
• Stage 1: sort by efficient sorting algorithm (e.g. mergesort)
• Stage 2: scan array to check pairs of adjacent elements
• Efficiency: Θ(nlog n) + O(n) = Θ(nlog n)

• Another 2 algorithms:
• Hashing – frequently useful
• Closest pair
DAA
Transform and Conquer - Presorting

Computing a mode
• A mode is a value that occurs most often in a given list of numbers.
• For example, for 5, 1, 5, 7, 6, 5, 7, the mode is 5.
• The brute-force approach
• Scan the list
• Compute the frequencies of all its distinct values (n),
• then find the value with the largest frequency (n-1)

• Complexity - Θ(𝑛2 )
 DAA
Transform and Conquer - Presorting

T (n) = Tsort(n) + Tsearch(n)

= Θ(n log n) + Θ(log n)
= Θ(n log n),
DAA
Transform and Conquer – Balanced Search Trees

Problem: Given a (multi)set S of keys and a search key K, find an occurrence of K in S, if

any
• Searching must be considered in the context of [context determines best data
structure]:
• file size (internal vs. external)
• dynamics of data (static vs. dynamic)
• Dictionary operations (dynamic data) [data structure determines performance]:
• find (search)
• insert
• delete
DAA
Transform and Conquer – Balanced Search Trees

Taxonomy List searching:

• List searching … • sequential search
• Tree searching … • binary search
• Hashing … • interpolation search

Hashing
• open hashing (separate chaining)
• closed hashing (open addressing)
DAA
Transform and Conquer – Balanced Search Trees

• Tree searching
• binary search tree
• balanced binary trees:
• AVL trees
• red-black trees
• multiway trees [balanced]:
• 2-3 trees
• 2-3-4 trees, B trees
DAA
Transform and Conquer – Binary Search Trees

Arrange keys in a binary tree with the binary search tree property:

<K >K

Example: 5, 3, 1, 10, 12, 7, 9

(Which could/should be the root? Best/Worst case?)
DAA
Transform and Conquer – Binary Search Trees – Dictionary Operations
• Searching – straightforward
• Insertion – search for key, insert at leaf where search terminated
• Deletion – 3 cases:
• deleting key at a leaf
• deleting key at node with single child
• deleting key at node with two children
• Efficiency depends on the tree’s height: log2 n  h  n-1, with average height
(random files) be about 3log2 n
• Maximum number of nodes if height k?
• Thus, all three operations have worst case efficiency: (n) and average case
efficiency: (log n)
• Bonus: inorder traversal produces sorted list
DAA
Transform and Conquer – Balanced Search Trees

Attractiveness of BST is marred by the bad (linear) worst-case efficiency. Two ideas to
overcome it (ie keep BST close to balanced) are:
• To restructure BST to maintain balance when an insertion makes the tree “too
unbalanced”
• AVL trees
• red-black trees
• To allow more than one key per node of a search tree
• 2-3 trees
• 2-3-4 trees
• B-trees
DAA
Transform and Conquer – Balanced Trees – AVL Trees

• Definition - An AVL tree is a BST in which, for every node, the difference between the
heights of its left and right subtrees, called the balance factor, is at most 1
• With the height of an empty tree defined as -1.
1 2

10 10
0 1 0 0
5 20 5 20

1 -1 0 1 -1

4 7 12 4 7

0 0 0 0

2 8 2 8

(a) (b)
Tree (a) is an AVL tree; tree (b) is not an AVL tree
 DAA
Transform and Conquer – Balanced Trees – AVL Trees - Rotations
• If a key insertion violates the balance requirement at some node,
• the subtree rooted at that node is transformed via one of the four rotations.
• The rotation is always performed for a subtree rooted at an “unbalanced” node closest
to the new leaf.
2 R
0
3
>
2
A rotation in an AVL tree is a local 1
0 0
transformation of its subtree rooted 2 1 3
at a node whose balance has
become either +2 or −2. 0
1

(a)
Single R-rotation
 DAA
Transform and Conquer – Balanced Trees – AVL Trees - Rotations

-2 1 > 0
2

2 0 0
-1
1 3

3
0

(b)
Single L-rotation
 DAA
Transform and Conquer – Balanced Trees – AVL Trees - Rotations

LR
2 >
3 0
2
-1
1 0 0
1 3

0
2

(c)
Double LR-rotation
 DAA
Transform and Conquer – Balanced Trees – AVL Trees - Rotations

RL
-2 >
1 0
2
1
3
0 0
1 3
0
2

(d)
Double RL-rotation
DAA
Transform and Conquer – Balanced Trees – AVL Trees - Rotations
DAA
Transform and Conquer – Balanced Trees – AVL Trees - Rotations
DAA
Transform and Conquer – Balanced Trees – AVL Trees

Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7

0 -1 -2
0
5 5 5 L(5) 6
0 -1
6 6
> 0 0
5 8

0
8
DAA
Transform and Conquer – Balanced Trees – AVL Trees
Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7
1 2 1
6 6 6
1 0 2 0 0 0
R (5)
5 8 5 8 > 3 8

0 1 0 0
3 3 2 5

0
2

2 0
6 5
-1 0 0 -1
LR (6)
3 3
8
> 6

0 1 0 0 0
2 5 2 4 8

0
4
DAA
Transform and Conquer – Balanced Trees – AVL Trees
Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7
-1 0

5 5

0 0 0
-2
3 RL (6) 3 7
6

0 0
> 0 0 0 0
1
2 4 2 4 6 8
8

0
7

• Homework - Construct an AVL tree by inserting 1 to 8 numbers.

DAA
Transform and Conquer – Balanced Trees – AVL Trees

• log2 n  h  1.4404 log2 (n + 2) - 1.3277

• average height: 1.01 log2n + 0.1 for large n (found empirically)
• Search and insertion are O(log n)

• Deletion is more complicated but is also O(log n)

• Disadvantages:
• frequent rotations
• complexity
• A similar idea: red-black trees (height of subtrees is allowed to differ by up to a factor
of 2)
DAA
Transform and Conquer – Balanced Trees – 2-3 Trees

Definition - A 2-3 tree is a search tree that

• may have 2-nodes and 3-nodes (How many keys per node?)
• height-balanced (all leaves are on the same level !! )
• A 2-3 tree is constructed by successive insertions of given keys,
• with a new key always inserted into a leaf of the tree.
• If the leaf is a 3-node, split it into two with the middle key promoted to the parent.
• Splitting can be repeated up the tree, as needed.
DAA
Transform and Conquer – Balanced Trees – 2-3 Trees
DAA
Transform and Conquer – Balanced Trees – 2-3 Trees

• Definition A multiway search tree is a search tree that allows more than one key in
tree nodes.
• Definition A node of a search tree is called an n-node if it contains n-1 ordered keys.
• Note: Every node in a classical binary search tree is a 2-node

k1 < k2 < … < kn-1

< k1 [k1, k2 )  kn-1

DAA
Transform and Conquer – Balanced Trees – 2-3 Trees
Construct a 2-3 tree the list 9, 5, 8, 3, 2, 4, 7
8 8
>
9 5, 9 5, 8, 9 > 5 9 3, 5 9

8 3, 8 3, 8

2, 3, 5 9
> >
2 5 9 2 4, 5 9
DAA
Transform and Conquer – Balanced Trees – 2-3 Trees

Construct a 2-3 tree the list 9, 5, 8, 3, 2, 4, 7

5
3, 8 3, 5, 8
> > 3 8
2 4, 5, 7 9 2 4 7 9
2 4 7 9

for any 2-3 tree of height h with n nodes, we get the inequality
n ≥ 1+ 2 + . . . + 2h = 2h+1 − 1,
and hence
h ≤ log2(n + 1) − 1.
DAA
Transform and Conquer – Balanced Trees – 2-3 Trees

• What happens when a 2-3 tree of height h with the largest number of keys
• Is a full tree of 3-nodes, each with two keys and three children.

For any 2-3 tree with n nodes,

n ≤ 2 . 1+ 2 . 3 + . . . + 2 . 3h = 2(1+ 3 + . . . + 3h) = 3h+1 − 1
Hence, h ≥log3 (n + 1) - 1
DAA
Transform and Conquer – Balanced Trees – 2-3 Trees

• log3 (n + 1) - 1  h  log2 (n + 1) - 1
• Lower and Upper bounds on height h.
• Search, insertion, and deletion are in (log n)
• The idea of 2-3 tree can be generalized by allowing more keys per node
• 2-3-4 trees
• B-trees

Construct a 2-3 tree for the list C,O, M, P,U, T, I,N,G.

Use the alphabetical order of the letters and insert them successively starting with the
empty tree.
DAA
Transform and Conquer – Balanced Trees – 2-3 Trees

Construct a 2-3 tree for the list C,O, M, P,U, T, I,N,G.

Use the alphabetical order of the letters and insert them successively starting with the
empty tree.
DAA
Transform and Conquer – Balanced Trees – 2-3 Trees

Construct a 2-3 tree for the list C,O, M, P,U, T, I,N,G.

Use the alphabetical order of the letters and insert them successively starting with the
empty tree.
DAA
Transform and Conquer – Heaps and Heapsort

• A heap is partially ordered data structure that is especially suitable for implementing
priority queues.
• A priority queue is a multiset of items with an orderable characteristic called an item’s
priority.
• Supporting the following operations:
• finding an item with the highest (i.e., largest) priority
• deleting an item with the highest priority
• adding a new item to the multiset
DAA
Transform and Conquer – Heaps and Heapsort

A heap is a binary tree with keys assigned to its nodes, one key per node, such that they
met:
• The shape property—the binary tree is essentially complete (or simply complete),
i.e., all its levels are full except possibly the last level, where only some rightmost
leaves may be missing.
• The parental dominance or heap property—the key in each node is ≥ the keys in its
children.
DAA
Transform and Conquer – Heaps and Heapsort

Not a heap not a heap a heap

First one is not a heap, because the parental dominance fails for the node with key 5.
Second one is not a heap, because the tree’s shape property is violated.
DAA
Transform and Conquer – Heaps and Heapsort - Properties

• Given n, there exists a unique binary tree (structure) with n nodes that is essentially
complete, with h = log2 n
• The root contains the largest key
• Every subtree rooted at every node of a heap is also a heap
• A heap can easily be represented as an array recording the elements in a top-down
and left-to-right fashion.
• The parental node keys will be in the first n/2 positions of the array, while the leaf
keys will occupy the last n/2 positions;
• The children of a key in the array’s parental position i (1≤ i ≤ n/2) will be in
positions 2i and 2i + 1 and the parent of a key in position i (2 ≤ i ≤ n) will be in
position i/2.
DAA
Transform and Conquer – Heaps and Heapsort - Properties
Store heap’s elements in an array (whose elements indexed, for convenience, 1 to n) in
top-down left-to-right order
Example:
• Left child of node j is at 2j
• Right child of node j is at 2j+1
• Parent of node j is at j/2
• Parental (ie interior) nodes are in the first n/2 locations

9 1 2 3 4 5 6
5 3 9 5 3 1 4 2

1 4 2
DAA
Transform and Conquer – Heaps and Heapsort – Construction (bottom-up)

Step 0: Initialize data structure (ie array) with keys in the given order

Step 1: Starting with the last (rightmost) parental (ie interior) node, fix the heap rooted
at it, if it doesn’t satisfy the heap condition: keep exchanging it with its largest
child until the heap condition holds

(Called the Heapify)

Step 2: Repeat Step 1 for the preceding parental node

Bottom up: Adding nodes to heap from bottom to top, pushing elements down, as
needed
DAA
Transform and Conquer – Heaps and Heapsort – Construction (bottom-up)
DAA
Transform and Conquer – Heaps and Heapsort – Construction (bottom-up)

Construct a heap for the list 2, 9, 7, 6, 5, 8 . Insert elements into the array. Process interior
nodes R to L. Why? Before and after each step? Heapify all the way down at each step.
Bottom up?
DAA
Transform and Conquer – Heaps and Heapsort – Construction (bottom-up)

Construct a heap for the list 2, 9, 7, 6, 5, 8 . Insert elements into the array. Process interior
nodes R to L. Why? Before and after each step? Heapify all the way down at each step.
Bottom up?
DAA
Transform and Conquer – Heaps and Heapsort – Construction (bottom-up)

Construct a heap for the list 2, 9, 7, 6, 5, 8 . Insert elements into the array. Process interior
nodes R to L. Why? Before and after each step? Heapify all the way down at each step.
Bottom up?
DAA
Transform and Conquer – Heaps and Heapsort – Construction (top-down)
• Basic operation in building heap in Top-Down order
• Insert the new element at last position in heap (size++)
• Compare new element with its parent and, if it violates heap condition, exchange them
• Continue comparing the new element with nodes up the tree until the heap condition
is satisfied
Example: Insert key 10 into heap of size 6
What order is this? Efficiency: O(log n)

9 9 10

6 8 > 6 10 > 6 9

2 5 7 10 2 5 7 8 2 5 7 8
DAA
Transform and Conquer – Heaps and Heapsort – Construction (top-down)
Deleting a root/maximum key from the heap

Step 1 Exchange the root’s key with the last key K of the heap.
Step 2 Decrease the heap’s size by 1.
Step 3 “Heapify” the smaller tree by sifting K down the tree exactly in the same way we
did it in the bottom-up heap construction algorithm.
• Verify the parental dominance for K: if it holds, we are done;
• if not, swap K with the larger of its children and repeat this operation until the
parental dominance condition holds for K in its new position.
• What order is this? Efficiency: O(log n)
DAA
Transform and Conquer – Heaps and Heapsort – Construction (top-down)
• Deleting a root/maximum key from the heap

8 6

2 5 1
DAA
Transform and Conquer – Heaps and Heapsort – Construction (top-down)
Construct a heap for the list 2, 9, 7, 6, 5, 8 [Start with elements in the array]. Process
interior nodes from L to R. Add nodes from top to bottom. Add each node, and push up
as needed.
2
29
9/ 2
9/ 6 7/ 2 5;
9/ 2 7
9/ 6 7/ 2 5, 8;
9/ 2 7/ 6
9/ 6 8/ 2 5, 7
9/ 6 7/ 2;
Is this a heap??
DAA
Transform and Conquer – Heapsort

Stage 1: Construct a heap for a given list of n keys

Stage 2: Repeat operation of root removal n-1 times:
• Exchange keys in the root and in the last (rightmost) leaf
• Decrease heap size by 1
• If necessary, repeatedly swap new root (node) with larger child until
the heap condition again holds
DAA
Transform and Conquer – Heapsort
Sort the list 2, 9, 7, 6, 5, 8 by heapsort

Stage 1 (heap construction) Stage 2 (root/max removal)

2 9 7 6 5 8 9 6 8 2 5 7
2 9 8 6 5 7 7 6 8 2 5|9
8 6 7 2 5
2 9 8 6 5 7
5 6 7 2|8
9 2 8 6 5 7
7 6 5 2
9 6 8 2 5 7
2 6 5|7
6 2 5
5 2|6
5 2
2
DAA
Transform and Conquer – Heapsort

Stage 1: Build heap for a given list of n keys (of height h) worst-case

C(n) = σℎ−1
𝑖=0 2 ℎ − 𝑖 2 𝑖
= 2(𝑛 − 𝑙𝑜𝑔2 𝑛 + 1 )𝜖(n)

Stage 2: Repeat operation of root removal n-1 times (fix heap) worst-case

𝑖=0 2𝑙𝑜𝑔2 𝑖 𝜖 (n log n)

C(n) = σ𝑛−1

Both worst-case and average-case efficiency: (nlogn)

DAA
Transform and Conquer – Problem Reduction
• This solves a problem by a transforming it into different problem for which an
algorithm is already available.
• Reduce P to Q and use a solution of Q as part of a solution to P
• To solve P, first solve Q then use solution to Q in solution to P
• OR To solve P, write an algorithm that calls Q
• To be of practical value, the combined time of the transformation and solving the
other problem should be smaller than solving the problem as given by another
method [eg by brute force].
• VERY IMPORTANT FOR P=NP (Last topic in course)
DAA
Transform and Conquer – Problem Reduction

• Computing lcm(m, n) via computing gcd(m, n)!

• Let’s examine LCM – least common multiple.
• Lcm(24, 60) = 120 24 = 2 * 2 * 2 * 3
• Lcm(11, 5) = 55. 60 = 2 * 2 * 3 * 5
Lcm(24, 60) = (2 * 2 * 3) * 2 * 5
DAA
Transform and Conquer – Problem Reduction

• Reduce P to Q = use a solution of Q as part of a solution to P

• To solve P, first solve Q then use solution to Q in solution to P
• OR equivalently: To solve P, write an algorithm that calls Q
• P = LCM, Q = GCD, thus, Reduce P to Q: Reduce LCM to GCD
• LCM(m, n) = (m * n) / GCD(m, n)
• LCM(60, 42) = (60*42) / GCD(60, 42) = 2520 / 6 = 420
• 60=2*2*3*5. 42=2*3*7. GCD=2*3. LCM=2*2*3*5*7.
• Assume * and / are constant time (ie Θ(1)).
• Compare performance of Best Algorithms for P & Q.
DAA
Transform and Conquer – Problem Reduction - Notation

• Reduce P = LCM to Q = GCD:

• LCM(x, y) = (x * y) / GCD(x, y)
• Notation: P  Q means P reduces to Q.
• LCM  GCD.
• Assume reduction steps are faster than Q (eg * and / are Θ(1)).
DAA
Transform and Conquer – Problem Reduction - Performance

Assume best algorithm for GCD is used. Are these statements true or false?

- The best algorithm for LCM can be faster than best algorithm for GCD.

- The best algorithm for GCD can be faster than best algorithm for LCM.

- Examples:

Best LCM: O(n) and Best GCD: O(n^2)

Best GCD: O(n) and Best LCM: O(n^2)

Notation: LCM  GCD.

DAA
Transform and Conquer – Problem Reduction

Counting Paths in a Graph between two vertices

Adjacency Matrix Adjacency Matrix Square

(path length of 1) (path length of 2)
DAA
Transform and Conquer – Problem Reduction

Counting Paths in a Graph between two vertices

DAA
Transform and Conquer – Problem Reduction
Reduction of Optimization Problems

• If a problem asks to find a maximum of some function, it is said to be a maximization

problem;
• If it asks to find a function’s minimum, it is called a minimization problem.
• Suppose find a minimum of some function f (x) and you have an algorithm for
function maximization.
• How can you take advantage of the latter?
• The answer lies in the simple formula min f (x)=−max[−f (x)].
• The other way is to max f(x) = - min[- f(x)]
DAA Relationship
Transform and Conquer – Problem Reduction
DAA
Transform and Conquer – Reduction to Graph Problems

• Vertices of a graph typically represent possible states of the problem in question, and
edges indicate permitted transitions among such states.
• One of the graph’s vertices represents an initial state and another represents a goal
state of the problem. (There might be several vertices of the latter kind.)
• Such a graph is called a state-space graph.
• Thus, the transformation reduces the problem to the question about a path from the
initial-state vertex to a goal-state vertex.
DAA
Transform and Conquer – Reduction to Graph Problems