Unit 6 - Notes

CSE357 7 min read

Unit 6: Algorithms

1. Understanding Algorithms and Analysis

1.1 Definition

An algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. In the context of Combinatorial Studies, algorithms are often used to generate structures (permutations, graphs) or optimize configurations.

1.2 Five Essential Properties (Knuth)

For a procedure to be considered an algorithm, it must satisfy:

Finiteness: The algorithm must always terminate after a finite number of steps.
Definiteness: Each step must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified.
Input: An algorithm has zero or more inputs.
Output: An algorithm has one or more outputs that have a specific relation to the inputs.
Effectiveness: All operations must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a human using pencil and paper.

1.3 Algorithm Analysis

Analysis refers to the process of predicting the resources that the algorithm requires.

Correctness: Proving that the algorithm produces the correct output for every valid input.
Efficiency: Measuring the computational complexity.
- Time Complexity: How long the algorithm takes to run as a function of input size.
- Space Complexity: How much memory the algorithm uses during execution.

2. Running Time Analysis and Rate of Growth

2.1 The RAM Model

To analyze running time independent of specific hardware, we use the Random Access Machine (RAM) model:

Instructions are executed one after another (no concurrent operations).
Standard operations (addition, comparison, assignment) take constant time ($1$ unit).
Memory access takes constant time.

2.2 Input Size ( $n$ )

The running time is expressed as a function $T(n)$ of the input size $n$ .

For sorting/searching: $n$ is the number of items in the list.
For graph algorithms: $n$ usually refers to vertices ( $V$ ) and edges ( $E$ ).
For arithmetic: $n$ is the number of bits needed to represent the number.

2.3 Rate of Growth

We are interested in the rate of growth (or order of growth) of the running time. We look at how $T(n)$ behaves as $n \to \infty$ . Lower order terms and leading constants are ignored because for very large inputs, the highest-degree term dominates.

Comparison of Growth Rates (Slowest to Fastest):

$1$ (Constant)
$\log n$ (Logarithmic)
$n$ (Linear)
$n \log n$ (Linearithmic/Quasilinear)
$n^2$ (Quadratic)
$n^3$ (Cubic)
$2^n$ (Exponential)
$n!$ (Factorial)

2.4 Cases of Analysis

Worst-Case Analysis (Standard): The maximum running time for any input of size $n$ . This provides an upper bound guarantee.
Average-Case Analysis: The expected running time over all possible inputs of size $n$ . Requires probability distribution assumptions.
Best-Case Analysis: The minimum running time. Often not useful for guaranteeing performance.

3. Asymptotic Notation: Big-O Notation

Asymptotic notation provides a mathematical framework to describe the limiting behavior of a function.

3.1 Big-O Notation ( $O$ ) – Upper Bound

$O(g(n))$ represents the set of functions that grow no faster than $g(n)$ .

Definition: $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that:
$0 \leq f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0$
Meaning: Worst-case scenario. The algorithm will not take longer than this order.

3.2 Big-Omega Notation ( $\Omega$ ) – Lower Bound

$\Omega(g(n))$ represents the set of functions that grow at least as fast as $g(n)$ .

Definition: $f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that:
$0 \leq c \cdot g(n) \leq f(n) \quad \text{for all } n \geq n_0$

3.3 Big-Theta Notation ( $\Theta$ ) – Tight Bound

$\Theta(g(n))$ implies the function grows at the same rate as $g(n)$ .

Definition: $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$ .

3.4 Rules for Manipulation

Constant Factors Rule: $O(k \cdot f(n)) = O(f(n))$ .
Sum Rule: $O(f(n) + g(n)) = O(\max(f(n), g(n)))$ .
Product Rule: $O(f(n) \cdot g(n)) = O(f(n)) \cdot O(g(n))$ .
Polynomial Rule: If $f(n)$ is a polynomial of degree $k$ , then $f(n) = O(n^k)$ .

4. Recursion and Backtracking

4.1 Recursion

Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem.

