A recurrence relation is an equation that expresses the value of a function in terms of its values at smaller inputs. It defines a sequence recursively.

Solving Recurrence Relations:

Common methods include:

• Substitution: Guess a solution and prove it by induction.
• Iteration (Unfolding): Repeatedly expand the recurrence until a pattern emerges.
• Master Theorem: Applies to specific recurrence forms (divide and conquer).
• Recursion Tree Method: Visualize the recurrence as a tree to determine the cost.

Time Complexity of T(n) = 2T(n/2) + 1 using Substitution Method:

1. Guess: We hypothesize that T(n) = O(n). This means T(n) ≤ cn for some constant c > 0.

2. Base Case: For n = 1, T(1) = 1 (assuming base case). 1 ≤ c(1) holds for any c ≥ 1.

3. Inductive Hypothesis: Assume T(k) ≤ ck for all k < n.

4. Inductive Step: We need to show that T(n) ≤ cn.

T(n) = 2T(n/2) + 1
≤ 2 * c(n/2) + 1 (by the inductive hypothesis)
= cn + 1

To prove T(n) ≤ cn, we need cn + 1 ≤ cn, which simplifies to 1 ≤ 0. This is false. Therefore, our initial guess of T(n) = O(n) is incorrect.

Let's refine our guess to T(n) = cn - d for some constants c and d.

T(n) = 2T(n/2) + 1
≤ 2 * [c(n/2) - d] + 1 (by the inductive hypothesis)
= cn - 2d + 1

We want cn - 2d + 1 ≤ cn - d. This simplifies to -2d + 1 ≤ -d, or d ≥ 1. So, if we choose d = 1, the inequality holds.

Therefore, T(n) ≤ cn - 1.

5. Conclusion: By the principle of mathematical induction, T(n) = O(n).

Matrix Chain Multiplication (Dynamic Programming Solution)

Given:
A1: 2×3
A2: 3×4
A3: 4×2
A4: 2×5

Dimension array:
p = [2, 3, 4, 2, 5]

We define:
m[i][j] = minimum cost to multiply Ai … Aj

Base case:
m[i][i] = 0

Step 1: Chain length = 2

m[1][2] = 2×3×4 = 24
m[2][3] = 3×4×2 = 24
m[3][4] = 4×2×5 = 40

Step 2: Chain length = 3

m[1][3]:

• k=1: (A1)(A2A3) = 0 + 24 + 2×3×2 = 12 → 36

• k=2: (A1A2)(A3) = 24 + 0 + 2×4×2 = 16 → 40
  So, m[1][3] = 36

m[2][4]:

• k=2: (A2)(A3A4) = 0 + 40 + 3×4×5 = 60 → 100

• k=3: (A2A3)(A4) = 24 + 0 + 3×2×5 = 30 → 54
  So, m[2][4] = 54

Step 3: Chain length = 4

m[1][4]:
Try all splits:

k=1:
(A1)(A2A3A4)
= 0 + 54 + 2×3×5 = 30 → 84

k=2:
(A1A2)(A3A4)
= 24 + 40 + 2×4×5 = 40 → 104

k=3:
(A1A2A3)(A4)
= 36 + 0 + 2×2×5 = 20 → 56

Final DP Table (m[i][j]):

Optimal cost:
56

Optimal parenthesization:
(A1 (A2 A3)) A4

RAM Model Definition (2 marks)

The Random Access Machine (RAM) model is a theoretical model of computation used to analyze algorithm efficiency. It assumes:

• An infinite, addressable memory array.
• A finite set of registers.
• A program counter.
• A set of instructions (e.g., load, store, add, subtract, jump).
• Instructions operate on memory addresses and register contents.
• Access time to any memory location is constant (unit cost).

Iterative Factorial Algorithm (1 mark)

function factorial(n):
  result = 1
  for i = 2 to n:
    result = result * i
  return result

Detailed Analysis (2 marks)

• Initialization: result = 1 - 1 assignment operation.
• Loop: The loop iterates n-1 times.
• Inside Loop:
  • result = result * i - 1 multiplication and 1 assignment operation per iteration.
• Return: return result - 1 return operation.

Total Cost:

• Initialization: 1
• Loop iterations: (n-1) * (1 multiplication + 1 assignment) = 2(n-1)
• Return: 1

Therefore, the total cost is 1 + 2(n-1) + 1 = 2n.

