DEPARTMENT OF ELECTRICAL AND ELECTRONICS ENGINEERING

22EEE545- COMPETITIVE CODING

MODULE 5 : ADVANCED ALGORITHMS

Sorting Algorithms: Merge Sort and Heap Sort, Searching Algorithms:

Binary Search and Ternary Search, Dynamic Programming: Knapsack
Problem, Longest Common Subsequence
Sorting Algorithms
Merge Sort
Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the
divide-and-conquer approach. It works by recursively dividing the input array into two halves,
recursively sorting the two halves and finally merging them back together to obtain the sorted
array.

How does Merge Sort work?

Here's a step-by-step explanation of how merge sort works:
Divide: Divide the list or array recursively into two halves until it can no more be divided.
Conquer: Each subarray is sorted individually using the merge sort algorithm.
Merge: The sorted subarrays are merged back together in sorted order. The process continues until
all elements from both subarrays have been merged.

2
Let's look at the working of above example:
Divide:

[38, 27, 43, 10] is divided into [38, 27 ] and [43, 10] .

[38, 27] is divided into [38] and [27] .

[43, 10] is divided into [43] and [10] .
Conquer:
[38] is already sorted.
[27] is already sorted.
[43] is already sorted.
[10] is already sorted.
Merge:
Merge [38] and [27] to get [27, 38] .
Merge [43] and [10] to get [10,43] .
Merge [27, 38] and [10,43] to get the final sorted list [10, 27, 38, 43]
Therefore, the sorted list is [10, 27, 38, 43].

3
C program of Merge sort
#include <stdio.h>
#include <stdlib.h>
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
// Copy data to temp arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temp arrays back into arr[l..r
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[],
// if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[],

4
 // if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// l is for left index and r is right index of the
// sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r){
if (l < r) {
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// Driver code
int main(){

int arr[] = {38, 27, 43, 10};

int arr_size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, arr_size - 1);
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Output

10 27 38 43

Advantages
• Consistent Time Complexity: O(n log n) time complexity in all cases (best,
• average, worst).
• Stable Sorting: Maintains the relative order of equal elements.
• Efficient for Large Data Sets: Handles large arrays or lists efficiently.
• Parallelizable: Can be easily parallelized due to its divide-and-conquer nature.

5
 • Predictable Performance: Performance does not degrade based on input data
characteristics.

Disadvantages
• High Space Complexity: Requires O(n) additional space for merging.
• Complex Implementation: More complex to implement compared to simpler
• algorithms like insertion sort or selection sort.
• Not In-Place: Uses extra space for temporary subarrays, which can be a
• limitation for memory-constrained environments.
• Overhead for Small Arrays: For small arrays, the overhead of recursive calls
• and merging can make it slower than simpler algorithms like insertion sort.

Applications of Merge Sort:

• Sorting large datasets
• External sorting (when the dataset is too large to fit in memory)
• Inversion counting
• Merge Sort and its variations are used in library methods of programming languages.
• Its variation TimSort is used in Python, Java Android and Swift. The main reason why it is
preferred to sort non-primitive types is stability which is not there in QuickSort.
• [Link] in Java uses QuickSort while [Link] uses MergeSort.
• It is a preferred algorithm for sorting Linked lists.
• It can be easily parallelized as we can independently sort subarrays and then merge.
• The merge function of merge sort to efficiently solve the problems like union and
intersection of two sorted arrays.

Heap Sort
Heap sort is a comparison-based sorting technique based on Binary Heap Data Structure. It can be
seen as an optimization over selection sort where we first find the max (or min) element and swap
it with the last (or first). We repeat the same process for the remaining elements. In Heap Sort, we
use Binary Heap so that we can quickly find and move the max element in O(Log n) instead of
O(n) and hence achieve the O(n Log n) time complexity.

Heap Sort Algorithm

First convert the array into a max heap using heapify, Please note that this happens in-place. The
array elements are re-arranged to follow heap properties. Then one by one delete the root node of
the Max-heap and replace it with the last node and heapify. Repeat this process while size of heap
is greater than 1.
• Rearrange array elements so that they form a Max Heap.

6
 • Repeat the following steps until the heap contains only one element:
o Swap the root element of the heap (which is the largest element in current heap)
with the last element of the heap.
o Remove the last element of the heap (which is now in the correct position). We
mainly reduce heap size and do not remove element from the actual array.
o Heapify the remaining elements of the heap.
• Finally we get sorted array.

Detailed Working of Heap Sort

Step 1: Treat the Array as a Complete Binary Tree
We first need to visualize the array as a complete binary tree. For an array of size n, the root is at
index 0, the left child of an element at index i is at 2i + 1, and the right child is at 2i + 2.

Step 2: Build a Max Heap

7
8
Step 3: Sort the array by placing largest element at end of unsorted array.

9
10
C program of Heap sort
#include <stdio.h>
// To heapify a subtree rooted with node i
// which is an index in arr[].
void heapify(int arr[], int n, int i) {
// Initialize largest as root
int largest = i;
// left index = 2*i + 1
int l = 2 * i + 1;
// right index = 2*i + 2
int r = 2 * i + 2;
// If left child is larger than root
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
// If right child is larger than largest so far

11
 if (r < n && arr[r] > arr[largest]) {
largest = r;
}
// If largest is not root
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

// Main function to do heap sort

void heapSort(int arr[], int n) {
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// A utility function to print array of size n
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

// Driver's code
int main() {
int arr[] = {9, 4, 3, 8, 10, 2, 5};

12
 int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
return 0;
}
Output
Sorted array is
2 3 4 5 8 9 10

Complexity Analysis of Heap Sort

Time Complexity: O(n log n)
Auxiliary Space: O(log n), due to the recursive call stack. However, auxiliary space can be O(1)
for iterative implementation.

Advantages of Heap Sort

• Efficient Time Complexity: Heap Sort has a time complexity of O(n log n) in all cases.
This makes it efficient for sorting large datasets. The log n factor comes from the height of
the binary heap, and it ensures that the algorithm maintains good performance even with a
large number of elements.
• Memory Usage: Memory usage can be minimal (by writing an iterative heapify() instead
of a recursive one). So apart from what is necessary to hold the initial list of items to be
sorted, it needs no additional memory space to work
• Simplicity: It is simpler to understand than other equally efficient sorting algorithms
because it does not use advanced computer science concepts such as recursion.
Disadvantages of Heap Sort
• Costly: Heap sort is costly as the constants are higher compared to merge sort even if the
time complexity is O(n Log n) for both.
• Unstable: Heap sort is unstable. It might rearrange the relative order.
• Inefficient: Heap Sort is not very efficient because of the high constants in the time
complexity.

13
Searching Algorithms:
Binary Search
Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly dividing the
search interval in half. The idea of binary search is to use the information that the array is sorted
and reduce the time complexity to O(log N).
Conditions to apply Binary Search Algorithm in a Data Structure
To apply Binary Search algorithm:
• The data structure must be sorted.
• Access to any element of the data structure should take constant time.
Binary Search Algorithm
Below is the step-by-step algorithm for Binary Search:
• Divide the search space into two halves by finding the middle index "mid".
• Compare the middle element of the search space with the key.
• If the key is found at middle element, the process is terminated.
• If the key is not found at middle element, choose which half will be used as the next search
space.
o If the key is smaller than the middle element, then the left side is used for next
search.
o If the key is larger than the middle element, then the right side is used for next
search.
• This process is continued until the key is found or the total search space is exhausted.

How does Binary Search Algorithm work?

To understand the working of binary search, consider the following illustration:
Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.

14
C program to implement iterative Binary Search
#include <stdio.h>
// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if x is present at mid
if (arr[mid] == x)
return mid;
// If x greater, ignore left half
if (arr[mid] < x)
low = mid + 1;
// If x is smaller, ignore right half

15
 else
high = mid - 1;
}

// If we reach here, then element was not present

return -1;
}

// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if(result == -1) printf("Element is not present in array");
else printf("Element is present at index %d",result);
}

Output
Element is present at index 3

Time Complexity: O(log N)

Auxiliary Space: O(1)

C program to implement recursive Binary Search

#include <stdio.h>
// A recursive binary search function. It returns
// location of x in given array arr[low..high] is present,
// otherwise -1
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - low) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray

16
 if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, x);
}

// We reach here when element is not

// present in array
return -1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1) printf("Element is not present in array");
else printf("Element is present at index %d", result);
return 0;
}
Output
Element is present at index 3

Complexity Analysis of Binary Search Algorithm

