Dynamic Programming vs. Memorization

Dynamic Programming:

• Bottom-up approach.
• Solves overlapping subproblems by systematically building solutions to larger subproblems from smaller ones.
• Typically uses tables to store solutions to subproblems, ensuring each subproblem is solved only once.
• Suitable when the order of solving subproblems doesn't matter.

Memorization:

• Top-down approach.
• Solves overlapping subproblems by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
• Uses recursion with a cache (e.g., a dictionary or array) to store computed values.
• Suitable when the natural recursive structure of the problem is clear.

Floyd-Warshall Algorithm

​​

Worst Case of Quick Sort:

• Occurs when the pivot chosen at each step is the smallest or largest element in the subarray.
• Results in a partition where one subarray has size 0 and the other has size n-1.
• Leads to a time complexity of O(n²).

Randomized Quick Sort:

• Addresses the worst-case scenario by randomly selecting the pivot element.
• Randomization makes the probability of consistently choosing the worst pivot extremely low.
• Provides an average-case time complexity of O(n log n) with high probability, regardless of the initial input order.

Quick Sort on {-2, 4, -3, 6, 12, 10, 11, 13, 9}:

1. Initial Array: {-2, 4, -3, 6, 12, 10, 11, 13, 9} (Let's choose -2 as the initial pivot)
2. Partition: {-3, -2, 4, 6, 12, 10, 11, 13, 9} (Elements less than -2 are to the left, greater to the right)
3. Recursive Calls:
   • Left Subarray: {-3} (Already sorted)
   • Right Subarray: {4, 6, 12, 10, 11, 13, 9} (Choose 4 as pivot)
4. Partition: {4, 6, 9, 10, 11, 13, 12}
5. Recursive Calls:
   • Left Subarray: {6, 9, 10, 11} (Choose 6 as pivot)
   • Right Subarray: {13, 12} (Choose 13 as pivot)
6. Partition: {9, 6, 10, 11} -> {9, 10, 11, 6} (Incorrect, should be {6, 9, 10, 11})
7. Partition: {12, 13} -> {12, 13}
8. Final Sorted Array: {-3, -2, 4, 6, 9, 10, 11, 12, 13}

Greedy algorithm does not always guarantee an optimal solution for every problem. It works optimally only when the problem has the greedy choice property and optimal substructure. For example, it gives optimal results in fractional knapsack, but not necessarily in 0/1 knapsack, shortest path with negative edges, etc.

Fractional Knapsack Problem:

We compute value per unit weight (value/weight):

Item 1: 12/2 = 6
Item 2: 10/1 = 10
Item 3: 20/3 ≈ 6.67
Item 4: 15/2 = 7.5
Item 5: 2/12 ≈ 0.167
Item 6: 3/10 = 0.3
Item 7: 50/1 = 50

Now sort items in decreasing order of value/weight:

Item 7 (50)
Item 2 (10)
Item 4 (7.5)
Item 3 (6.67)
Item 1 (6)
Item 6 (0.3)
Item 5 (0.167)

Assume knapsack capacity is 15 kg (standard assumption since not given).

Now pick greedily:

Item 7: weight 1, value 50 → remaining capacity = 14
Item 2: weight 1, value 10 → remaining = 13
Item 4: weight 2, value 15 → remaining = 11
Item 3: weight 3, value 20 → remaining = 8
Item 1: weight 2, value 12 → remaining = 6
Item 6: weight 10, but only 6 capacity left → take fraction 6/10

Fraction of Item 6 value = 3 × (6/10) = 1.8

Total value = 50 + 10 + 15 + 20 + 12 + 1.8 = 108.8

Final Answer:
Maximum loot = 108.8 units

(Note: If capacity differs, final selection changes accordingly.)

Diagram of this type of questions are tedious, you can check on video to see the method to solve these types of problems instead.

Backtracking to find subsets summing to 35:

1. Initialization: Start with an empty subset and a current sum of 0.
2. Exploration:
   • Consider each element in A sequentially.
   • Include: Add the element to the current subset and update the current sum.
     • If the current sum equals 35, a solution is found.
     • If the current sum is less than 35, recursively explore further elements.
     • If the current sum exceeds 35, backtrack (remove the element).
   • Exclude: Do not add the element to the current subset and recursively explore further elements.
3. Backtracking: If a path leads to a sum greater than 35 or all elements are explored without finding a solution, remove the last added element (backtrack) and explore alternative paths.

Applying this to A = {5, 7, 10, 12, 15, 18, 20}:

• Path 1: 5 + 7 + 10 + 12 + 1 = 35 (Incorrect, 1 is not in A)
• Path 2: 5 + 7 + 10 + 15 = 37 (Exceeds 35, backtrack)
• Path 3: 5 + 7 + 10 + 12 = 34 (Continue)
  • 5 + 7 + 10 + 12 + 15 = 49 (Exceeds 35, backtrack)
• Path 4: 5 + 7 + 20 = 32 (Continue)
  • 5 + 7 + 20 + 10 = 42 (Exceeds 35, backtrack)
• Path 5: 5 + 15 + 15 = 35 (Incorrect, 15 appears twice)
• Path 6: 7 + 10 + 18 = 35

Therefore, the subset that sums to 35 is {7, 10, 18}.

The Fibonacci sequence is:

F(n)=F(n-1)+F(n-2)

where F(0)=0,\F(1)=1

where each number is the sum of the two previous numbers.

Algorithm to Find the nth Fibonacci Number

Efficient Iterative Algorithm

Pseudocode

Algorithm Fibonacci(n)

Input: Integer n
Output: nth Fibonacci number

if n == 0
    return 0

if n == 1
    return 1

a = 0
b = 1

for i = 2 to n
    c = a + b
    a = b
    b = c

return b

Time and Space Complexity

Time Complexity

• The loop runs from 2 to n

Therefore:  O(n)

Space Complexity

• Only three variables are used (a, b, c)
• No extra array or recursion stack is needed

Therefore: O(1)

Order Statistics Problem:

The order statistics problem involves finding the k-th smallest element in a set of n numbers. Formally, given an unsorted array S of n distinct numbers, the k-th order statistic is the element that would be in the k-th position if the array were sorted. This can be solved more efficiently than fully sorting the array (O(n log n)) using algorithms like Quickselect, achieving an average time complexity of O(n).

Edit Distance (“cat” and “car”):

Therefore, the edit distance between "cat" and "car" is d[3, 3] = 1. This corresponds to substituting 't' with 'r'.

Recursion:
Recursion is a technique in which a function calls itself repeatedly to solve a problem. A recursive solution generally consists of:

1. Base Case – condition where recursion stops.

2. Recursive Case – function calls itself with a smaller subproblem.

Example:

factorial(n):
    if n == 0
        return 1
    return n * factorial(n-1)

Advantages:

• Simple and shorter code

• Useful for tree traversal and divide-and-conquer problems

Disadvantages:

• Uses extra memory due to recursion stack

• Can be slower because of repeated function calls

Backtracking:
Backtracking is an algorithmic technique used to solve problems by trying different possible solutions and removing those that do not satisfy the required conditions.

It is based on recursion.

Steps involved:

1. Choose an option

2. Explore recursively

3. If the choice fails, undo it

4. Try another choice

Applications:

• N-Queens problem

• Sudoku solver

• Graph coloring

• Maze solving

General structure:

backtrack(solution):
    if solution is complete
        print solution
        return

    for each possible choice
        make choice
        backtrack(solution)
        undo choice

Miller Rabin Randomized Primality Test:
The Miller Rabin algorithm is a probabilistic algorithm used to determine whether a number is prime or composite.

The algorithm performs multiple random tests on the number. If the number passes all tests, it is considered probably prime.

Complexity Analysis:
Let:

• n = number being tested

• k = number of iterations

Each iteration uses modular exponentiation.

Time Complexity:
O(k(log n)^3)

Space Complexity:
O(log n)

The algorithm is efficient for testing very large numbers and is widely used in cryptography.

The approximation algorithm for vertex cover is a greedy algorithm that achieves a 2-approximation ratio.

Algorithm:

1. Initialize an empty vertex cover set, C.
2. While the graph G has edges:
   • Select an arbitrary edge (u, v) from G.
   • Add both vertices u and v to the vertex cover set C.
   • Remove all edges incident to either u or v from G.
3. Return the vertex cover set C.

Approximation Ratio:

The algorithm provides a 2-approximation because, in the worst case, for each edge selected, both endpoints are added to the cover. An optimal vertex cover must include at least one endpoint of each edge. Therefore, the size of the returned vertex cover is at most twice the size of the optimal vertex cover.

Example:

Consider the graph with vertices {A, B, C, D} and edges {(A, B), (B, C), (C, D), (A, C)}.

1. C = {}
2. Select edge (A, B). C = {A, B}. Remove edges (A, B). Graph now has edges {(B, C), (C, D), (A, C)}.
3. Select edge (B, C). C = {A, B, C}. Remove edges (B, C), (A, C). Graph now has edge {(C, D)}.
4. Select edge (C, D). C = {A, B, C, D}. Remove edge (C, D). Graph has no edges.
5. Return C = {A, B, C, D}.

In this example, the algorithm returns a vertex cover of size 4. The optimal vertex cover is {B, C}, with size 2. The approximation ratio is 4/2 = 2.

Cook's Theorem:

Cook's Theorem states that the Boolean Satisfiability Problem (SAT) is NP-complete. Formally:

• SAT is in NP: Given a truth assignment, verifying its correctness can be done in polynomial time.
• SAT is NP-hard: Every problem in NP can be reduced to SAT in polynomial time.

Problem Reducibility:

Problem reducibility is a fundamental technique in computational complexity theory used to demonstrate the relative difficulty of problems.

• Definition: A reduction from problem A to problem B (denoted A ≤p B) is a polynomial-time computable function f that transforms instances of A into instances of B, such that the answer to the instance of A is related to the answer of the instance of B via f. Specifically:

  • If x is a 'yes' instance of A, then f(x) is a 'yes' instance of B.
  • If x is a 'no' instance of A, then f(x) is a 'no' instance of B.

• Purpose:

  • Proving NP-hardness: If a problem B is known to be NP-hard, and A ≤p B, then A is also NP-hard. This is because if we could solve A in polynomial time, we could solve B in polynomial time (by reducing A to B and then solving B).
  • Establishing relative difficulty: Reducibility shows that problem A is no harder than problem B (in a precise sense).

• Types of Reductions:

  • Polynomial-time reduction (≤p): The reduction function f is computable in polynomial time. This is the most common type used in NP-completeness proofs.
  • Log-space reduction (≤l): The reduction function f is computable in log-space. This is a stronger type of reduction than ≤p.
  • Many-one reduction (≤m): A special case of ≤p where f maps an instance of A to a unique instance of B.

a) Big Oh, Big Omega, Big Theta

