1

HEAP

A heap is a binary tree-based data structure.

A heap data structure is a complete binary tree that satisfies the heap property,

Heap Property:

1. Max-Heap: The value of each node is always greater than or equal to the values
of its children, ensuring that the root node contains the maximum value. As you
move down the tree, the values decrease.
2. Min-Heap: The value of each node is always less than or equal to the values of its
children, ensuring that the root node contains the minimum value. As you move
down the tree, the values increase.

In a heap, all the tree levels are completely filled except possibly for the lowest level
which is filled from left to right.

The above tree is not a heap because it is not a complete binary tree.

Example:

What are the minimum and maximum numbers of elements in heap of height h?

Solution:

Minimum number of nodes happens in a heap in which the last level contains only one
node.

Thus, minimum no. of nodes = 20 + 21 + ⋯ + 2ℎ−1 + 1 = 2ℎ−1+1 − 1 + 1 = 2ℎ

Dr. A. K. Panda
 2

Maximum number of nodes happens in a heap in which the last level is full

Thus, Maximum no. of nodes = 20 + 21 + ⋯ + 2ℎ−1 + 2ℎ = 2ℎ+1 − 1

Example:

Show that an n-element heap has height ⌊log 𝑛⌋

Solution:

Since, the minimum and maximum numbers of elements in heap of height ℎ are 2ℎ and
2ℎ+1 − 1 respectively, we have:

2ℎ ≤ 𝑛 ≤ 2ℎ+1 − 1

Taking logarithm we get:

log 2ℎ ≤ log 𝑛 ≤ log 2ℎ+1 − 1

⇒ ℎ ≤ log 𝑛 ≤ log 2ℎ+1

⇒ ℎ ≤ log 𝑛 ≤ ℎ + 1

Hence, ℎ = ⌊log 𝑛⌋

Heapify:

The process in which the binary tree is reshaped into a Heap data structure is known as
heapify.

Maintaining the Heap property:

The heap property can be maintained by using the procedure Max-Heapify or, Min-
Heapify.

Max-Heapify Procedure:

Max-heapify is a process of arranging the nodes in correct order so that they follow
max-heap property. It has two inputs: Array A and Index i into the array. MAX-HEAPIFY
lets the value at A[i]float down in the max-heap so that the subtree rooted at index i
obeys the max-heap property.

Working Procedure:

1. Set current element i as largest.

2. If left child is greater than current element (i.e. element at 𝑖 𝑡ℎ index), then set left
child index as largest.
3. If right child is greater than element in largest, then set right child
index as largest.
4. Swap largest with current element.

Dr. A. K. Panda
 3

5. Repeat the same procedure until the subtree is heapified.

Algorithm:

MAX-HEAPIFY (A, i)
l← left[i]
r←right[i]
if 𝑙 ≤ ℎ𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒[𝐴] and 𝐴[𝑙] > 𝐴[𝑖] then
largest←l
else largest ← 𝑖
if 𝑟 ≤ ℎ𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒[𝐴] and 𝐴[𝑟] > 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡] then
largest ←r
if largest ≠ 𝑖 then
exchange 𝐴[𝑖 ] ↔ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡]
MAX-HEAPIFY (𝐴, 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 )

Example:
Suppose we have an array of elements: 𝐴 = {16, 4,10,14, 7, 9, 3, 2, 8, 1} which form the
following complete binary tree.

ℎ𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒[𝐴] = size of the array = 10.

In this tree the root node 16 satisfies max-heap property. But the parent node 4 violates
max- heap property.

Since index of 4 is 2, 𝑖 = 2.
So we call MAX-HEAPIFY (A, 2)

𝑖 = 2, 𝑙 = 𝑙𝑒𝑓𝑡[𝑖 ] = 𝑙𝑒𝑓𝑡[2] = 4, 𝑟 = 𝑟𝑖𝑔ℎ𝑡[2] = 5

𝑙 ≤ ℎ𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒[𝐴] and 𝐴[𝑙 ] > 𝐴[2] ⟹ 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 𝑙 = 4

Then 𝑟 ≤ ℎ𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒[𝐴] and 𝐴[𝑟] ≯ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡], 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 4

Since, 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 ≠ 𝑖 , exchange 𝐴[𝑖 ] ↔ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡]

Dr. A. K. Panda
 4

exchange 4 ↔ 14

Now MAX-HEAPIFY (𝐴, 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 )i.e. MAX-HEAPIFY (𝐴, 4 )

Time Complexity:

The time complexity of Heapify algorithm is equal to

𝑂(ℎ𝑒𝑖𝑔ℎ𝑡 𝑜𝑓 𝑡ℎ𝑒 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 𝑏𝑖𝑛𝑎𝑟𝑦 𝑡𝑟𝑒𝑒) i.e 𝑂(𝑙𝑜𝑔 𝑛).

Building a Heap:

Given an array of n elements, the task is to build a Binary Heap (Max-heap/Min-heap)

from the given array.

Working Procedure:

1. Create a complete binary tree from the array.

2. Starting from the first index of a non-leaf node to the index of the root apply Max
heapify procedure recursively.

Algorithm:

BUILD-MAX-HEAP(A)
heap_size(A) ← length(A)
for (𝑖 = ⌊𝑙𝑒𝑛𝑔𝑡ℎ(𝐴)/2⌋ down to 1 do
MAX-HEAPIFY(A, i)

Example:
Illustrate the operation of 𝐵𝑈𝐼𝐿𝐷 − 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃 on the array:

Dr. A. K. Panda
 5

𝐴 = {5, 3, 17, 22, 84, 19, 6, 10, 9}

Solution:

Construct a complete binary tree as follows:

9
𝐻𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒 (𝐴) = 𝑙𝑒𝑛𝑔𝑡ℎ[𝐴] = 9, 𝑖 = ⌊2⌋ = 4

So first we call the procedure MAX-HEAPIFY (A, 4)

Pass 1: MAX-HEAPIFY (A, 4)

Pass 2: MAX-HEAPIFY (A, 3)

Dr. A. K. Panda
 6

Pass 3: MAX-HEAPIFY (A, 2)

Pass 4: MAX-HEAPIFY (A, 1)

Dr. A. K. Panda
 7

Time Complexity of BUILD-MAX-HEAP:

Each call to MAX-HEAPIFY takes 𝑂(𝑙𝑜𝑔 𝑛) time

𝑛
There are 𝑂(𝑛) such calls specifically, ⌊ 2 ⌋

Thus the running time is 𝑂(𝑛 𝑙𝑜𝑔 𝑛)

Heap Sort:

This produces a sorted array by repeatedly removing the largest element from the heap
(which is the root of the heap), and then inserting it into the array. The heap is updated
after each removal. Once all elements have been removed from the heap, the result is a
sorted array.

Working Procedure:

1. Build a max-heap from an unordered array.

2. Find the maximum element, which is located at 𝐴[0] because the heap is a max-
heap.
3. Swap elements 𝐴[𝑛] and 𝐴[0] so that the maximum element is at the end of the
array where it belongs.
4. Decrement the heap size by one (this discards the node we just moved to the
bottom of the heap, which was the largest element).
5. Now run max_heapify on the heap in case the new root causes a violation of the
max-heap property.
6. Return to step 2.

Algorithm

HEAP-SORT (A)
BUILD-MAX-HEAP(A)
for 𝑖 ← 𝑙𝑒𝑛𝑔𝑡ℎ [𝐴] down to 2 do
exchange 𝐴[1] ↔ 𝐴[𝑖 ]
heap-size[𝐴] ←heap-size[𝐴] − 1
MAX-HEAPFY(𝐴, 1)

Example:
Illustate the operation of HEAP-SORT on the array 𝐴 = {6, 14, 3, 26, 8, 18, 21, 9, 5}

Dr. A. K. Panda
 8

Solution:
Initial Array:
6 14 3 26 8 18 21 9 5

14 3

26 8 18 21

9 5

Step 1:

First call BUILD-MAX-HEAP(A) to build a max heap. 𝐻𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒 (𝐴) = 9

So, 𝑖 = 4 to 1, call MAX-HEAPFY(𝐴, 𝑖).

Pass 1: MAX-HEAPFY(𝐴, 4)
𝐴[𝑖] = 26, 𝐴[𝑙] = 9, 𝐴[𝑟] = 5
𝐴[𝑖 ] > 𝐴[𝑙] and 𝐴[𝑖 ] > 𝐴[𝑟]

Pass2: MAX-HEAPFY(𝐴, 3)
𝐴[𝑖] = 3, 𝐴[𝑙] = 18, 𝐴[𝑟] = 21
𝐴[𝑙 ] > 𝐴[𝑖 ], Thus 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 6
𝐴[𝑟] > 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡] Thus 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 7 and 𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝐴[𝑖 ] ↔ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡]

14 21

26 8 18 3

9 5

Dr. A. K. Panda
 9