Components:

Base Case: The condition under which the recursion stops (prevents infinite loops).
Recursive Step: The function calls itself with a modified parameter (moving toward the base case).

Recurrence Relations:
The running time of recursive algorithms is described by recurrence relations.

Example (Merge Sort): $T(n) = 2T(n/2) + O(n)$ .
Master Theorem: A formulaic way to solve recurrences of the form $T(n) = aT(n/b) + f(n)$ .

4.2 Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.

Key Concepts:

State Space Tree: A tree representing all possible states (configurations) of the problem.
Depth-First Search (DFS): Backtracking explores the tree depth-first.
Pruning: If the current node cannot possibly lead to a valid solution, the algorithm abandons this branch (backtracks) to save time. This distinguishes backtracking from brute-force enumeration.

Combinatorial Application:
Generating permutations, combinations, or solving constraint satisfaction problems.

Example: The N-Queens Problem

Goal: Place $N$ queens on an $N \times N$ chessboard so no two queens attack each other.
Approach: Place a queen in column 1. Move to column 2. If a safe square exists, place queen. If not, backtrack to column 1 and move that queen.
Complexity: $O(N!)$ in worst case, but average performance is much better due to pruning.

PYTHON

# Pseudocode for Backtracking Template
def backtrack(candidate):
    if find_solution(candidate):
        output(candidate)
        return
    
    for next_candidate in list_of_candidates:
        if is_valid(next_candidate):
            place(next_candidate)
            backtrack(next_candidate)
            remove(next_candidate) # Backtrack step

5. Dynamic Programming (DP) Strategies

Dynamic Programming is an optimization technique used to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations.

5.1 Two Necessary Properties

For DP to be applicable, the problem must exhibit:

Optimal Substructure: An optimal solution to the problem contains within it optimal solutions to subproblems.
Overlapping Subproblems: The recursive algorithm visits the same subproblems repeatedly.

5.2 Approaches

Top-Down with Memoization:
- Write the recursive solution.
- Create a cache (array or hash map).
- Before computing a subproblem, check if the result is in the cache.
- If yes, return it. If no, compute and save it.
Bottom-Up with Tabulation:
- Identify the order in which subproblems must be solved (usually smallest to largest).
- Fill a table iteratively.
- The final answer is usually in the last cell of the table.

5.3 Combinatorial Example: Binomial Coefficients $C(n, k)$

Calculating "n choose k" recursively involves massive redundancy.

Recursive Relation: $C(n, k) = C(n-1, k-1) + C(n-1, k)$ .
DP Approach (Pascal's Triangle):
Construct a table where row $i$ and column $j$ stores $C(i, j)$ .
$\text{Table}[i][j] = \text{Table}[i-1][j-1] + \text{Table}[i-1][j]$
Complexity: Reduces from Exponential (Recursive) to $O(n \cdot k)$ (DP).

6. Greedy Algorithms

6.1 Definition

A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most immediate and obvious benefit. It makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.

6.2 Key Properties

Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.
Optimal Substructure: An optimal solution to the problem contains an optimal solution to subproblems.

6.3 Contrast with Dynamic Programming

DP: Makes a decision at each step based on the solutions to all subproblems (looks back). It is exhaustive and guarantees the optimum.
Greedy: Makes a decision based on current information without looking at the bigger picture (looks forward). It is faster but does not always guarantee the optimal solution.

6.4 Examples

Interval Scheduling (Activity Selection): Given a set of activities with start and finish times, select the maximum number of non-overlapping activities.
- Greedy Strategy: Always pick the remaining activity that finishes earliest. (This is proven to work).
Huffman Coding: Used for data compression. Builds a tree by repeatedly combining the two symbols with the lowest frequency.
Knapsack Problem:
- Fractional Knapsack: (Items can be cut) -> Greedy works (pick highest value/weight ratio).
- 0/1 Knapsack: (Items are whole) -> Greedy fails. Requires Dynamic Programming.

Unit 5