• Time Complexity:
o Best Case: O(1)
o Average Case: O(log N)
o Worst Case: O(log N)
• Auxiliary Space: O(1), If the recursive call stack is considered then the auxiliary space
will be O(log N).
Applications of Binary Search Algorithm
• Binary search can be used as a building block for more complex algorithms used in
machine learning, such as algorithms for training neural networks or finding the optimal
hyperparameters for a model.
• It can be used for searching in computer graphics such as algorithms for ray tracing or
texture mapping.
• It can be used for searching a database.

17
Ternary Search
Computer systems use different methods to find specific data. There are various search algorithms,
each better suited for certain situations. For instance, a binary search divides information into two
parts, while a ternary search does the same but into three equal parts. It's worth noting that ternary
search is only effective for sorted data. In this article, we're going to uncover the secrets of Ternary
Search – how it works, why it's faster in some situations.

What is the Ternary Search?

Ternary search is a search algorithm that is used to find the position of a target value within a sorted
array. It operates on the principle of dividing the array into three parts instead of two, as in binary
search. The basic idea is to narrow down the search space by comparing the target value with
elements at two points that divide the array into three equal parts.
mid1 = l + (r-l)/3
mid2 = r - (r-l)/3

When to use Ternary Search:

• When you have a large ordered array or list and need to find the position of a specific value.
• When you need to find the maximum or minimum value of a function.
• When you need to find bitonic point in a bitonic sequence.
• When you have to evaluate a quadratic expression

Working of Ternary Search:

The concept involves dividing the array into three equal segments and determining in which
segment the key element is located. It works similarly to a binary search, with the distinction of
reducing time complexity by dividing the array into three parts instead of two.
Below are the step-by-step explanation of working of Ternary Search:
1. Initialization:
• Set two pointers, left and right, initially pointing to the first and last elements of
our search space.
2. Divide the search space:
• Calculate two midpoints, mid1 and mid2, dividing the current search space into
three roughly equal parts:
• mid1 = left + (right - left) / 3
• mid2 = right - (right - left) / 3
• The array is now effectively divided into [left, mid1], (mid1, mid2), and [mid2,
right].
3. Comparison with Target:.
• If the target is equal to the element at mid1 or mid2, the search is successful, and
the index is returned
• If the target is less than the element at mid1, update the right pointer to mid1 - 1.

18
 •If the target is greater than the element at mid2, update the left pointer to mid2 +
1.
• If the target is between the elements at mid1 and mid2, update the left pointer
to mid1 + 1 and the right pointer to mid2 - 1.
4. Repeat or Conclude:
• Repeat the process with the reduced search space until the target is found or the
search space becomes empty.
• If the search space is empty and the target is not found, return a value indicating
that the target is not present in the array.

C program to illustrate recursive approach to ternary search

#include <stdio.h>
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
if (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
19
 return mid1;
}
if (ar[mid2] == key) {
return mid2;
}

// Since key is not present at mid,

// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
// The key lies in between mid1 and mid2
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
// Key not found
return -1;
}
// Driver code
int main()
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// end element index
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;

20
 // Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d\n", key, p);

// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d", key, p);
}
Output
Index of 5 is 4
Index of 50 is -1

Time Complexity: O(2 * log3n)

Auxiliary Space: O(log3n)

C program to illustrate iterative approach to ternary search

#include <stdio.h>
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
while (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region

21
 if (key < ar[mid1]) {
// The key lies in between l and mid1
r = mid1 - 1;
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
l = mid2 + 1;
}
else {
// The key lies in between mid1 and mid2
l = mid1 + 1;
r = mid2 - 1;
}
}
// Key not found
return -1;
}
// Driver code
int main()
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// end element index
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d\n", key, p);
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);

22
 // Print the result
printf("Index of %d is %d", key, p);
}
Output
Index of 5 is 4
Index of 50 is -1

Time Complexity: O(2 * log3n), where n is the size of the array.

Auxiliary Space: O(1)

Complexity Analysis of Ternary Search:

Time Complexity:
Worst case: O(log3N)
Average case: Θ(log3N)
Best case: Ω(1)
Auxiliary Space: O(1)

Binary search Vs Ternary Search:

The time complexity of the binary search is less than the ternary search as the number of
comparisons in ternary search is much more than binary search. Binary Search is used to find the
maxima/minima of monotonic functions where as Ternary Search is used to find the
maxima/minima of unimodal functions.
Note: We can also use ternary search for monotonic functions but the time complexity will be
slightly higher as compared to binary search.

