Iterative Algorithm to Find GCD:

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them.

The iterative method uses Euclid’s algorithm, which is based on the property:
gcd(a, b) = gcd(b, a mod b)

Algorithm:

GCD(a, b):

while b != 0:
    temp = b
    b = a mod b
    a = temp

return a

Explanation:

• Replace the larger number with the smaller number

• Replace the smaller number with remainder (a mod b)

• Repeat until remainder becomes 0

• The last non-zero value of a is the GCD

Example:
Find GCD of 48 and 18:

48 mod 18 = 12 → (18, 12)
18 mod 12 = 6 → (12, 6)
12 mod 6 = 0 → (6, 0)

So, GCD = 6

Complexity Analysis:

Time Complexity:
At each step, the pair (a, b) reduces significantly.

The number of steps is proportional to the number of digits of the smaller number.

So time complexity is:
O(log min(a, b))

Space Complexity:
Only a constant number of variables are used.

So space complexity is:
O(1)

1. Frequency Calculation:

   • C: 2
   • Y: 1
   • B: 1
   • E: 2
   • R: 2
   • I: 1
   • M: 1

2. Initial Tree Nodes: Create a node for each character and its frequency.

3. Huffman Tree Construction:

   • Combine 'I' (1) and 'B' (1) -> Node(2) – 'IB'
   • Combine 'Y' (1) and 'M' (1) -> Node(2) – 'YM'
   • Combine 'IB' (2) and 'YM' (2) -> Node(4) – 'IBYM'
   • Combine 'C' (2) and 'E' (2) -> Node(4) – 'CE'
   • Combine 'R' (2) and 'CE' (4) -> Node(6) – 'RCE'
   • Combine 'IBYM' (4) and 'RCE' (6) -> Node(10) – 'IBYMRCE' (Root)

4. Code Assignment:

   • I/B: 11
   • Y/M: 10
   • CE: 01
   • R: 00

5. Prefix Codes:

   • C: 010
   • Y: 100
   • B: 110
   • E: 011
   • R: 00

6. Encoding the String "CYBER CRIME":

   • C: 010
   • Y: 100
   • B: 110
   • E: 011
   • R: 00
   • : 000 (space)
   • C: 010
   • R: 00
   • I: 111
   • M: 101
   • E: 011

7. Total Bits Required:

   • 3 + 3 + 3 + 3 + 2 + 3 + 3 + 2 + 3 + 3 + 3 = 33 bits

Tractable Problem:
A problem is considered tractable if it can be solved in polynomial time by a deterministic algorithm. This means the time required to solve the problem grows as a polynomial function of the input size (e.g., O(n), O(n²), O(n³)).

Intractable Problem:
A problem is considered intractable if no polynomial-time algorithm is known to solve it, and it is believed that no such algorithm exists. These problems typically require exponential time (e.g., O(2ⁿ), O(n!)) to solve, making them impractical for large input sizes. They often belong to the complexity class NP-complete.

Vertex Cover Problem:

Example ko lagi watch video - it is best that way..

Edit distance between “ARTIFICIAL” and “NATURAL” using dynamic programming:

1. Initialization:

Create a (m+1) x (n+1) matrix dp, where m = len("ARTIFICIAL") = 10 and n = len("NATURAL") = 7.

dp[i][0] = i for all i from 0 to m.
dp[0][j] = j for all j from 0 to n.

2. Recurrence Relation:

dp[i][j] = min(dp[i-1][j] + 1, // Deletion dp[i][j-1] + 1, // Insertion dp[i-1][j-1] + (0 if s1[i-1] == s2[j-1] else 1)) // Substitution

3. Calculation:

Populate the dp matrix using the recurrence relation.

4. Result:

The edit distance is dp[m][n] = dp[10][7] = 7.

a) Best, Worst and Average Case Complexity

These complexities describe the performance of an algorithm as input size (n) grows.

• Best Case: Minimum time/space required for algorithm execution. Occurs under most favorable input conditions. Expressed using Big O notation: O(f(n)).
• Worst Case: Maximum time/space required. Occurs under most unfavorable input conditions. Provides a guarantee on upper bound performance. Expressed as O(f(n)).
• Average Case: Expected time/space, averaged over all possible inputs of size n. Requires probabilistic analysis and is often more representative of real-world performance. Expressed as O(f(n)).

b) Greedy Strategy

A problem-solving approach where, at each step, the algorithm makes the locally optimal choice, hoping to find the global optimum.

• Principle: Build a solution incrementally, making the best immediate choice.
• Applicability: Suitable for optimization problems where locally optimal choices lead to a globally optimal solution (e.g., Dijkstra’s algorithm, Huffman coding).
• Limitations: Does not always guarantee the optimal solution. Requires proof of correctness for each specific problem.
• Example: Coin change problem – repeatedly selecting the largest denomination coin that doesn't exceed the remaining amount.

Let the given congruences be:
x ≡ 1 (mod 2) ...(1)
x ≡ 3 (mod 5) ...(2)
x ≡ 6 (mod 7) ...(3)

Here, n1 = 2, n2 = 5, n3 = 7.
N = n1 * n2 * n3 = 2 * 5 * 7 = 70

N1 = N/n1 = 70/2 = 35
N2 = N/n2 = 70/5 = 14
N3 = N/n3 = 70/7 = 10

Now, we need to find the inverses:
x1 such that N1 * x1 ≡ 1 (mod n1) => 35 * x1 ≡ 1 (mod 2) => x1 ≡ 1 (mod 2)
x2 such that N2 * x2 ≡ 1 (mod n2) => 14 * x2 ≡ 1 (mod 5) => 14x2 ≡ 4x2 ≡ 1 (mod 5) => x2 ≡ 4 (mod 5)
x3 such that N3 * x3 ≡ 1 (mod n3) => 10 * x3 ≡ 1 (mod 7) => 3x3 ≡ 1 (mod 7) => x3 ≡ 5 (mod 7)

The solution is given by:
x = (a1 * N1 * x1 + a2 * N2 * x2 + a3 * N3 * x3) mod N
x = (1 * 35 * 1 + 3 * 14 * 4 + 6 * 10 * 5) mod 70
x = (35 + 168 + 300) mod 70
x = 503 mod 70
x = 13

Therefore, x ≡ 13 (mod 70).