The algorithm has a time complexity of O(n). The number of operations grows linearly with the input n .

Insertion Sort Algorithm:

1. Iterate from the second element (index 1) to the last element of the array.
2. For each element, compare it with the elements before it.
3. If the current element is smaller than its predecessor, compare it with the elements before the predecessor.
4. Shift the larger elements one position ahead.
5. Insert the current element into its correct sorted position.

Pseudocode:

InsertionSort(array A)
  for i = 1 to length(A) - 1 do:
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key do:
      A[j + 1] = A[j]
      j = j - 1
    A[j + 1] = key
  end for

Time Complexity:

• Best Case: O(n) - When the array is already sorted.
• Average Case: O(n²)
• Worst Case: O(n²) - When the array is sorted in reverse order.

Space Complexity:

• O(1) - Insertion sort is an in-place sorting algorithm, requiring only a constant amount of extra space.

Minimax Finding Algorithm:

Minimax is a recursive decision-making algorithm used to find the maximum and minimum number in a given array of elements of size "n" . This algorithm is based on DAC(Divide and conquer Approach),The array is divided into two halves and then using recursive approach the maximun and minimum numbers in each halves are found out.later the maximum of two maxima of each halves and the minimum of the two minima of each halves are found out and returned.   

ALGORITHM:

• Divde the array into 2 halves from the mid index ; Mid= (left+right)/2
• Divide till each sub array has 2 elements.
• compare each sub array for maximum and minmum values 

Pseudocode

MinMax(l,r)

{

if(l==r)

    {

max=min=A[l];

}

elseif(l=r-1)

{

if(A[l]<A[r])

{

max=a[r];

min=a[l];

}

else

{

max=A[l];

min=A[r];

}

}

else    //dividing the probelm

{

mid=(l+r)/2;          //integer division

{min,max}=MinMax{l,mid};      //solving subproblems

{min1,max1}=MinMax{mid+1,r} ;  

if(max1>max)

 max=max1;

if(min1,min)

 min=min1;

}

}

Complexity Analysis:

Since we perform the MinMax finding algrorithm on "n" number of elements , so the time complexity for the algorithm is O(n).

Greedy strategy provides an optimal solution when the problem satisfies the greedy-choice property and optimal substructure. This means:

1. Greedy-choice property: A locally optimal choice at each step leads to a globally optimal solution.

2. Optimal substructure: An optimal solution to the problem contains optimal solutions to its subproblems.

Greedy algorithms work correctly when making one choice does not affect the feasibility of future optimal choices in a harmful way.

Examples where greedy gives optimal solution:

• Fractional Knapsack

• Activity Selection Problem

• Huffman Coding

• Prim’s and Kruskal’s algorithms (MST)

• Dijkstra’s algorithm (non-negative weights)

Job Sequencing with Deadlines Algorithm:

Problem statement:
We are given n jobs, each job has:

• a deadline

• a profit
  Each job takes 1 unit time. Only one job can be scheduled at a time. The goal is to maximize total profit.

Algorithm:

1. Sort all jobs in decreasing order of profit.

2. Create an array of time slots from 1 to max deadline, all initially empty.

3. For each job in sorted order:

   • Find a free slot from its deadline down to 1

   • If a free slot is found, assign the job to that slot

Pseudocode:

sort jobs in decreasing order of profit

for each job in jobs:
    for j = min(deadline, n) down to 1:
        if slot[j] is empty:
            slot[j] = job
            break

Complexity Analysis:

Let n be number of jobs and d be maximum deadline.

Sorting takes:
O(n log n)

Scheduling step:
For each job, we may scan up to d slots in worst case.

So scheduling takes:
O(n × d)

Total time complexity:
O(n log n + n d)

Space complexity:
O(d) for slot array (or O(n) depending on implementation)

1. Initialization: Create a node for each symbol with its frequency.

2. Iteration 1:

   • Combine 'a' (30) and 'b' (20) into a new node 'ab' (50).
   • Remaining nodes: 'ab'(50), 'c'(25), 'd'(15), 'e'(35).

3. Iteration 2:

   • Combine 'c' (25) and 'd' (15) into a new node 'cd' (40).
   • Remaining nodes: 'ab'(50), 'cd'(40), 'e'(35).

4. Iteration 3:

   • Combine 'cd' (40) and 'e' (35) into a new node 'cde' (75).
   • Remaining nodes: 'ab'(50), 'cde'(75).