Advantages:
Ternary search can find maxima/minima for unimodal functions, where binary search is not
applicable.
Ternary Search has a time complexity of O(2 * log3n), which is more efficient than linear search
and comparable to binary search.
Fits well with optimization problems.

Disadvantages:
Ternary Search is only applicable to ordered lists or arrays, and cannot be used on unordered or
non-linear data sets.
Ternary Search takes more time to find maxima/minima of monotonic functions as compared to
Binary Search.

23
Dynamic Programming
Dynamic Programming is a commonly used algorithmic technique used to optimize
recursive solutions when same subproblems are called again.
The core idea behind DP is to store solutions to subproblems so that each is solved only
once.
To solve DP problems, we first write a recursive solution in a way that there are overlapping
subproblems in the recursion tree (the recursive function is called with the same parameters
multiple times)
To make sure that a recursive value is computed only once (to improve time taken by
algorithm), we store results of the recursive calls.
There are two ways to store the results, one is top down (or memoization) and other is
bottom up (or tabulation).

When to Use Dynamic Programming (DP)?

Dynamic programming is used for solving problems that consists of the following
characteristics:
1. Optimal Substructure:
The property Optimal substructure means that we use the optimal results of subproblems
to achieve the optimal result of the bigger problem.
Example:
Consider the problem of finding the minimum cost path in a weighted graph from a source
node to a destination node. We can break this problem down into smaller subproblems:
• Find the minimum cost path from the source node to each intermediate node.
• Find the minimum cost path from each intermediate node to the destination node.
• The solution to the larger problem (finding the minimum cost path from the source
node to the destination node) can be constructed from the solutions to these smaller
subproblems.
2. Overlapping Subproblems:
The same subproblems are solved repeatedly in different parts of the problem refer to
Overlapping Subproblems Property in Dynamic Programming

Example:
Consider the problem of computing the Fibonacci series. To compute the Fibonacci number
at index n, we need to compute the Fibonacci numbers at indices n-1 and n-2. This means
that the subproblem of computing the Fibonacci number at index n-2 is used twice (note

24
that the call for n - 1 will make two calls, one for n-2 and other for n-3) in the solution to
the larger problem of computing the Fibonacci number at index n.
You may notice overlapping subproblems highlighted in the second recursion tree for Nth
Fibonacci diagram shown below.

Approaches of Dynamic Programming (DP):

1. Top-Down Approach (Memoization):

In the top-down approach, also known as memoization, we keep the solution recursive and
add a memoization table to avoid repeated calls of same subproblems.
• Before making any recursive call, we first check if the memoization table already
has solution for it.
• After the recursive call is over, we store the solution in the memoization table.

2. Bottom-Up Approach (Tabulation):

In the bottom-up approach, also known as tabulation, we start with the smallest
subproblems and gradually build up to the final solution.
• We write an iterative solution (avoid recursion overhead) and build the solution in
bottom-up manner.
• We use a dp table where we first fill the solution for base cases and then fill the
remaining entries of the table using recursive formula.
• We only use recursive formula on table entries and do not make recursive calls.

25
Example of Dynamic Programming (DP)
Example 1: Consider the problem of finding the Fibonacci sequence:
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Brute Force Approach: To find the nth Fibonacci number using a brute force approach, you
would simply add the (n-1)th and (n-2)th Fibonacci numbers.
// C program to find fibonacci number using recursion.
#include <stdio.h>
// Function to find nth fibonacci number
int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
int main() {
int n = 5;
printf("%d", fib(n));
return 0;
}

How will Dynamic Programming (DP) Work?

The above recursion tree with overlapping subproblems highlighted with same color. We
can clearly see that that recursive solution is doing a lot work again and again which is
causing the time complexity to be exponential. Imagine time taken for computing a large
Fibonacci number.

26
 • Identify Subproblems: Divide the main problem into smaller, independent
subproblems, i.e., F(n-1) and F(n-2)
• Store Solutions: Solve each subproblem and store the solution in a table or array
so that we do not have to recompute the same again.
• Build Up Solutions: Use the stored solutions to build up the solution to the main
problem. For F(n), look up F(n-1) and F(n-2) in the table and add them.
• Avoid Recomputation: By storing solutions, DP ensures that each subproblem (for
example, F(2)) is solved only once, reducing computation time.

Using Memoization Approach - O(n) Time and O(n) Space

