Unit6 - Subjective Questions

An Algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.

Essential Characteristics:

1. Input: An algorithm has zero or more inputs, taken from a specified set of objects.
2. Output: An algorithm has one or more outputs, which have a specified relation to the inputs.
3. Definiteness: Each step of the algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case.
4. Finiteness: An algorithm must always terminate after a finite number of steps. If it runs forever, it is a computational method, not an algorithm.
5. Effectiveness: All operations to be performed must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a person using paper and pencil.

A Priori Analysis (Theoretical Analysis):

• Definition: It is a determination of the order of magnitude of a statement execution count (time complexity) or space requirement before running the algorithm.
• Dependency: It is independent of the underlying hardware and programming language.
• Focus: It uses asymptotic notations (like Big-O) to describe the algorithm's efficiency as a function of input size .

A Posteriori Analysis (Empirical Analysis):

• Definition: It involves implementing the algorithm using a specific programming language and executing it on a specific machine.
• Dependency: It is highly dependent on hardware (processor speed, memory), compiler, and operating system.
• Focus: It collects actual statistics like running time (in seconds) and memory consumption (in bytes).

Asymptotic Notation is a mathematical tool used to represent the time or space complexity of algorithms for large input sizes. It describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Big-O Notation ()

Definition: Let and be functions mapping non-negative integers to real numbers. We say that is (read as "big-oh of g of n") if there exist positive constants and such that:

Geometric Interpretation:

• acts as an upper bound on the growth of .
• For all input sizes greater than , the value of is always on or below the curve .
• It is typically used to describe the worst-case scenario of an algorithm.

Big-Omega ()

Definition: if there exist positive constants and such that:

• Meaning: It provides an asymptotic lower bound. It denotes that the algorithm will take at least this much time.

Big-Theta ()

Definition: if there exist positive constants and such that:

• Meaning: It provides an asymptotic tight bound. The function grows at the same rate as .

Difference from Big-O:

• Big-O (): Upper bound (Worst case typically). "Algorithm takes at most this much time."
• Big-Omega (): Lower bound (Best case typically). "Algorithm takes at least this much time."
• Big-Theta (): Tight bound (Average/Exact fit). "Algorithm takes exactly this order of time."

To prove , we need to find positive constants and such that:

Derivation:

1. Since , we know that and .
2. We can rewrite the inequality:
   
3. Combine terms:
   
4. Therefore, if we choose and , the condition holds.

Conclusion:
Since for all , by definition, .

Types of Cases:

1. Best Case: The specific input configuration for which the algorithm performs the minimum number of steps. It defines the lower bound of time complexity.
2. Average Case: The expected behavior of the algorithm over all possible inputs of size , weighted by the probability of those inputs occurring. It is often harder to calculate as it requires knowledge of input distribution.
3. Worst Case: The specific input configuration for which the algorithm performs the maximum number of steps. It defines the upper bound ().

Importance of Worst Case:

• Guarantee: It provides a guarantee that the algorithm will never take longer than this time, which is critical for real-time systems.
• Design Benchmark: It allows software engineers to design systems based on peak load capacity.
• Frequency: In some algorithms (like searching unsorted databases), the worst-case scenario (item not found) occurs frequently.

To arrange them, we compare how fast increases as .

Analysis:

1. (Polynomial < 1)
2. (Linear)
3. (Log-linear)
4. (By Stirling's approximation)
5. (Quadratic)
6. (Exponential)
7. (Factorial)

Correct Order (Slowest to Fastest Growth):

Note: While , usually simple polynomial terms are listed before logarithmic factorial approximations if strictly ordering classes, but they are asymptotically tight.

Recursion is a programming technique where a function calls itself to solve a smaller instance of the problem.

Components:

1. Base Case: The condition under which the recursion stops. Without this, the function would call itself indefinitely (infinite recursion) leading to a stack overflow.
2. Recursive Step: The part where the function calls itself with modified arguments moving towards the base case.

Mechanics (Stack Memory):

• When a recursive call is made, the current state of the function (local variables, return address) is pushed onto the Call Stack (Activation Record).
• The control transfers to the new function call.
• This process continues until the Base Case is reached.
• Once the base case returns a value, the stack pops the top frame, returning control and the result to the previous caller.
• This unwinding continues until the original call returns the final result.

Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.

Core Concept:

• It builds candidates for the solution incrementally.
• It abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
• It typically uses a Depth-First Search (DFS) on the state-space tree.

Difference from Brute Force:

• Brute Force: Generates all possible solutions and checks each one to see if it satisfies the constraints. It visits every leaf node of the state-space tree.
• Backtracking: Uses bounding functions (constraints). If a partial solution violates a constraint, it prunes the whole subtree rooted at that node. It is essentially "Brute Force with Pruning," making it significantly more efficient.

The Master Theorem solves recurrences of the form .

Given:

• (number of subproblems)
• (factor by which input size decreases)
• (cost of dividing/merging)

Steps:

1. Calculate .
2. Compare with .
3. Here, and . They are equal.
4. This falls under Case 2 of the Master Theorem: If , then .

Result:

Standard Algorithm: This is the time complexity of Merge Sort.

Dynamic Programming is an optimization technique used to solve complex problems by breaking them down into simpler overlapping subproblems. Unlike recursion, DP stores the results of subproblems to avoid re-computing them.

Key Properties:

1. Optimal Substructure:

   • A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
   • Example: In shortest path problems, the shortest path from A to C via B implies the path A to B is also the shortest.

2. Overlapping Subproblems:

   • The recursive algorithm visits the same subproblems repeatedly.
   • DP solves each subproblem only once and stores the result in a table (Memoization or Tabulation).
   • Example: Calculating Fibonacci numbers recursively computes multiple times.

Both are techniques to store results of subproblems in Dynamic Programming.

Greedy Algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate and obvious benefit.

Core Philosophy:

It makes a locally optimal choice at each step with the hope that these choices will lead to a globally optimal solution. It does not backtrack or revise previous choices.

Greedy Choice Property:

• This property states that a global optimum can be arrived at by selecting a local optimum.
• We make the choice that looks best in the current moment without considering results from subproblems.
• Contrast with DP: DP considers solutions to subproblems before making a choice; Greedy makes a choice before solving subproblems.

Fractional Knapsack Problem:

Given items with weights and values , and a knapsack of capacity , maximize the total value. You can break items to take a fraction of them.

Greedy Strategy:

1. Calculate value-to-weight ratio () for all items.
2. Sort items descending by this ratio.
3. Add items until the bag is full. If the last item doesn't fit, take the fraction that fits.

Why Greedy works for Fractional but not 0/1:

• Fractional: The greedy choice (taking the densest item) is always safe because you can fill the remaining "gap" with a fraction of the next best item. There is no "wasted space" penalty.
• 0/1 Knapsack: You either take the item or leave it. Taking the item with the highest ratio might leave a small empty space that cannot be filled by any other item, whereas a combination of items with lower ratios might fill the bag perfectly and yield a higher total value. The greedy choice might prevent reaching the global optimum.

Problem Definition:
Given a set of activities, each with a start time and finish time , select the maximum number of activities that can be performed by a single person/resource, assuming that the person can only work on one activity at a time.

Greedy Strategy:

1. Sort: Sort all activities in increasing order of their finish times ().
2. Select: Select the first activity (the one that finishes earliest).
3. Iterate: For the remaining sorted activities, select the next activity only if its start time is greater than or equal to the finish time of the previously selected activity ().

Why it works: Choosing the activity that finishes earliest leaves the maximum amount of remaining time for other activities.

Problem: Place queens on an chessboard such that no two queens attack each other (i.e., no two queens share the same row, column, or diagonal).

Backtracking Solution:

1. Start in the leftmost column.
2. If all queens are placed, return true.
3. Try all rows in the current column.
4. For each row, check if the queen can be placed safely:
   • Check row on the left side.
   • Check upper diagonal on left side.
   • Check lower diagonal on left side.
5. If safe, place the queen and recursively check for the rest of the queens in the next column.
6. Backtrack Step: If placing the queen leads to no solution (recursive call returns false), remove the queen from the current cell (backtrack) and try the next row.

Fibonacci Series: for , with .

Naive Recursive Solution:

• Code: return fib(n-1) + fib(n-2)
• Analysis: Each call branches into two. This creates a binary tree of depth .
• Complexity: (Exponential). Specifically where is the Golden Ratio.
• Issue: Massive re-computation of overlapping subproblems.

Dynamic Programming Solution (Memoization/Tabulation):

• Strategy: Store calculated values in an array arr[0...n].
• Analysis: We compute each value from to exactly once.
• Complexity: (Linear).
• Space: (can be optimized to space by storing only last two values).

Little-o notation ()

• Definition: if for any positive constant , there exists an such that for all .
• Strict Inequality: It implies becomes insignificant relative to as grows. Algebraically: .
• Analogy: .

Little-omega notation ()

• Definition: if for any positive constant , there exists an such that for all .
• Strict Inequality: It implies grows strictly faster than . Algebraically: .
• Analogy: .

To determine the complexity, we count how many times the print statement executes.

1. Outer Loop: Runs for .
2. Inner Loop: Runs for to . So, it runs times for each iteration of the outer loop.

Total Executions:
Sum of for from $1$ to :

Sum of Arithmetic Series:

Asymptotic Analysis:
The term with the highest degree is .
Therefore, the time complexity is .