5. Iteration 4:

   • Combine 'ab' (50) and 'cde' (75) into the root node 'abcde' (125).

6. Code Assignment:

   • Traverse the tree from the root to each leaf node, assigning '0' to left branches and '1' to right branches.
   • a: 00
   • b: 01
   • c: 100
   • d: 101
   • e: 11

Huffman Codes:

• a: 00
• b: 01
• c: 100
• d: 101
• e: 11

Backtracking can yield multiple solutions if the problem has multiple valid solutions and the algorithm is not modified to stop after finding the first solution.

Subset sum problems ko lagi video herda huncha rather than seeing a particular question

Extended Euclidean Algorithm (Iterative Approach):

We want to find gcd(a, b) and integers x, y such that:
a·x + b·y = gcd(a, b)

Iterative Algorithm:

extended_gcd_iterative(a, b):

a1 = a, a2 = b
x1 = 1, x2 = 0
y1 = 0, y2 = 1

while a2 != 0:
    q = a1 // a2

    a1, a2 = a2, a1 - q * a2
    x1, x2 = x2, x1 - q * x2
    y1, y2 = y2, y1 - q * y2

return (a1, x1, y1)

Explanation of variables:

• a1, a2 track the current and next remainder in Euclid’s algorithm

• x1, x2 track coefficients for a

• y1, y2 track coefficients for b

At each step:

• We perform Euclid’s division step

• Then update coefficients to maintain:
  a1·x1 + b·y1 = current gcd

Time Complexity:
O(log min(a, b))

Because each iteration reduces the size of the numbers similar to Euclid’s algorithm.

Space Complexity:
O(1)

Only a fixed number of variables are used, and no recursion stack is needed.

NP-Complete Problems:

A problem is NP-Complete if it satisfies two conditions:

1. It is in NP
   (A given solution can be verified in polynomial time)

2. It is NP-Hard
   (Every problem in NP can be reduced to it in polynomial time)

If any NP-Complete problem can be solved in polynomial time, then all NP problems can be solved in polynomial time (i.e., P = NP).

Examples of NP-Complete problems:

• SAT (Boolean Satisfiability Problem)

• 3-SAT

• Clique problem

• Vertex cover (decision version)

• Hamiltonian cycle problem

• Subset sum problem

• Traveling Salesman Problem (decision version)

Proof that SAT is NP-Complete (Cook–Levin Theorem):

We prove two things:

1. SAT is in NP
   Given a Boolean formula and an assignment of variables, we can evaluate the formula in polynomial time to check whether it is satisfied.
   So SAT ∈ NP.

2. SAT is NP-Hard

We must show that every problem in NP can be reduced to SAT in polynomial time.

Idea of proof:

• Take any problem in NP.

• It is solved by a nondeterministic Turing machine in polynomial time.

• We construct a Boolean formula that simulates the computation of this machine.

Encoding includes:

• Input configuration

• Machine states

• Tape contents at each step

• Transition rules

We build a Boolean formula that is satisfiable if and only if the machine accepts the input.

This transformation can be done in polynomial time.

Conclusion:
Since SAT is both:

• In NP

• NP-Hard

Therefore, SAT is NP-Complete.

a) Aggregate Analysis

Aggregate analysis determines the average-case resource usage of a sequence of operations. It differs from amortized analysis by not focusing on the worst-case cost of each individual operation, but rather the total cost over a series of n operations, divided by n.

• Method: Calculate the total cost of n operations and divide by n to obtain the average cost per operation.
• Applicability: Useful when individual operations have varying costs, but a pattern emerges when considering a large number of operations.
• Example: n push operations onto a stack followed by one pop operation. The total cost is n + 1. The aggregate cost is (n+1)/n, which approaches 1 as n grows large.

b) Selection Problems

Selection problems involve finding the k-th smallest element in a given array or list.

• Goal: Locate the element that would be at index k-1 if the array were sorted.
• Algorithms:
  • Sorting: Sort the array and return the element at index k-1. Time complexity: O(n log n).
  • Quickselect: A selection algorithm based on the partitioning step of quicksort. Average time complexity: O(n). Worst-case: O(n²).
  • Median-of-Medians: Guarantees O(n) worst-case time complexity, but has a higher constant factor than Quickselect.
• Applications: Order statistics, finding quantiles, and data mining.