To achieve this in our example we simply take an memo array initialized to -1. As we make
a recursive call, we first check if the value stored in the memo array corresponding to that
position is -1. The value -1 indicates that we haven't calculated it yet and have to recursively
compute it. The output must be stored in the memo array so that, next time, if the same
value is encountered, it can be directly used from the memo array.

Common Algorithms that Use DP:

• Longest Common Subsequence (LCS): This is used in day to day life to find difference
between two files (diff utility)
• Edit Distance : Checks how close to strings are. Can we be useful in implementing
Google's did you mean type feature.
• Longest Increasing Subsequence : There are plenty of variations of this problem that
arise in real world.

27
• Bellman–Ford Shortest Path: Finds the shortest path from a given source to all other
vertices.
• Floyd Warshall : Finds shortest path from every pair of vertices.
• Knapsack Problem: Determines the maximum value of items that can be placed in a
knapsack with a given capacity.
• Matrix Chain Multiplication: Optimizes the order of matrix multiplication to minimize
the number of operations.
• Fibonacci Sequence: Calculates the nth Fibonacci number.

Advantages of Dynamic Programming (DP)

Dynamic programming has a wide range of advantages, including:
• Avoids recomputing the same subproblems multiple times, leading to significant
time savings.
• Ensures that the optimal solution is found by considering all possible combinations.

Applications of Dynamic Programming (DP)

Dynamic programming has a wide range of applications, including:
• Optimization: Knapsack problem, shortest path problem, maximum subarray
problem
• Computer Science: Longest common subsequence, edit distance, string matching
• Operations Research: Inventory management, scheduling, resource allocation

Knapsack Problem
The Knapsack problem is an example of the combinational optimization problem. This
problem is also commonly known as the "Rucksack Problem". The name of the problem is
defined from the maximization problem as mentioned below:
Given a bag with maximum weight capacity of W and a set of items, each having a weight
and a value associated with it. Decide the number of each item to take in a collection such
that the total weight is less than the capacity and the total value is maximized.

Types of Knapsack Problem:

The knapsack problem can be classified into the following types:
1. Fractional Knapsack Problem
2. 0/1 Knapsack Problem
3. Bounded Knapsack Problem
4. Unbounded Knapsack Problem

28
1. Fractional Knapsack Problem
The Fractional Knapsack problem can be defined as follows:
Given the weights and values of N items, put these items in a knapsack of capacity W to
get the maximum total value in the knapsack. In Fractional Knapsack, we can break items
for maximizing the total value of the knapsack.
Given two arrays, val[] and wt[], representing the values and weights of item respectively,
and an integer capacity representing the maximum weight a knapsack can hold, we have to
determine the maximum total value that can be achieved by putting the items in the
knapsack without exceeding its capacity.
Items can also be taken in fractional parts if required.

Examples:
Input: val[] = [60, 100, 120], wt[] = [10, 20, 30], capacity = 50
Output: 240
Explanation: We will take the items of weight 10kg and 20kg and 2/3 fraction of 30kg.
Hence total value will be 60 + 100 + (2/3) * 120 = 240.
Input: val[] = [500], wt[] = [30], capacity = 10
Output: 166.667

Steps to solve the problem:

1. Calculate the ratio (value/weight) for each item.
2. Sort all the items in decreasing order of the ratio.
3. Iterate through items:
4. if the current item fully fits, add its full value and decrease capacity otherwise, take
the fractional part that fits and add proportional value.
5. Stop once the capacity becomes zero.

2. 0/1 Knapsack Problem

The 0/1 Knapsack problem can be defined as follows:
We are given N items where each item has some weight (wi) and value (vi) associated with
it. We are also given a bag with capacity W. The target is to put the items into the bag such
that the sum of values associated with them is the maximum possible.
Note that here we can either put an item completely into the bag or cannot put it at all.
Mathematically the problem can be expressed as:
Maximize ∑i=1Nvixi ∑i=1Nvixi subject to ∑i=1Nwixi≤W ∑i=1Nwi
xi≤W and xi ∈ {0, 1}