Pass3: MAX-HEAPFY(𝐴, 2)
𝐴[𝑖] = 14, 𝐴[𝑙] = 26, 𝐴[𝑟] = 8
𝐴[𝑙 ] > 𝐴[𝑖 ], Thus 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 4
𝐴[𝑟] < 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡] and 𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝐴[𝑖 ] ↔ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡]

26 21

14 8 18 3

9 5

Now 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 4, call MAX-HEAPFY(𝐴, 4)

𝐴[𝑖] = 14, 𝐴[𝑙] = 9, 𝐴[𝑟] = 5

𝐴[𝑖 ] > 𝐴[𝑙] and 𝐴[𝑖 ] > 𝐴[𝑟]

Pass 4:
MAX-HEAPFY(𝐴, 1)
𝐴[𝑖 ] > 𝐴[𝑙 ], 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 2
𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡] > 𝐴[𝑟] and 𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝐴[𝑖 ] ↔ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡]

26

6 21

14 8 18 3

9 5

Now 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 2, call MAX-HEAPFY(𝐴, 2)

𝐴[𝑖] < 𝐴[𝑙]. Thus 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 4
𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡] > 𝐴[𝑟] and 𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝐴[𝑖 ] ↔ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡]

Dr. A. K. Panda
 10

26

14 21

6 8 18 3

9 5

Now 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 4, call MAX-HEAPFY(𝐴, 4)

𝐴[𝑖] < 𝐴[𝑙]. Thus 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 = 8
𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡] > 𝐴[𝑟] and 𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝐴[𝑖 ] ↔ 𝐴[𝑙𝑎𝑟𝑔𝑒𝑠𝑡]
26

14 21

9 8 18 3

6 5

Step 2:
For 𝑖 = 9 down to 2
𝑒𝑥𝑐ℎ𝑎𝑛𝑔𝑒 𝐴[1] ↔ 𝐴[𝑖 ] and heap-size = heap-size-1 and call 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃𝐼𝐹𝑌 (𝐴, 1)
Pass 1:
By exchanging A[1] with A[9] and reducing heap-size by 1 we get

14 21

9 8 18 3

6 25

Dr. A. K. Panda
 11

5 14 21 9 8 18 3 6 26

Now applying 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃𝐼𝐹𝑌 (𝐴, 1) we get

21

14 18

9 8 5 3

Pass 2:
By exchanging A[1] with A[8] and reducing heap-size by 1 we get

14 18

9 8 5 3

21

6 14 18 9 8 5 3 21 26

Now applying 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃𝐼𝐹𝑌 (𝐴, 1) we get

18

14 6

9 8 5 3

Dr. A. K. Panda
 12

Pass 3:
By exchanging A[1] with A[7] and reducing heap-size by 1 we get

14 6

9 8 5 18

3 14 6 9 8 5 18 21 26

Now applying 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃𝐼𝐹𝑌 (𝐴, 1) we get

14

9 6

3 8 5

Pass 4:
By exchanging A[1] with A[6] and reducing heap-size by 1 we get

9 6

3 8 14

5 9 6 3 8 14 18 21 26

Now applying 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃𝐼𝐹𝑌 (𝐴, 1) we get

8 6

3 5

Dr. A. K. Panda
 13

Pass 5:
By exchanging A[1] with A[5] and reducing heap-size by 1 we get

8 6

3 9

5 8 6 2 9 14 18 21 26

Now applying 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃𝐼𝐹𝑌 (𝐴, 1) we get

5 6

Pass 6:
By exchanging A[1] with A[4] and reducing heap-size by 1 we get

5 6

3 5 6 8 9 14 18 21 26

Now applying 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃𝐼𝐹𝑌 (𝐴, 1) we get

5 3

Dr. A. K. Panda
 14

Pass 7:
By exchanging A[1] with A[3] and reducing heap-size by 1 we get

5 6

3 5 6 8 9 14 18 21 26

Now applying 𝑀𝐴𝑋 − 𝐻𝐸𝐴𝑃𝐼𝐹𝑌 (𝐴, 1) we get

Pass 8:
By exchanging A[1] with A[2] and reducing heap-size by 1 we get

3 5 6 8 9 14 18 21 26

Thus the sorted array is:

3 5 6 8 9 14 18 21 26

Time Complexity:

Worst Case: If the elements of the array is alreay in ascending order, line 1 takes
𝑂(𝑛) time while line 5 takes 𝑂(log 𝑛) time since MAX-HEAPIFY must do log 𝑛 exchange.
Hence 𝑇(𝑛) = 𝑂(𝑛) + 𝑛 𝑂(log 𝑛) = 𝑂(𝑛 log 𝑛).

Best Case: If the elements of the array is in descending order, line 1 calls to MAX-
HEAPIFY 𝑂(𝑛/2) times without any work and line 5 takes 𝑂(log 𝑛) times. Hence 𝑇(𝑛) =
𝑂(𝑛/2) + 𝑛 𝑂(log 𝑛) = 𝑂(𝑛 log 𝑛).

Dr. A. K. Panda
 15

Space complexity:

The space complexity of heap-sort is 𝑂(1), because it does not require any extra
memory.

PRIORITY QUEUE

A priority queue is a type of queue in which each element has a priority value
associated with it and they are arranged in a queue based on their priority. Elements
with higher priority values are typically retrieved or removed before elements with
lower priority values.

Difference between Priority Queue and Normal Queue:

In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the

values are removed on the basis of priority.

Properties:

1. Every element in a priority queue has some priority associated with it.
2. An element with the higher priority will be dequeued before the elements with
lesser priority.
3. If two elements in a priority queue have the same priority, they will be arranged
using the FIFO principle.

Types of Priority queues:

1. Min priority Queue: If the element with the smallest value has the highest
priority, then that priority queue is called the min-priority queue or ascending
order priority queue.
2. Max Priority Queue: If the element with the highest value has the highest
priority, then that priority queue is called the max-priority queue or descending
order priority queue.

Implementation of Priority Queue

Priority queue can be implemented by using:

 an array
 a linked list
 a heap data structure, or
 a binary search tree.

Implementation of Priority Queue by using binary heap:

We can implement the min-priority queue using a min heap, whereas we can implement
the max priority queue using a max heap.

Dr. A. K. Panda
 16

MAX-Priority Queue Operations:

A Max-priority queue supports the following operations:

1. 𝑀𝐴𝑋𝐼𝑀𝑈𝑀(𝑆) : returns the element of S with the largest key.

2. 𝐸𝑋𝑇𝑅𝐴𝐶𝑇 − 𝑀𝐴𝑋(𝑆): removes and returns the element of S with the largest key.
3. 𝐼𝑁𝐶𝑅𝐸𝐴𝑆𝐸 − 𝐾𝐸𝑌 (𝑆, 𝑥, 𝑘): increases value of element x’s key to the new value k.
Assume that 𝑘 ≥x’s current key value.
4. 𝐼𝑁𝑆𝐸𝑅𝑇(𝑆 , 𝑥 ): inserts the element x with key k into the set S, i.e. 𝑆 = 𝑆 ∪ {𝑥 }

1. Finding the maximum element from the Priority Queue:

The maximum element in a priority queue is the root of the tree.

Algorithm:

MAX-HEAP-MAXIMUM (A)
if 𝐴. ℎ𝑒𝑎𝑝 − 𝑠𝑖𝑧𝑒 < 1
error “heap underflow”;
return A[1];

Time Complexity: 𝑂(1)

2. Extracting the maximum element from the priority queue:

1. Remove the element from the root
2. Remove the last element from the last level of the heap
3. Replace the root with the last element
4. Re-heapify the heap with one fewer node.

Algorithm:

MAX-HEAP-EXTRACT-MAX(A)

1. 𝑚𝑎𝑥 = 𝑀𝐴𝑋-𝐻𝐸𝐴𝑃-𝑀𝐴𝑋𝐼𝑀𝑈𝑀 (𝐴)

2. 𝐴[1] = 𝐴[𝐴. ℎ𝑒𝑎𝑝-𝑠𝑖𝑧𝑒]
3. 𝐴. ℎ𝑒𝑎𝑝-𝑠𝑖𝑧𝑒 = 𝐴. ℎ𝑒𝑎𝑝-𝑠𝑖𝑧𝑒 − 1
4. 𝑀𝐴𝑋-𝐻𝐸𝐴𝑃𝐼𝐹𝑌(𝐴, 1)
5. 𝑟𝑒𝑡𝑢𝑟𝑛 𝑚𝑎𝑥

Time Complexity: 𝑀𝐴𝑋-𝐻𝐸𝐴𝑃𝐼𝐹𝑌 takes 𝑂(𝑙𝑜𝑔 𝑛) time and since only constant work is
added to it, time complexity of MAX-HEAP-EXTRACT-MAX(A) is 𝑂(𝑙𝑜𝑔 𝑛).

3. Increasing Key Value:

Suppose element whose key to be increased is identified by index i

Dr. A. K. Panda
 17

1. Make sure that key is more than the element at index i.

2. Update 𝐴[𝑖] to key
3. Traverse the tree upward comparing 𝐴[𝑖] to its parent and swapping keys if
necessary, until 𝐴[𝑖]’s key is smaller than its parent’s key.

