1) The recurrence relation for insertion sort is (T(n)=T(n-1)+O(n)This is because for an array of

size (n), the algorithm recursively sorts the first (n-1) elements and then inserts the $n(the
lement into its correct position, which can take upto O(n)$ time in the worst case.

Recurrence relation breakdown

(T(n)): The time complexity for sorting an array of size (n).

(T(n-1): The time it takes to recursively sort the first (n-1) elements of the array.

(O(n): The time it takes to insert the $n

(th element into its correct sorted position [1,2,15]. In the worst-casescenario(e.g.,when the array is
in reverse order),this element must be compared with all n-1$ previously sorted elements.

2. Quicksort is a popular sorting algorithm that chooses a pivot element and sorts the input list
around that pivot element.

There are mainly three steps in the algorithm:

1. Choose a Pivot: Select an element from the array as the pivot. The choice of pivot can vary
(e.g., first element, last element, random element, or median).

2. Partition the Array: Re arrange the array around the pivot. After partitioning, all elements
smaller than the pivot will be on its left, and all elements greater than the pivot will be on its
right. The pivot is then in its correct position, and we obtain the index of the pivot.

3. Recursively Call: Recursively apply the same process to the two partitioned sub-arrays (left
and right of the pivot).

4. Base Case: The recursion stops when there is only one element left in the sub-array, as a
single element is already sorted.
3. Randomized quick sort is designed to decrease the chances of the algorithm being executed in the
worst case time complexity of O(n2). The worst case time complexity of quick sort arises when the
input given is an already sorted list, leading to n(n 1) comparisons. There are two ways to randomize
the quicksort –

 Randomly shuffling the inputs: Randomization is done on the input list so that the sorted
input is jumbled again which reduces the time complexity. However, this is not usually
performed in the randomized quick sort.

 Randomly choosing the pivot element: Making the pivot element a random variable is
commonly used method in the randomized quick sort. Here, even if the input is sorted, the
pivot is chosen randomly so the worst case time complexity is avoided.

Dijkstras shortest path algorithm is similar to that of Prims algorithm as they both rely on finding the
shortest path locally to achieve the global solution. However, unlike prims algorithm, the dijkstras
algorithm does not find the minimum spanning tree; it is designed to find the shortest path in the
graph from one vertex to other remaining vertices in the graph. Dijkstras algorithm can be performed
on both directed and undirected graphs.

The algorithm starts from the source. The inputs taken by the algorithm are the graph G {V, E}, where
V is the set of vertices and E is the set of edges, and the source vertex S. And the output is the
shortest path spanning tree.
Step 1

Initialize the distances of all the vertices as ∞, except the source node S.

Vertex S A B C D E

Distance 0 ∞ ∞ ∞ ∞ ∞

Now that the source vertex S is visited, add it into the visited array.

visited = {S}

Step 2

The vertex S has three adjacent vertices with various distances and the vertex with minimum
distance among them all is A. Hence, A is visited and the dist[A] is changed from ∞ to 6.

S→A=6

S→D=8

S→E=7

Vertex S A B C D E

Distance 0 6 ∞ ∞ 8 7

VisStep 2 The vertex S has three adjacent vertices with various distances and the vertex with
minimum distance among them all is A. Hence, A is visited and the dist[A] is changed from ∞ to 6. S
→ A = 6 S → D = 8 S → E = 7 Vertex S A B C D E Distance 0 6 ∞ ∞ 8 7 ited = {S, A}

Step 3

There are two vertices visited in the visited array, therefore, the adjacent vertices must be checked
for both the visited vertices.

Vertex S has two more adjacent vertices to be visited yet: D and E. Vertex A has one adjacent vertex
B.

Calculate the distances from S to D, E, B and select the minimum distance −

S → D = 8 and S → E = 7.

S → B = S → A + A → B = 6 + 9 = 15

Vertex S A B C D E

Distance 0 6 15 ∞ 8 7

VStep 3 There are two vertices visited in the visited array, therefore, the adjacent vertices must be
checked for both the visited vertices. Vertex S has two more adjacent vertices to be visited yet: D and
E. Vertex A has one adjacent vertex B. Calculate the distances from S to D, E, B and select the
minimum distance − S → D = 8 and S → E = 7. S → B = S → A + A → B = 6 + 9 = 15

Vertex S A B C D E

Distance 0 6 15 ∞ 8 7 isited = {S, A, E}

Step 4

Calculate the distances of the adjacent vertices S, A, E of all the visited arrays and select the vertex
with minimum distance.

S→D=8

S → B = 15

S → C = S → E + E → C = 7 + 5 = 12

Vertex S A B C D E

Distance 0 6 15 12 8 7

Visited = {S, A, E, D}

Step 5
Recalculate the distances of unvisited vertices and if the distances minimum than existing distance is
found, replace the value in the distance array.

S → C = S → E + E → C = 7 + 5 = 12

S → C = S → D + D → C = 8 + 3 = 11

dist[C] = minimum (12, 11) = 11

S → B = S → A + A → B = 6 + 9 = 15

S → B = S → D + D → C + C → B = 8 + 3 + 12 = 23

dist[B] = minimum (15,23) = 15

Vertex S A B C D E

Distance 0 6 15 11 8 7

ed = { S, A, E, D, C}

Step 6

The remaining unvisited vertex in the graph is B with the minimum distance 15, is added to the
output spanning tree.

VisiteStep 6 The remaining unvisited vertex in the graph is B with the minimum distance 15, is added
to the output spanning tree. d = {S, A, E, D, C, B}

5. Dynamic programming is employed in optimization scenarios when two key characteristics

 Optimal Substructure:

The optimal solution to the overall problem can be constructed from the optimal solutions of its
subproblems. This means that if you find the best solution for a smaller part of the problem, that
solution will contribute to the best solution for the larger problem.

 Overlapping Subproblems:

The same subproblems are encountered and solved multiple times during the computation of the
overall solution. Dynamic programming addresses this by storing the solutions to these subproblems
(using memoization or tabulation) so they can be reused, avoiding redundant calculations and
significantly improving efficiency.

6. Coding, Fractional Knapsack), but it might not be optimal. Use Dynamic Programming
(DP) when absolute global optimality is crucial and the problem has overlapping
subproblems, using memoization to build solutions from smaller optimal sub-
solutions (e.g., 0/1 Knapsack, LCS).
Use Greedy When:

 Greedy Choice Property: A locally optimal choice leads to a globally optimal solution (e.g.,
Activity Selection).

 Speed & Simplicity: You need faster execution and less memory (no memoization needed).

 Near-Optimal is Fine: An exact optimal solution isn't strictly required.

 Examples: Dijkstra's Algorithm (shortest path), Huffman Coding, Fractional Knapsack.

Use Dynamic Programming When:

 Optimal Substructure & Overlapping Subproblems: Solutions to large problems rely on

 Guaranteed Optimal: You must find the absolute best solution.

 Complex Decisions: Local choices don't guarantee global optimality, requiring look-back.

 Examples: 0/1 Knapsack, Longest Common Subsequence, Matrix Chain Multiplication.

The "0/1 Fractional Knapsack Problem" is a slight misnomer, as 0/1 and Fractional knapsack are
different problems: the 0/1 Knapsack means taking items whole or not at all (solved with Dynamic
Programming), while the Fractional Knapsack lets you take parts of items (solved greedily by
value/weight ratio). Combining