29
Given n items where each item has some weight and profit associated with it and also given
a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put
the items into the bag such that the sum of profits associated with them is the maximum
possible.
Note: The constraint here is we can either put an item completely into the bag or cannot
put it at all [It is not possible to put a part of an item into the bag].
Input: W = 4, profit[] = [1, 2, 3], weight[] = [4, 5, 1]
Output: 3
Explanation: There are two items which have weight less than or equal to 4. If we select
the item with weight 4, the possible profit is 1. And if we select the item with weight 1, the
possible profit is 3. So the maximum possible profit is 3. Note that we cannot put both the
items with weight 4 and 1 together as the capacity of the bag is 4.
Input: W = 3, profit[] = [1, 2, 3], weight[] = [4, 5, 6]
Output: 0

3. Bounded Knapsack Problem

The Bounded Knapsack problem can be defined as follows:
Given N items, each item having a given weight wi and a value vi, the task is to maximize
the value by selecting a maximum of K items adding up to a maximum weight W.
Mathematically the problem can be expressed as:
Maximize ∑i=1Nvixi ∑i=1Nvixi subject to ∑i=1Nwixi≤W ∑i=1Nwixi
≤W and xi ∈ {0, 1, . . . , K}
Given N items, each item having a given weight Ci and a profit value Pi, the task is to
maximize the profit by selecting a maximum of K items adding up to a maximum weight
W.

Examples:
Input: N = 5, P[] = {2, 7, 1, 5, 3}, C[] = {2, 5, 2, 3, 4}, W = 8, K = 2.
Output: 12
Explanation:
Here, the maximum possible profit is when we take 2 items: item2 (P[1] = 7 and C[1] = 5)
and item4 (P[3] = 5 and C[3] = 3).
Hence, maximum profit = 7 + 5 = 12
Input: N = 5, P[] = {2, 7, 1, 5, 3}, C[] = {2, 5, 2, 3, 4}, W = 1, K = 2
Output: 0
Explanation: All weights are greater than 1. Hence, no item can be picked.

30
Approach: The dynamic programming approach is preferred over the general recursion
approach. Let us first verify that the conditions of DP are still satisfied.
1. Overlapping sub-problems: When the recursive solution is tried, 1 item is added
first and the solution set is (1), (2), ...(n). In the second iteration we have (1, 2) and
so on where (1) and (2) are recalculated. Hence there will be overlapping solutions.
2. Optimal substructure: Overall, each item has only two choices, either it can be
included in the solution or denied. For a particular subset of z elements, the solution
for (z+1)th element can either have a solution corresponding to the z elements or
the (z+1)th element can be added if it doesn't exceed the knapsack constraints.
Either way, the optimal substructure property is satisfied.

4. Unbounded Knapsack Problem

The Unbounded Knapsack problem can be defined as follows:
Given a knapsack weight W and a set of N items with certain value vi and weight wi, we
need to calculate the maximum amount that could make up this quantity exactly. This is
different from 0/1 Knapsack problem, here we are allowed to use an unlimited number of
instances of an item.
Mathematically the problem can be expressed as:
Maximize ∑i=1Nvixi ∑i=1Nvixi subject to ∑i=1Nwixi≤W ∑i=1Nwi
xi≤W and xiϵZ xiϵZ and xi ≥ 0.

[Link] Fractional Knapsack

Given the weights and values of n items, the task is to put these items in a knapsack of
capacity W to get the maximum total value in the knapsack, we can repeatedly put the same
item and we can also put a fraction of an item.
Examples:
Input: val[] = {14, 27, 44, 19}, wt[] = {6, 7, 9, 8}, W = 50
Output: 244.444
Input: val[] = {100, 60, 120}, wt[] = {20, 10, 30}, W = 50
Output: 300

Approach: The idea here is to just find the item which has the largest value to weight ratio.
Then fill the whole knapsack with this item only, in order to maximize the final value of
the knapsack.

31
Variations of Knapsack Problem:
There are several variations possible for the Knapsack Problem. Some of the well-known
variations are provided below:

1. Multi-objective Knapsack problem:

In this variation, the goal of filling the knapsack changes. Instead of maximizing only the
value, there can be several other objectives.
For example: Consider you are organizing a music show in a hall that has a capacity of
10,000. You are organizing a show and the size of the audience depends on the popularity
of the singers. Also, the more popular the singer is, the more the fee. You want to maximize
the profit and minimize the amount spend on the singer simultaneously and also want to
bring as many singers as possible.

2. Multi-dimensional Knapsack problem:

In this variation of the problem, the weight of any item i is given by an M dimensional
vector {wi1, wi2, . . . wiM} and similarly, the capacity of the knapsack is also an M
dimensional vector {W1, W2, . . . , WM}.