Algorithm:
MAX-HEAP-INCREASE-KEY(𝑨, 𝒊, 𝒌𝒆𝒚)
if key< A[i] then
error “new key is smaller than current key”
end if
A[i] ← key
while i > 1 and A[Parent(i)] < A[i] do
exchange 𝐴[𝑖] ↔ 𝐴[𝑃𝑎𝑟𝑒𝑛𝑡(𝑖)]
𝑖 ←Parent(i)
end while
Time Complexity: It is height of tree 𝑂(𝑙𝑜𝑔 𝑛)
Example:
MAX-HEAP-INCREASE-KEY(𝐴, 9,15) : Update node 9 from 4 to 15.

4. Inserting into the heap

Given a key to insert into the heap:

1. Increment the heap size.

2. Insert a new node in the last position in the heap, with key −∞.

Dr. A. K. Panda
 18

3. Increase the −∞ key to key using the MAX-HEAP-INCREASE-KEY procedure

defined above.

Algorithm:

MAX-HEAP-INSERT(𝑨, 𝒌𝒆𝒚)

1. ℎ𝑒𝑎𝑝-𝑠𝑖𝑧𝑒(𝐴) ← ℎ𝑒𝑎𝑝-𝑠𝑖𝑧𝑒(𝐴) + 1
2. 𝐴[ℎ𝑒𝑎𝑝-𝑠𝑖𝑧𝑒(𝐴)] ← −∞
3. MAX-HEAP-INCREASE-KEY(𝐴, ℎ𝑒𝑎𝑝-𝑠𝑖𝑧𝑒(𝐴), 𝑘𝑒𝑦)

Time Complexity: 𝑂(𝑙𝑜𝑔 𝑛)

Dr. A. K. Panda
 19

DYNAMIC PROGRAMMING

It is a programming technique in which solution is obtained from a sequence of

decisions.

A dynamic programming problem can be divided into a number of stages where an

optimal decision must be made at each stage. The decision made at each stage must take
into account its effects not only on the next stage, but also on the entire subsequent
stages. Dynamic programming provides a systematic procedure whereby starting with
the last stage of the problem and working backwards one makes an optimal decision for
each stage of problem. The information for the last stage is the information derived
from the previous stage.

Dynamic programming design involves 4 major steps.

1. Characterize the structure of optimal solution.

2. Recursively define the value of an optimal solution.
3. Compute the value of an optimum solution in a bottom up fashion.
4. Construct an optimum solution from computed information

General Characteristics of Dynamic Programming:

The general characteristics of Dynamic programming are

1. The problem can be divided into stages with a policy decision required at each
stage.
2. Each stage has number of states associated with it.
3. Given the current stage an optimal policy for the remaining stages is
independent of the policy adopted.
4. The solution procedure begins be finding the optimal policy for each state of the
last stage.
5. A recursive relation is available which identifies the optimal policy for each stage
with n stages remaining given the optimal policy for each stage with (n-1) stages
remaining.

Difference between Divide-and Conquer & Dynamic Programming

Sl. Divide-and Conquer Dynamic Programming

No.
1. It Breaks a problem into smaller sub- Breaks a problem into overlapping
problems and solves them sub-problems and solves them
independently. recursively or iteratively, storing their
solutions.
2. It can be thought of as top-down It can be thought of as bottom-up
algorithms. algorithm
3. Sub-problems are independent of each Sub-problems can overlap or share
other. common sub-problems.

Dr. A. K. Panda
 20

4. Generally simpler to understand and Can often be quite complex and tricky
implement.
5. It can be used for any kind of It is generally used for optimization
problems. problem.

Applications of Dynamic Programming

1. Matrix Chain Multiplication

2. Longest common sequence
3. Assembly line scheduling
4. Optimal Binary search Trees
5. 0/1 Knapsack Problem
6. Shortest path problem
7. Travelling sales person problem

Matrix Chain Multiplication:

Given a sequence of 𝑛 matrices 𝐴1 , 𝐴2 , … 𝐴𝑛 of order 𝑝0 × 𝑝1 , 𝑝1 × 𝑝2 , … , 𝑝𝑛−1 ×

𝑝𝑛 respectively, the objective is to compute their product 𝐴1 × 𝐴2 × … × 𝐴𝑛 using
minimum number of scalar multiplications.

Suppose there are two matrices 𝐴1 & 𝐴2 of order (3 × 3) and (3 × 2) respectively:

𝑎11 𝑎12 𝑎13 𝑏11 𝑏12

𝑎
𝐴1 = [ 21 𝑎22 𝑎23 ] & 𝐴2 = [𝑏21 𝑏22 ] then
𝑎31 𝑎32 𝑎33 𝑏31 𝑏32

𝑎11 . 𝑏11 + 𝑎12 . 𝑏21 + 𝑎13 . 𝑏31 𝑎11 . 𝑏12 + 𝑎12 . 𝑏22 + 𝑎13 . 𝑏32
𝐴1 × 𝐴2 = [𝑎21 . 𝑏11 + 𝑎22 . 𝑏21 + 𝑎23 . 𝑏31 𝑎21 . 𝑏12 + 𝑎22 . 𝑏22 + 𝑎23 . 𝑏32 ]
𝑎31 . 𝑏11 + 𝑎32 . 𝑏21 + 𝑎33 . 𝑏31 𝑎31 . 𝑏12 + 𝑎32 . 𝑏22 + 𝑎33 . 𝑏32

Total Number of scalar multiplications

= 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 = 18 = 3 × 3 × 2

If 𝐴1 is of order 𝑝0 × 𝑝1 and 𝐴2 is of order 𝑝1 × 𝑝2 then number of scalar multiplications

in computation of 𝐴1 × 𝐴2 is 𝑝0 𝑝1 𝑝2 .

Algorithm to multiply two matrices:

MATRIX-MULTIPLY (A, B, C, m, n, p)
{
for 𝑖 = 1 to m do
{
for j = 1 to n do
{
for 𝑘 = 1 to p do

Dr. A. K. Panda
 21

𝐶 [𝑖, 𝑗] = 𝐶 [𝑖, 𝑗] + 𝐴[𝑖, 𝑘] ∗ 𝐵[𝑘, 𝑗];

}
}
}
The running time of the above algorithm is 𝑚𝑛𝑝.

Since matrix multiplication is non-commutative and associative, there are different

ways to compute 𝐴1 × 𝐴2 × … × 𝐴𝑛 and our objective is to find the best way (minimum
number of multiplications).

For example, let us consider three matrices 𝐴1 , 𝐴2 , 𝐴3 of order (10 × 100), (100 × 5)
and (5 × 50) respectively.

Here 𝑝0 = 10, 𝑝1 = 100, 𝑝2 = 5 and 𝑝3 = 50

There are two ways to compute 𝐴1 × 𝐴2 × 𝐴3 :

𝐴1 × 𝐴2 × 𝐴3 = (𝐴1 × 𝐴2 ) × 𝐴3 = 𝐴1 × (𝐴2 × 𝐴3 )

Computation of (𝐴1 × 𝐴2 ) × 𝐴3 :

𝐴1 × 𝐴2 = 𝐴12 requires 10 × 100 × 5 = 5000 multiplications

𝐴12 × 𝐴3 requires 10 × 5 × 50 = 2500 multiplications

Total: 7500 multiplications

Computation of 𝐴1 × (𝐴2 × 𝐴3 ):

𝐴2 × 𝐴3 = 𝐴23 requires 100 × 5 × 50 = 25000 multiplications

𝐴1 × 𝐴23 requires 10 × 100 × 50 = 50000 multiplications

Total: 75000 multiplications

No. of ways for parenthesizing the matrices:

Let 𝑃(𝑛) = Possible number of parenthesization to multiply n matrices 𝐴1 × 𝐴2 × … ×

𝐴𝑛

𝑃(1) = 1 (𝐴1 )

𝑃(2) = 1 (𝐴1 × 𝐴2 )

𝑃 (3) = 2 (𝐴1 × 𝐴2 ) × 𝐴3

𝐴1 × (𝐴2 × 𝐴3 )

𝑃 (4) = 5 𝐴1 × (𝐴2 × (𝐴3 × 𝐴3 ))

Dr. A. K. Panda
 22

𝐴1 × ((𝐴2 × 𝐴3 ) × 𝐴3 )

(𝐴1 × 𝐴2 ) × (𝐴3 × 𝐴3 )

((𝐴1 × 𝐴2 ) × 𝐴3 ) × 𝐴3

(𝐴1 × (𝐴2 × 𝐴3 )) × 𝐴3

In general if there are 𝑛 matrices then there are 𝑛 − 1 places where we can split the
sequence into two parts: one consists of 𝑘 matrices and the other consists of 𝑛 − 𝑘
matrices.

If there are 𝑝 ways for parenthesizing the left sequence and 𝑞 ways for parenthesizing
the right sequence then total number of ways will be 𝑝 × 𝑞.