Big Oh (O):
Big Oh represents the upper bound of an algorithm’s running time. It gives the worst-case growth rate.
If f(n) = O(g(n)), then f(n) does not grow faster than g(n) after some point.

Example: 3n + 5 is O(n)

Big Omega (Ω):
Big Omega represents the lower bound of an algorithm’s running time. It gives the best-case growth rate.
If f(n) = Ω(g(n)), then f(n) grows at least as fast as g(n).

Example: 3n + 5 is Ω(n)

Big Theta (Θ):
Big Theta represents a tight bound. It means both upper and lower bound are the same asymptotically.
If f(n) = Θ(g(n)), then f(n) grows exactly like g(n) in order.

Example: 3n + 5 is Θ(n)

b) Class P, Class NP, NP-Complete

Class P:
Class P consists of decision problems that can be solved in polynomial time by a deterministic algorithm.
These are problems that are efficiently solvable.

Example: Sorting, shortest path (Dijkstra), etc.

Class NP:
Class NP consists of decision problems whose solutions can be verified in polynomial time.
That means, if someone gives a solution, we can check it quickly.

Example: Sudoku verification, Hamiltonian path verification.

NP-Complete:
A problem is NP-Complete if:

1. It is in NP

2. Every problem in NP can be reduced to it in polynomial time

These are the hardest problems in NP. If any NP-complete problem is solved in polynomial time, then P = NP.

Example: SAT problem, Traveling Salesman (decision version), Clique problem.