3. Multiple Knapsack problem:

This variation of the knapsack problem is similar to the Bin packing algorithm. The
difference in both the problem is here we can pick a subset of the items whereas, in the Bin
Packing problem, we have to pack all the items in any of the bins. The idea is that there are
multiple knapsacks which may seem like adding capacity to the initial knapsack, but it is
not similar to that at all.

4. Quadratic Knapsack problem:

This variation has the goal of achieving the maximum value of a quadratic objective
function that is subjected to binary and linear capacity constraints.

5. Geometric Knapsack problem:

In this variation, there is a set of rectangles with different values and a rectangular
knapsack. The goal is to pack the largest possible value into the knapsack.

32
Applications of the Knapsack Problem:
The Knapsack problem has several real-life applications. Some of them are mentioned
here:
• One of the early applications of the Knapsack problem was in construction and
scoring of exams in which the test takers have a choice as to which questions they
answer.
• The subset sum problem is solved using the concept of the Knapsack problem.
• The multiple objective variations of the Knapsack problem is frequently used for
transportation logistics optimization problems.
• The multiple knapsack problem is often used in many loading and scheduling
algorithms in Operational Research.

33
QUESTION BANK

1. What is the fundamental approach used by Merge Sort?

2. What are the three main steps of the Merge Sort algorithm?
3. Explain the "Divide" step of Merge Sort with an example.
4. What is the time complexity of Merge Sort in the best, average, and worst cases?
5. Why is Merge Sort considered a stable sorting algorithm?
6. List three advantages of using Merge Sort.
7. What is the primary disadvantage of Merge Sort regarding space complexity?
8. For what kind of data sets is Merge Sort particularly efficient?
9. In what real-world applications is Merge Sort used?
10. Why is Merge Sort a preferred algorithm for sorting linked lists?
11. What data structure is Heap Sort based on?
12. How does Heap Sort work as an optimization over Selection Sort?
13. Describe the two main steps of the Heap Sort algorithm.
14. What is the time complexity of Heap Sort?
15. What is the auxiliary space complexity of Heap Sort, and how can it be made O(1)?
16. Why is Heap Sort considered an unstable sorting algorithm?
17. Name two advantages and two disadvantages of Heap Sort.
18. Explain the
heapify function's role in the Heap Sort algorithm.
19. How do you visualize an array as a complete binary tree for Heap Sort?
20. Why might Heap Sort be considered "costly" compared to Merge Sort, even with the
same time complexity?
21. What are the two main conditions required to apply the Binary Search algorithm?
22. Explain the step-by-step process of Binary Search.
23. What is the time complexity of an iterative Binary Search?
24. How does Ternary Search differ from Binary Search?
25. What is a "unimodal" function, and why is Ternary Search used for it?

34
26. What is Dynamic Programming, and what is its core idea?
27. What are the two properties that a problem must have to be solved using Dynamic
Programming?
28. Differentiate between the Top-Down (Memoization) and Bottom-Up (Tabulation)
approaches of Dynamic Programming.
29. State the Knapsack Problem.
30. What is the key difference between the 0/1 Knapsack Problem and the Fractional
Knapsack Problem?
Programs:
1. Write a C program to implement Merge Sort for an array of integers.
2. Write a C program to implement Heap Sort for an array of integers.
3. Write a C program to find an element in a sorted array using an iterative Binary Search.
4. Write a C program to find an element in a sorted array using a recursive Binary Search.
5. Write a C program to find an element in a sorted array using a recursive Ternary Search.
6. Write a C program to find an element in a sorted array using an iterative Ternary Search.
7. Write a C program to find the nth Fibonacci number using recursion (brute force).
8. Write a C program to find the nth Fibonacci number using a Top-Down Dynamic
Programming (Memoization) approach.
9. Write a C program to find the nth Fibonacci number using a Bottom-Up Dynamic
Programming (Tabulation) approach.
10. Write a C program to solve the 0/1 Knapsack problem using recursion.
11. Write a C program to solve the 0/1 Knapsack problem using dynamic programming.
12. Write a C program to find the Longest Common Subsequence (LCS) of two strings
using recursion.
13. Write a C program to find the Longest Common Subsequence (LCS) of two strings
using dynamic programming.
14. Write a C program to demonstrate the fractional knapsack problem.
15. Write a C program to implement Matrix Chain Multiplication using dynamic
programming.

35