Since 𝑘 has 𝑛 − 1 choices then

1 𝑖𝑓 𝑛 = 1
𝑛−1
𝑃(𝑛) = {
∑ 𝑃(𝑘) × 𝑃(𝑛 − 𝐾) 𝑖𝑓 𝑛 ≥ 2
𝑘=1

1 𝑖𝑓 𝑛 = 1
( )
𝑃 𝑛 ={ 2(𝑛 − 1)𝐶𝑛−1
𝑖𝑓 𝑛 ≥ 2
𝑛

Dynamic Programming Approach:

Input: (𝑝0 , 𝑝1 , … 𝑝𝑛 ) i.e. A sequence of n matrices 𝐴1 , 𝐴2 , … 𝐴𝑛 of order (𝑝0 × 𝑝1 ), (𝑝1 ×

𝑝2 ), … (𝑝𝑛−1 × 𝑝𝑛 )

Output: A parenthesization of 𝐴1 × 𝐴2 × … × 𝐴𝑛 that minimizes the total number of

scalar multiplications.

Note that in the matrix-chain multiplication problem, we are not actually multiplying
matrices. Our goal is only to determine an order for multiplying matrices that has the
lowest cost.

1. Characterize the structure of optimal solution:

Our first step in the dynamic-programming paradigm is to find the optimal substructure
and then use it to construct an optimal solution to the problem from optimal solutions
to sub-problems.

Let 𝐴𝑖..𝑗 = 𝐴𝑖 × 𝐴𝑖+1 × … × 𝐴𝑗

The order of 𝐴𝑖..𝑗 is (𝑝𝑖−1 × 𝑝𝑗 )

Our objective is to break the problem into several simpler and smaller sub-problems of
similar structure.

Dr. A. K. Panda
 23

𝐴𝑖..𝑗 = 𝐴𝑖..𝑘 × 𝐴𝑘+1..𝑗

That is, for some value of 𝑘, we first compute the matrices 𝐴𝑖..𝑘 and 𝐴𝑘+1..𝑗 and then
multiply them together to produce the final product 𝐴𝑖..𝑗 .

𝑇ℎ𝑒 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑡ℎ𝑖𝑠 𝑝𝑎𝑟𝑒𝑛𝑡ℎ𝑒𝑠𝑖𝑧𝑎𝑡𝑖𝑜𝑛 =

𝑇ℎ𝑒 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑐𝑜𝑚𝑝𝑢𝑡𝑖𝑛𝑔 𝑡ℎ𝑒 𝑚𝑎𝑡𝑟𝑖𝑥 𝐴𝑖..𝑘 + 𝑇ℎ𝑒 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑐𝑜𝑚𝑝𝑢𝑡𝑖𝑛𝑔 𝐴𝑘+1..𝑗
+ 𝑇ℎ𝑒 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑦𝑖𝑛𝑔 𝑡ℎ𝑒𝑚 𝑡𝑜𝑔𝑒𝑡ℎ𝑒𝑟.

2. Recursively define the value of an optimal solution:

Let 𝑚[𝑖, 𝑗] be the minimal number of multiplications needed to compute 𝐴𝑖..𝑗

= 𝐴𝑖 × 𝐴𝑖+1 × … × 𝐴𝑗

If the final multiplication for 𝐴𝑖..𝑗 is 𝐴𝑖..𝑗 = 𝐴𝑖..𝑘 × 𝐴𝑘+1..𝑗 then we have to compute
recursively the best way to multiply the chain from 𝑖 to 𝑘, and from 𝑘 + 1 to 𝑗, and add
the cost of the final product. This means that

𝑚[𝑖, 𝑗] = 𝑚[𝑖, 𝑘] + 𝑚[𝑘 + 1, 𝑗] + 𝑝𝑖−1 × 𝑝𝑘 × 𝑝𝑗 .

We have to find value of 𝑘 so that 𝑚[𝑖, 𝑗] is minimum.

We do not know the optimal value of k, hence,

0 𝑖𝑓 𝑖 = 𝑗
𝑚[𝑖, 𝑗] = { min {𝑚[𝑖, 𝑘] + 𝑚[𝑘 + 1, 𝑗] + 𝑝 × 𝑝 × 𝑝 } 𝑖𝑓 𝑖 < 𝑗
𝑖−1 𝑘 𝑗
𝑖≤𝑘<𝑗

To keep track of optimal sub-solutions, we store the value of 𝑘 in a table 𝑠[𝑖, 𝑗]. Note
that, 𝑘 is the place at which we split the product 𝐴𝑖..𝑗 to get an optimal parenthesization.

[Link] the value of optimal solution in a bottom-up fashion by constructing cost

tables.

That is we calculate in the order:

𝑚[1,2], 𝑚[2,3], 𝑚[3,4] .. .. ………… 𝑚[𝑛 − 2, 𝑛 − 1] 𝑚[𝑛 − 1, 𝑛]

𝑚[1,3] 𝑚[2,4] 𝑚[3,5] .. .. ………… 𝑚[𝑛 − 2, 𝑛]
𝑚[1,4] 𝑚[2,5] 𝑚[3,6] .. .. 𝑚[𝑛 − 3, 𝑛]
.
.
𝑚[1, 𝑛]

[Link] an optimal solution from computed information.

The array 𝑠[𝑖, 𝑗] gives the optimal split points.

Dr. A. K. Panda
 24

Example:

Consider a sequence of matrices 𝐴, 𝐵, 𝐶 and 𝐷 with order (3 × 7), (7 × 6), (6 × 2) and

(2 × 9) respectively. Find the lowest cost parenthesization to multiply the given
matrices using matrix chain multiplication.

Solution:

Given, 𝑛 = 4, 𝑝0 = 3, 𝑝1 = 7, 𝑝2 = 6, 𝑝3 = 2 and 𝑝4 = 9

𝑃 (1) = 1

𝑃 (2) = 𝑃 (1) . 𝑃 (1) = 1 × 1 = 1

𝑃 (3) = 𝑃 (1). 𝑃 (2 ) + 𝑃 (2). 𝑃 (1 ) + 𝑃 (1). 𝑃 ( 1) = 1 × 1 + 1 × 1 = 2

4

𝑃 (4) = ∑ 𝑃 (𝑘 ) 𝑃 (4 − 𝑘 ) = 𝑃 (1). 𝑃 (4 − 1 ) + 𝑃 (2). 𝑃 ( 4 − 2) + 𝑃 (3 ). 𝑃 (4 − 3)

𝑘=1
+ 𝑃(4). 𝑃(4 − 4) = 𝑃 (1). 𝑃 (3) + 𝑃 (2). 𝑃 (2) + 𝑃 (3). 𝑃 (1) = 2 + 1 + 2 = 5.

Hence number of possible parenthesization for 𝑛 = 4 is 5.

1. ((𝐴 × 𝐵) × 𝐶) × 𝐷
2. (𝐴 × (𝐵 × 𝐶 )) × 𝐷
3. (𝐴 × 𝐵 ) × (𝐶 × 𝐷 )
4. 𝐴 × ((𝐵 × 𝐶 ) × 𝐷)
5. 𝐴 × (𝐵 × (𝐶 × 𝐷))

Initialization:

for 𝑖 = 1 to n do 𝑚[𝑖 , 𝑖 ] = 0

𝑚[1,1 ] = 0, 𝑚[2 , 2 ] = 0, 𝑚[3 , 3 ] = 0, 𝑚[4 , 4 ] = 0

𝒎[𝒊, 𝒋]
1 2 3 4
1 0
2 0
3 0
4 0
Iteration 1:

𝑚[1,2] = min {𝑚[1, 1] + 𝑚[2, 2] + 𝑝0 × 𝑝1 × 𝑝2 } = 0 + 0 + 3 × 7 × 6 = 126

1≤𝑘<2

Dr. A. K. Panda
 25

𝑚[2,3] = min {𝑚[2, 2] + 𝑚[3, 3] + 𝑝1 × 𝑝2 × 𝑝3 } = 0 + 0 + 7 × 6 × 2 = 84

1≤𝑘<2

𝑚[3,4] = min {𝑚[3, 3] + 𝑚[4, 4] + 𝑝2 × 𝑝3 × 𝑝4 } = 0 + 0 + 6 × 2 × 9 = 108

1≤𝑘<2

𝒎[𝒊, 𝒋]
1 2 3 4
1 0 126
2 0 84
3 0 108
4 0
Iteration 2:

𝑚[1,3] = min {𝑚[1, 1] + 𝑚[2, 3] + 𝑝0 × 𝑝1 × 𝑝3, 𝑚[1, 2] + 𝑚[3, 3] + 𝑝0 × 𝑝2 × 𝑝3 }

1≤𝑘<3

= min{(0 + 84 + 3 × 7 × 2), 126 + 0 + 3 × 6 × 2}

= min{106, 162} = 106(𝑘 = 1)

𝑚[2,4] = min {𝑚[2, 2] + 𝑚[3,4] + 𝑝1 × 𝑝2 × 𝑝4, 𝑚[2,3] + 𝑚[4,4] + 𝑝1 × 𝑝3 × 𝑝4 }

2≤𝑘<4

= min{(0 + 108 + 7 × 6 × 9), 84 + 0 + 7 × 2 × 9}

= min{486,210} = 210(𝑘 = 3)

𝒎[𝒊, 𝒋]
1 2 3 4
1 0 126 106
2 0 84 210
3 0 108
4 0
Iteration 3:

𝑚[1,4] = min {𝑚[1, 1] + 𝑚[2,4] + 𝑝0 × 𝑝1 × 𝑝4, 𝑚[1,2] + 𝑚[3,4] + 𝑝0 × 𝑝2 × 𝑝4 ,

1≤𝑘<4
𝑚[1,3] + 𝑚[4,4] + 𝑝0 × 𝑝3 × 𝑝4 }

= min{(0 + 210 + 3 × 7 × 9), 126 + 108 + 3 × 6 × 9 , 106 + 0 + 3 × 2 × 9}

Dr. A. K. Panda
 26

= min{399, 396, 160} = 160(𝑘 = 3)

𝒎[𝒊, 𝒋]
1 2 3 4
1 0 126 106 160
2 0 84 210
3 0 108
4 0

Therefore, the optimal solution 𝑚[1,4] = 160

𝒔[𝒊, 𝒋]
1 2 3 4
1 0 126/1 106/1 160/3
2 0 84/2 210/3
3 0 108/3
4 0

The lowest cost value at [1, 4] is achieved when k = 3, therefore, the first
parenthesization must be done at 3.

(𝐴 × 𝐵 × 𝐶) × 𝐷

The lowest cost value at [1, 3] is achieved when k = 1, therefore the next
parenthesization is done at 1.

(𝐴 × (𝐵 × 𝐶 )) × 𝐷

and optimal parenthesization is

(𝐴 × (𝐵 × 𝐶 )) × 𝐷

Algorithm Matrix-Chain-Order:

This algorithm determines the optimal number of scalar multiplications needed to

compute product of a sequence of matrices.

𝑠[𝑖, 𝑗]: The value of 𝑘 such that an optimal parenthesization of 𝐴𝑖 , 𝐴2 , … 𝐴𝑗 splits into
(𝐴𝑖 , … , 𝐴𝑘 ) and 𝐴𝑘+1 , … , 𝐴𝑗 .

𝑚[𝑖, 𝑗]: Minimal number of multiplications needed to compute 𝐴𝑖..𝑗

Dr. A. K. Panda
 27

𝑴𝒂𝒕𝒓𝒊𝒙 − 𝑪𝒉𝒂𝒊𝒏 − 𝑶𝒓𝒅𝒆𝒓(𝒑)

{
𝑛 = 𝑙𝑒𝑛𝑔𝑡ℎ[𝑝]– 1;
for 𝑖 = 1 to 𝑛 do
𝑚[𝑖, 𝑖 ] = 0;
for 𝑙 = 2 to 𝑛 do // 𝑙 is the chain length.
{
for 𝑖 = 1 to 𝑛 − 𝑙 + 1 do
{
𝑗 = 𝑖 + 𝑙 − 1;
𝑚[𝑖, 𝑗] = ∞;
for 𝑘 = 𝑖 to 𝑗 – 1 do
{
𝑞 = 𝑚[𝑖, 𝑘] + 𝑚[𝑘 + 1, 𝑗] + 𝑝[𝑖 − 1] ∗ 𝑝[𝑘] ∗ 𝑝[𝑗];
if 𝑞 < 𝑚[𝑖, 𝑗] then
{
𝑚[𝑖, 𝑗] = 𝑞;
𝑠[𝑖, 𝑗] = 𝑘;
}
}
}
}
return 𝑚 and 𝑠;
}
Time Complexity:
There are three nested loops and each loop index takes on ≤ 𝑛 values. Hence the time
complexity is 𝑂(𝑛3 ).

Algorithm 𝐏𝐑𝐈𝐍𝐓 − 𝐎𝐏𝐓𝐈𝐌𝐀𝐋 − 𝐏𝐀𝐑𝐄𝐍𝐓𝐇𝐄𝐒𝐈𝐒

This algorithm prints an optimal parenthesization of product of the
matrices 𝐴1 , 𝐴2 , … 𝐴𝑛 .

𝑃𝑅𝐼𝑁𝑇 − 𝑂𝑃𝑇𝐼𝑀𝐴𝐿 − 𝑃𝐴𝑅𝐸𝑁𝑇𝐻𝐸𝑆𝐼𝑆 (𝑠, 𝑖, 𝑗)

{
if (𝑖 == 𝑗) then print "𝐴"𝑖 ;
else
{
print “(“;
𝑃𝑅𝐼𝑁𝑇 − 𝑂𝑃𝑇𝐼𝑀𝐴𝐿 − 𝑃𝐴𝑅𝐸𝑁𝑇𝐻𝐸𝑆𝐼𝑆 (𝑠, 𝑖, 𝑠[𝑖, 𝑗]);
𝑃𝑅𝐼𝑁𝑇 − 𝑂𝑃𝑇𝐼𝑀𝐴𝐿 − 𝑃𝐴𝑅𝐸𝑁𝑇𝐻𝐸𝑆𝐼𝑆 (𝑠, 𝑠[𝑖, 𝑗] + 1, 𝑗);
print “)“;
}
}

Dr. A. K. Panda
 28

Example:

Consider a sequence of matrices 𝐴1 , 𝐴2 , … , 𝐴5 with order (4 × 10), (10 × 3), (3 ×

12), (12 × 20), and (20 × 7) respectively. Find the lowest cost parenthesization to
multiply the given matrices using matrix chain multiplication.

Solution:

Initialization:

Given, 𝑛 = 5, 𝑝0 = 4, 𝑝1 = 10, 𝑝2 = 3, 𝑝3 = 12, 𝑝4 = 20, 𝑝5 = 7

𝑚[1,1 ] = 0, 𝑚[2 , 2 ] = 0, 𝑚[3 , 3 ] = 0, 𝑚[4 , 4 ] = 0, 𝑚[5 , 5 ] = 0

𝒎[𝒊, 𝒋] 1 2 3 4 5
1 0
2 0
3 0
4 0
5 0
Iteration 1:

𝑚[1,2] = min {𝑚[1, 1] + 𝑚[2, 2] + 𝑝0 × 𝑝1 × 𝑝2 } = 0 + 0 + 4 × 10 × 3 = 120

1≤𝑘<2

𝑚[2,3] = min {𝑚[2, 2] + 𝑚[3, 3] + 𝑝1 × 𝑝2 × 𝑝3 } = 0 + 0 + 10 × 3 × 12 = 360

1≤𝑘<2

𝑚[3,4] = min {𝑚[3, 3] + 𝑚[4, 4] + 𝑝2 × 𝑝3 × 𝑝4 } = 0 + 0 + 3 × 12 × 20 = 720

1≤𝑘<2

𝑚[4,5] = min {𝑚[4, 4] + 𝑚[5, 5] + 𝑝3 × 𝑝4 × 𝑝5 } = 0 + 0 + 12 × 20 × 7 = 1680

1≤𝑘<2

𝒎[𝒊, 𝒋] 1 2 3 4 5
1 0 120
2 0 360
3 0 720
4 0 1680
5 0

Iteration 2:

Dr. A. K. Panda
 29

𝑚[1, 1] + 𝑚[2, 3] + 𝑝0 × 𝑝1 × 𝑝3, = 0 + 360 + 4 × 10 × 12 = 840

𝑚[1,3] = min {
1≤𝑘<3 𝑚[1, 2] + 𝑚[3, 3] + 𝑝0 × 𝑝2 × 𝑝3 = 120 + 0 + 4 × 3 × 12 = 264

= 264 (𝑘 = 2)

𝑚[2, 2] + 𝑚[3,4] + 𝑝1 × 𝑝2 × 𝑝4, = 0 + 720 + 10 × 3 × 20 = 1320

𝑚[2,4] = min {
2≤𝑘<4 𝑚 [2,3] + 𝑚 [4,4] + 𝑝1 × 𝑝3 × 𝑝4 = 360 + 0 + 10 × 12 × 20 = 2760

= 1320(𝑘 = 2)

𝑚[3, 3] + 𝑚[4,5] + 𝑝2 × 𝑝3 × 𝑝5, = 0 + 1680 + 3 × 12 × 7 = 1932

𝑚[3,5] = min {
3≤𝑘<5 𝑚 [3,4] + 𝑚 [5,5] + 𝑝2 × 𝑝4 × 𝑝5 = 720 + 0 + 3 × 20 × 7 = 1140

= 1140(𝑘 = 4)

𝒎[𝒊, 𝒋] 1 2 3 4 5
1 0 120 264
2 0 360 1320
3 0 720 1140
4 0 1680
5 0

Iteration 3:

𝑚[1,4]
𝑚[1, 1] + 𝑚[2, 4] + 𝑝0 × 𝑝1 × 𝑝4 = 0 + 1320 + 4 × 10 × 20 = 2120
= min {𝑚[1, 2] + 𝑚[3, 4] + 𝑝0 × 𝑝2 × 𝑝4 = 120 + 720 + 4 × 3 × 20 = 1080
1≤𝑘<4
𝑚[1, 3] + 𝑚[4, 4] + 𝑝0 × 𝑝3 × 𝑝4 = 264 + 0 + 4 × 12 × 20 = 1224

= 1080(𝑘 = 2)

𝑚[2,5]
𝑚[2, 2] + 𝑚[3,5] + 𝑝1 × 𝑝2 × 𝑝5 = 0 + 1140 + 10 × 3 × 7 = 1350
= min {𝑚[2, 3] + 𝑚[4,5] + 𝑝1 × 𝑝3 × 𝑝5 = 360 + 1680 + 10 × 12 × 7 = 2880
2≤𝑘<5
𝑚[2, 4] + 𝑚[5,5] + 𝑝1 × 𝑝4 × 𝑝5 = 1320 + 0 + 10 × 20 × 7 = 2720

= 1350(𝑘 = 2)

Dr. A. K. Panda
 30

𝒎[𝒊, 𝒋] 1 2 3 4 5
1 0 120 264 1080
2 0 360 1320 1350
3 0 720 1140
4 0 1680
5 0

Iteration 4:

𝑚[1,5]
𝑚[1, 1] + 𝑚[2, 5] + 𝑝0 × 𝑝1 × 𝑝5 = 0 + 1350 + 4 × 10 × 7 = 1630
𝑚[1, 2] + 𝑚[3, 5] + 𝑝0 × 𝑝2 × 𝑝5 = 120 + 1140 + 4 × 3 × 7 = 1344
= min
1≤𝑘<4 𝑚 [1, 3] + 𝑚[4, 5] + 𝑝0 × 𝑝3 × 𝑝5 = 264 + 1680 + 4 × 12 × 7 = 2016
{𝑚[1, 4] + 𝑚[5, 5] + 𝑝0 × 𝑝4 × 𝑝5 1380 + 0 + 4 × 20 × 7 = 1544

= 1344(𝑘 = 2)

𝒎[𝒊, 𝒋] 1 2 3 4 5
1 0 120 264 1080 1344
2 0 360 1320 1350
3 0 720 1140
4 0 1680
5 0

Therefore the optimal solution 𝑚[1, 5] = 1344

Now for optimal parenthesization, each time we find the optimal value of 𝑚[𝑖, 𝑗], we
have to store the value of k that is used.

𝒔[𝒊, 𝒋] 1 2 3 4 5
1 0 120/1 264/2 1080/2 1344/2
2 0 360/2 1320/2 1350/2
3 0 720/3 1140/4
4 0 1680/4
5 0

The k value for the solution 𝑚[1, 5] is 2, so we have (𝐴1 × 𝐴2 )(A3 × A4 × A5 )

Dr. A. K. Panda
 31

The k value for 𝑚[3, 5] is 4, so we have (𝐴1 × 𝐴2 )((A3 × A4 ) × A5 )

Therefore the optimal parenthesis is ((𝐴1 × 𝐴2 )((A3 × A4 ) × A5 )).

LONGEST COMMON SUBSEQUENCE

A subsequence of a string S, is a set of characters that appear in left-to-right order, but

not necessarily consecutively.

For Example: Consider a string 𝑆: 𝐴 𝐶 𝑇 𝑇 𝐺 𝐶 𝐺

𝐴 𝐶 𝑇 , 𝐴 𝑇 𝑇 𝐶 , 𝑇 , 𝐴 𝐶 𝑇 𝑇 𝐺 𝐶 are all subsequences of 𝑆 but, 𝑇 𝑇 𝐴 is not a subsequence

of 𝑆.

A common subsequence of two strings is a subsequence that appears in both strings.

Given two sequences 𝑆1 and 𝑆2 , a common subsequence is a subsequence that occurs in
both 𝑆1 and 𝑆2 .

A longest common subsequence is a common subsequence of maximal length.

Example:

Consider two strings:

𝑆1 : 𝐴 𝐵 𝐴 𝑍 𝐷 𝐶

𝑆2 : 𝐵 𝐴 𝐶 𝐵 𝐴 𝐷

The longest common subsequence is 𝐴 𝐵 𝐴 𝐷 of length 4.

Example:

Consider two strings:

𝑆1 : 𝐴 𝐴 𝐴 𝐶 𝐶 𝐺 𝑇 𝐺 𝐴 𝐺 𝑇 𝑇 𝐴 𝑇 𝑇 𝐶 𝐺 𝑇 𝑇 𝐶 𝑇 𝐴 𝐺 𝐴 𝐴

𝑆2 : 𝐶 𝐴 𝐶 𝐶 𝐶 𝐶 𝑇 𝐴 𝐴 𝐺 𝐺 𝑇 𝐴 𝐶 𝐶 𝑇 𝑇 𝑇 𝐺 𝐺 𝑇 𝑇 𝐶

The longest common subsequence is 𝐴 𝐶 𝐶 𝑇 𝐴 𝐺 𝑇 𝐴 𝐶 𝑇 𝑇 𝑇 𝐺 of length 13.

Dynamic programming Approach:

Let 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑚 } and 𝑌 = {𝑦1 , 𝑦2 , … , 𝑦𝑛 } be two strings of length 𝑚 and 𝑛 respectively.

Suppose that 𝑋𝑖 and 𝑌𝑗 be be the prefixes of X and Y of length i and j respectively.

Let 𝑐[𝑖, 𝑗] = length of LCS of 𝑋𝑖 and 𝑌𝑗

Dr. A. K. Panda
 32

𝑐 [𝑚, 𝑛] = length of LCS of X and Y which is the final solution.

Step 1: Characterize the structure of the optimal solution:

Case 1: If Last characters of both X and Y is same then the problem gets reduced to
finding the LCS of the remaining substrings of size m-1 and n-1 respectively and add 1
to get the output. 𝐿𝐶𝑆 (𝑋, 𝑌) = 𝐿𝐶𝑆 (𝑋𝑚−1 , 𝑌𝑛−1 ) + 1.

X = A B C B D A A

Y = B D C A B A

Case 2: If the last characters of two strings are not equal, there are two possibilities for
smaller sub-problems and we need to find maximum of them.

1. Find the length of the LCS by excluding the last character of string X and
including the last character of String Y.

X = A B C B D A B

Y = B D C A B A

𝐿𝐶𝑆 (𝑋, 𝑌) = 𝐿𝐶𝑆 (𝑋𝑚−1 , 𝑌)

2. Find the length of the LCS by including the last character of string X and
excluding the last character of String Y.

X = A B C B D A B

Y = B D C A B A

𝐿𝐶𝑆 (𝑋, 𝑌) = 𝐿𝐶𝑆 (𝑋, 𝑌𝑛−1 )

1 + 𝐿𝐶𝑆 (𝑋𝑚−1 , 𝑌𝑛−1 ) 𝑖𝑓 𝑥𝑚 = 𝑦𝑛

∴ 𝐿𝐶𝑆 (𝑋, 𝑌) = {
max(𝐿𝐶𝑆 (𝑋𝑚−1 , 𝑌), 𝐿𝐶𝑆 (𝑋, 𝑌𝑛−1 ) 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Step 2: Recursively define the value of an optimal solution.

1 + 𝑐 [𝑖 − 1, 𝑗 − 1] 𝑖𝑓 𝑥𝑖 = 𝑦𝑗
𝑐[𝑖, 𝑗] = {
max(𝑐 [𝑖 − 1, 𝑗], 𝑐[𝑖, 𝑗 − 1]) 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Dr. A. K. Panda
 33

Where 𝑐[𝑖, 𝑗] = length of LCS of 𝑋𝑖 and 𝑌𝑗

Step 3: Compute the value of optimal solution in a bottom-up fashion

Start with 𝑖 = 𝑗 = 0, Since 𝑋0 and 𝑌0 are empty strings, their LCS is always empty.
Hence 𝑐[0,0] = 0.

 LCS of empty string and any other string is empty. Hence for every 𝑖 and
𝑗: 𝑐[0, 𝑗] = 𝑐[𝑖, 0] = 0.
 Calculate other values of 𝑐[𝑖, 𝑗] by following procedure:

Case 1: If 𝑥𝑖 = 𝑦𝑗 , then length of LCS 𝑋𝑖 and 𝑌𝑗 equals to the length of LCS of

smaller strings 𝑋𝑖−1 and 𝑌𝑖−1 plus 1.

Case 2: If 𝑥𝑖 ≠ 𝑦𝑗 , then our solution is not improved, and the length of 𝐿𝐶𝑆(𝑋𝑖 , 𝑌𝑗 )
is the same as before (i.e. maximum of 𝐿𝐶𝑆(𝑋𝑖 , 𝑌𝑗−1 ) and 𝐿𝐶𝑆(𝑋𝑖−1 , 𝑌𝑗 ).

Step 4: Construct an optimum solution from computed information.

Working Procedure to find LCS of 𝑿 and 𝒀:

1. Create a blank table of dimension (𝑛 + 1, 𝑚 + 1) where n and m are the lengths

of X and Y respectively. Put 0’s in the first row and first column of the table.
2. If the character corresponding to the current row and current column are
matching, then fill the current cell by adding one to the diagonal element,
encircle it and point an arrow to the diagonal cell. Otherwise, take the maximum
value from the previous column and previous row element for filling the current
cell. Point an arrow to the cell with maximum value. If they are equal, point to
any of them.
3. Repeat step 2 until the table is filled.
4. The value in the last row and the last column is the length of the longest common
subsequence.
5. In order to find the longest common subsequence, start from the last element
and follow the direction of the arrow. The elements corresponding to encircled
cell form the longest common subsequence.

Example:
Find the LCS of the following two strings:
X: A C A D B
Y: C B D A

Solution:

Dr. A. K. Panda
 34

Initialization:

𝑌𝑗 C B D A
𝑋𝑖 0 0 0 0 0
A 0
0
C 0
0
Iteration
A 0 1:
0
D 0
0
B 0
0
0
Iteration 1:

𝑌𝑗 C B D A
𝑋𝑖 0 0 0 0 0
A 0 0 0 0 1
0
C 0
0 0
A 0 0
0
D 0 0
0 0
B 0
0
0
Iteration 2:

𝑌𝑗 C B D A
𝑋𝑖 0 0 0 0 0
A 0 0 0 0 1
0
C 0 1 1 1 1
0 00
A 0
0 00
D 0
0 10
0
B 0
0
0

Dr. A. K. Panda
 35

Iteration 3:

𝑌𝑗 C B D A
𝑋𝑖 0 0 0 0 0
A 0 0 0 0 1
0
C 0 1 1 1 1
0 00
A 0 1 1 1 2
0 00
D 0
0 10
0
B 0
0

Iteration 4: 0

𝑌𝑗 C B D A
𝑋𝑖 0 0 0 0 0
A 0 0 0 0 1
0
C 0 1 1 1 1
0 00
A 0 1 1 1 2
0 00
D 0
0 10
1 1 2 2
0
B 0
0
0
Iteration 5:
𝑌𝑗 C B D A
𝑋𝑖 0 0 0 0 0
A 0 0 0 0 1
0
C 0 1 1 1 1
0 00
A 0 1 1 1 2
0 00
D 0
0 10
1 1 2 2
0
B 0 1 2 2 2
0
0
Hence length of Longest common subsequence is 2 and the LCS can be obtained using
backtracking i. e. CA

Dr. A. K. Panda
 36

Example:
Find the LCS of the following two strings:
X: A G G T A B
Y: G X T X A Y B

Solution:
Initialization:

𝑌𝑗 G X T X A Y B
𝑋𝑖 0 0 0 0 0 0 0 0
A 0
0
G 0
0
0
G 0
T 0
0
A 0
0
B 0
0
0

Iteration 1:

𝑌𝑗 G X T X A Y B
𝑋𝑖 0 0 0 0 0 0 0 0
A 0 0 0 0 0 1 1 1
0
G 0
0
0
G 0
T 0
0
A 0
0
B 0
0
0

Dr. A. K. Panda
 37

Iteration 2:
𝑌𝑗 G X T X A Y B
𝑋𝑖 0 0 0 0 0 0 0 0
A 0 0 0 0 0 1 1 1
0
G 0 1 1 1 1 1 1 1
0
0
G 0 1
T 0
0
A 0
0
B 0
Iteration 3: 0
0

𝑌𝑗 G X T X A Y B
𝑋𝑖 0 0 0 0 0 0 0 0
A 0 0 0 0 0 1 1 1
0
G 0 1 1 1 1 1 1 1
0
0
G 0 1
1 1 1 1 1 1 1
T 0
0
A 0
0
B 0
0
0
Iteration 4:

𝑌𝑗 G X T X A Y B
𝑋𝑖 0 0 0 0 0 0 0 0
A 0 0 0 0 0 1 1 1
0
G 0 1 1 1 1 1 1 1
0
0
G 0 1
1 1 1 1 1 1 1
T 0 1 1 2 2 2 2 2
0
A 0
0
B 0
0
0

Dr. A. K. Panda
 38

Iteration 5:

𝑌𝑗 G X T X A Y B
𝑋𝑖 0 0 0 0 0 0 0 0
A 0 0 0 0 0 1 1 1
0
G 0 1 1 1 1 1 1 1
0
0
G 0 1
1 1 1 1 1 1 1
T 0 1 1 2 2 2 2 2
0
A 0 1 1 2 2 3 3 3
0
B 0
0
Iteration 6:
0

𝑌𝑗 G X T X A Y B
𝑋𝑖 0 0 0 0 0 0 0 0
A 0 0 0 0 0 1 1 1
0
G 0 1 1 1 1 1 1 1
0
0
G 0 1
1 1 1 1 1 1 1
T 0 1 1 2 2 2 2 2
0
A 0 1 1 2 2 3 3 3
0
B 0 1 1 2 2 3 3 4
0
0

Hence length of Longest common subsequence is 4 and the LCS can be obtained using
backtracking i. e. GTAB

Example:
Find the LCS of the following two strings:
X: B D C A B A
Y: A B C B D A B

Dr. A. K. Panda
 39

Solution:

Hence length of Longest common subsequence is 4 and the LCS can be obtained by
backtracking i. e. BCBA

Algorithm LCS:

By using this algorithm we can find length of the longest common subsequence of two
strings X and Y.

LCS-Length(X, Y)
{
m = length(X) // get the No. of symbols in X
n = length(Y) // get the No. of symbols in Y
for i= 1 to m do
c[i, 0] = 0; // special case: 𝑌0
for j = 1 to n do
c[0, j] = 0; // special case: 𝑋0
for i= 1 to m do // for all 𝑋𝑖
{
for j = 1 to n do // for all 𝑌𝑗
{
if (𝑋𝑖 == 𝑌𝑗 ) then
c[i,j] = c[i-1, j-1] + 1;
else
c[i,j] = max( c[i-1, j], c[i, j-1] )
}

Dr. A. K. Panda
 40

}
return c
}

Time Complexity:

Time Complexity of the algorithm = Time Complexity for initializing the table +Time
complexity for filling the table in buttom-up manner = 𝑂(𝑚 + 𝑛) + 𝑂(𝑚𝑛) = 𝑂(𝑚𝑛).

ASSEMBLY LINE SCHEDULING

It is a problem in operations management that involves determining the optimal

sequence of tasks or operations on an assembly line to minimize the production cost.

Problem Statement:

Suppose that a manufacturing company has two assembly lines.

Each assembly line has 𝑛 stations, numbered 𝑗 = 1,2. . . 𝑛 .

𝑆𝑖𝑗 = 𝑗𝑡ℎ station on line 1.

𝑎𝑖𝑗 =the assembly time taken at station 𝑆𝑖𝑗 .

A chassis must pass through each of the n stations in order before exiting the company.

The parallel stations of the two assembly lines perform the same task.

After it passes through station 𝑆𝑖𝑗 , it will continue to station 𝑆𝑖𝑗+1 unless it decides to
transfer to the other line.

Ordinarily, once a chassis enters a line, it will stay on that line until completion.
However, sometimes a rush order comes in, where we seek to complete a vehicle in the
fastest possible time.

Continuing on the same line incurs no extra cost, but transferring from line 𝑖 at station
𝑗 − 1 to station j on the other line takes time 𝑡𝑖𝑗

Each line also has an entry time, 𝑒𝑖 , the time taken for the chassis to enter line i, and an
exit time, 𝑥𝑖 , the time taken for the completed vehicle to leave line i.

If we are at any particular station, we will add the time of that specific station, and we
will move to the next station. We have two options for the next station, either we can go
to the next station of the same line, or we can go to the next station of another line. If we
choose to go to the next station of another line, we will have to add the transfer cost
between stations.

Dr. A. K. Panda
 41

Assembly Line

Station 𝑆1,1 Station 𝑆1,2 Station 𝑆1,𝑛−1 Station 𝑆1,𝑛

Station 𝑆2,1 Station 𝑆2,2 Station 𝑆2,𝑛−1 Station 𝑆2,𝑛

𝑒𝑖 = Entry time for line i

𝑎𝑖𝑗 = Assembly time for Station j, on line i
𝑡𝑖𝑗 = Transfer time away from line i, after station 𝑆𝑖𝑗
𝑥𝑖 = Exit time for vehicle to leave line i

Dynamic Programming Approach:

Objective: To find the optimal scheduling i.e., the fastest way from start to exit.

Let 𝑓𝑖 [𝑗] denotes the fastest way from start to station 𝑆𝑖𝑗 (station 𝑗 on line 𝑖).

And 𝑓 ∗ be the fastest time for the chassis to get all the way through the factory, arriving
at the exit as a finished vehicle.

𝑓 [𝑛] + 𝑥1
Final Solution: 𝑓 ∗ = min ( 1 )
𝑓2 [𝑛] + 𝑥2

𝑓1 [1] = 𝑒1 + 𝑎11
Base Case:
𝑓2 [1] = 𝑒2 + 𝑎21

Recursive Solution:

The chassis at station 𝑆1𝑗 can come either from station 𝑆1𝑗−1 or station 𝑆2𝑗−1 .

But if the chassis comes from 𝑆2𝑗−1 , it additionally incurs the transfer cost to change the
assembly line.

Thus, the recursive formula to reach the station j in assembly line i are as follows:

Dr. A. K. Panda
 42

𝑒1 + 𝑎11 𝑖𝑓 𝑗 = 1
𝑓1 [𝑗] = {
min[𝑓1 [𝑗 − 1] + 𝑎1𝑗 , 𝑓2 [𝑗 − 1] + 𝑡2,𝑗−1 + 𝑎1𝑗 ] 𝑖𝑓 𝑗 ≥ 2
𝑒2 + 𝑎21 𝑖𝑓 𝑗 = 1
𝑓2 [𝑗] = {
min[𝑓2 [𝑗 − 1] + 𝑎2𝑗 , 𝑓1 [𝑗 − 1] + 𝑡1,𝑗−1 + 𝑎2𝑗 ] 𝑖𝑓 𝑗 ≥ 2

Example:

Solve the following assembly line scheduling problem by using dynamic programming
technique:

𝑺𝟏𝟏 𝑺𝟏𝟐 𝑺𝟏𝟑 𝑺𝟏𝟒 𝑺𝟏𝟓 𝑺𝟏𝟔

7 9 3 4 8 4
3
2 3 1 3
4
2

Entry Exit

4
2 1 2 2 1 2

8 5 6 4 5 7

𝑺𝟐𝟏 𝑺𝟐𝟐 𝑺𝟐𝟑 𝑺𝟐𝟒 𝑺𝟐𝟓 𝑺𝟐𝟔

Solution:

Initialization (j=1)

𝑓1 [1] = 𝑒1 + 𝑎11 = 2 + 7 = 9
𝑓2 [1] = 𝑒2 + 𝑎21 = 4 + 8 = 12

j 1 2 3 4 5 6
𝑓1 [𝑗] 9
𝑓2 [𝑗] 12

Iteration 1 (j=2)

𝑓1 [2] = min[9 + 9, 12 + 2 + 9] = 18
𝑓2 [2] = min[12 + 5, 9 + 2 + 5] = 16

j 1 2 3 4 5 6 𝑗 2 3 4 5 6
𝑓1 [𝑗] 9 18 𝐿1 [𝑗] 1
𝑓2 [𝑗] 12 16 𝐿2 [𝑗] 1

Dr. A. K. Panda
 43

Iteration 2 (j=3)

𝑓1 [3] = min[18 + 3, 16 + 1 + 3] = 20
𝑓2 [3] = min[16 + 6, 18 + 3 + 6] = 22

j 1 2 3 4 5 6 𝑗 2 3 4 5 6
𝑓1 [𝑗] 9 18 20 𝐿1 [𝑗] 1 2
𝑓2 [𝑗] 12 16 22 𝐿2 [𝑗] 1 2

Iteration 3 (j=4)

𝑓1 [4] = min[20 + 4, 22 + 2 + 4] = 24
𝑓2 [4] = min[22 + 4, 20 + 1 + 4] = 25

j 1 2 3 4 5 6 𝑗 2 3 4 5 6
[ ]
𝑓1 𝑗 9 18 20 24 𝐿1 [𝑗] 1 2 1
𝑓2 [𝑗] 12 16 22 25 𝐿2 [𝑗] 1 2 1

Iteration 4 (j=5)

𝑓1 [5] = min[24 + 8, 22 + 2 + 4] = 32
𝑓2 [5] = min[25 + 5, 24 + 3 + 5] = 30

j 1 2 3 4 5 6 𝑗 2 3 4 5 6
𝑓1 [𝑗] 9 18 20 24 32 𝐿1 [𝑗] 1 2 1 1
𝑓2 [𝑗] 12 16 22 25 30 𝐿2 [𝑗] 1 2 1 2

Iteration 5 (j=6)

𝑓1 [6] = min[32 + 4, 30 + 1 + 4] = 35
𝑓2 [6] = min[30 + 7, 32 + 4 + 7] = 37

j 1 2 3 4 5 6 𝑗 2 3 4 5 6
𝑓1 [𝑗] 9 18 20 24 32 35 𝐿1 [𝑗] 1 2 1 1 2
𝑓2 [𝑗] 12 16 22 25 30 37 𝐿2 [𝑗] 1 2 1 2 2

Optimal Schedule:

𝑓1 [𝑛] + 𝑥1 35 + 3 = 38
𝑓 ∗ = min ( ) = min ( ) = 38
𝑓2 [𝑛] + 𝑥2 37 + 2 = 49

Tracing out the optimal path:

The optimal path can be traced by moving backward with values of L-table.

Dr. A. K. Panda
 44

𝑗 2 3 4 5 6
𝐿1 [𝑗] 1 2 1 1 2 𝐿∗ = 1
𝐿2 [𝑗] 1 2 1 2 2

Thus, the optimal schedule is:

𝑆𝑡𝑎𝑟𝑡 → 𝑒1 → 𝑆11 → 𝑡11 → 𝑆22 → 𝑡22 → 𝑆13 → 𝑡13 → 𝑆24 → 𝑆25 → 𝑡25 → 𝑆16 → 𝑥1
→ 𝑒𝑥𝑖𝑡

𝑺𝟏𝟏 𝑺𝟏𝟐 𝑺𝟏𝟑 𝑺𝟏𝟒 𝑺𝟏𝟓 𝑺𝟏𝟔

7 9 3 4 8 4
3
2 3 1 3
4
2

Entry Exit

4
2 1 2 2 1 2

8 5 6 4 5 7

𝑺𝟐𝟏 𝑺𝟐𝟐 𝑺𝟐𝟑 𝑺𝟐𝟒 𝑺𝟐𝟓 𝑺𝟐𝟔

Dr. A. K. Panda
 45

Algorithm:

fastest−way (𝒂, 𝒕, 𝒆, 𝒙, 𝒏) //Assembly costs, Transfer costs, Entry costs, Exit cost, Stations
𝑓1 [1] ← 𝑒1 + 𝑎1,1
𝑓2 [1] ← 𝑒2 + 𝑎1,2
for j ← 2 to n do
if 𝑓1 [𝑗 − 1] + 𝑎1,𝑗 ≤ 𝑓2 [𝑗 − 1] + 𝑡2,𝑗−1 + 𝑎1,𝑗 then
𝑓1 [𝑗] ← 𝑓1 [𝑗 − 1] + 𝑎1,𝑗
𝑙1 [𝑗] ← 1
else
𝑓1 [𝑗] ← 𝑓2 [𝑗 − 1] + 𝑡2,𝑗−1 + 𝑎1,𝑗
𝑙1 [𝑗] ← 2
if 𝑓2 [𝑗 − 1] + 𝑎2,𝑗 ≤ 𝑓1 [𝑗 − 1] + 𝑡1,𝑗−1 + 𝑎2,𝑗 then
𝑓2 [j] ← 𝑓2 [𝑗 − 1] + 𝑎2,𝑗
𝑙2 [𝑗] ← 2
else
𝑓2 [𝑗] ← 𝑓1 [𝑗 − 1] + 𝑡1,𝑗−1 + 𝑎2,𝑗
𝑙2 [𝑗] ← 1
if 𝑓1 [𝑛] + 𝑥1 ≤ 𝑓2 [𝑛] + 𝑥2 then
𝑓 ∗ = 𝑓1 [𝑛] + 𝑥1
𝑙∗ =1
else
𝑓 ∗ = 𝑓2 [n] + 𝑥2
𝑙 ∗ =2
return 𝑓𝑖 , 𝑓 ∗ , 𝑙𝑖 , 𝑙 ∗

Time complexity: 𝑶(𝟐𝒏 )

Printing out the path:

Algorithm:
print−stations(𝒍∗ , 𝒍𝒊 , 𝒏) //Final line, Array of lines, Number of stations
𝑖=𝑙 ∗
// Initialise final exit line
print “𝑙𝑖𝑛𝑒 ” + 𝑖 + “, 𝑠𝑡𝑎𝑡𝑖𝑜𝑛 ” + 𝑛 // Print last station we exit from
for j = n downto 2 do
𝑖 = 𝐿𝑖 [𝑗] // Set line number to print
print “𝑙𝑖𝑛𝑒 ” + 𝑖 + “, 𝑠𝑡𝑎𝑡𝑖𝑜𝑛 ” + 𝑗 − 1 // Prints line, stations 𝑗 − 1 to 1

Dr. A. K. Panda