DAA Unit 1: Introduction, Performance Analysis, and Graph Traversals

Introduction to Algorithms

Definition: An algorithm is a finite sequence of well-defined instructions that, when executed, accomplishes a specific task or solves a particular problem.
Formal Definition: A finite set of instructions that, if followed, accomplishes a particular task.
Essential Characteristics of an Algorithm:
- Input: The algorithm accepts zero or more externally supplied values.
- Output: It produces at least one meaningful result.
- Definiteness: Every instruction is precise, clear, and unambiguous.
- Finiteness: The process terminates after a finite number of steps.
- Effectiveness: Each operation is simple, feasible, and executable.

Algorithm Specification and Pseudocode Conventions

Pseudocode: This is an informal, language-independent notation used to describe algorithm steps.
Pseudocode Conventions:
- Comments: Used to improve readability. Written after // or enclosed within comments.
- Compound Statements: Multiple statements grouped between BEGIN and END keywords.
- Assignment Statement: Assigns a value to a variable using the symbol ←. Example: $sum ← sum + x$ .
- Conditional Statements: Used for decision making with keywords IF, THEN, and ELSE.
- Repeat-Until Loop: Executes at least once and stops when the condition becomes true.
- For Loop: Used when the exact number of iterations is known.
- Case Statement: Used for multi-way selection, similar to a switch statement. Format: CASE choice OF 1 : Add 2 : Delete 3 : Search ENDCASE.
- Procedure/Function Call: Invokes another module using CALL, e.g., CALL Sort(A, n).
- Input/Output Statements: Used for accepting and displaying data with READ(n) and WRITE(sum).

Recursion and the Towers of Hanoi

Recursion: A technique where a function or algorithm calls itself to solve a problem.
- Direct Recursion: An algorithm calls itself directly.
- Indirect Recursion: An algorithm calls another algorithm which eventually calls the original.
Towers of Hanoi Example:
- Description: A classic puzzle with three towers ( $A$ , $B$ , and $C$ ) and $n$ disks of different sizes stacked on tower $A$ in decreasing order.
- Rules: Move only one top disk at a time; a larger disk cannot be placed on a smaller disk.
- Objective: Move all disks from Tower $A$ (Source) to Tower $B$ (Destination) using Tower $C$ (Auxiliary).

Performance Analysis

Objective Measures: Execution time is not ideal because it is computer-specific. Counting statements is not ideal as it varies by language and programmer style.
Phases of Evaluation:
- A priori estimates: Theoretical calculations.
- A posteriori testing: Practical performance testing.
Space Complexity: The amount of memory an algorithm needs to run to completion.
- Formula: $S(P) = c + S_p(\text{Instance characteristics})$ , where $c$ is a constant fixed part (instruction space, simple variables, constants) and $S_p$ is the variable part (size dependent on problem instance).
Time Complexity: The amount of computer time needed to run to completion.
- Total time $T(p) = \text{compile time} + \text{run time}$ .
- Compile time is independent of instance characteristics.
- Program Step: A meaningful statement or group of statements whose execution time is constant regardless of input size.

Time Complexity Calculation Examples

Summation (RSum):
- An algorithm that recursively sums elements of an array.
- Step count for $n = 0$ : $2$ .
- Step count for n > 0: $2 + x$ , where $x = t_{RSum}(n - 1)$ .
Matrix Addition (Add):
- Iterates through rows $m$ and columns $n$ .
- for i = 1 to m do executes $m+1$ times.
- for j = 1 to n do executes $m(n+1)$ times.
- Inner addition executes $m \times n$ times.
- Total steps: $2mn + 2m + 1$ .
Fibonacci Calculation:
- Calculates the $n^{th}$ Fibonacci number using a loop.
- if (n ≤ 1): $1$ step.
- for i := 2 to n do: $n$ steps.
- Inner loop assignments and additions: $(n-1) + (2n-2)$ steps.
- Total steps for n > 1: $T(n) = 4n + 1$ .

Asymptotic Notations and Growth Rates

Purpose: To compare algorithms by looking at their rate of growth as $n$ approach infinity.
Common Notations:
1. Big-OH (O): Upper bound.
2. Big-OMEGA (Ω): Lower bound.
3. Big-THETA (Θ): Tight bound; $f(n) = Θ(g(n))$ if and only if $f = O(g(n))$ and $f = Ω(g(n))$ .
Rate of Growth Concept: Low-order terms are insignificant for large $n$ . For example, $n^4 + 100n^2 + 10n + 50 ≈ n^4$ .
Comparison of Growth Orders (at N = 1,000,000):
- $O(1)$ : $1 μsec$ .
- $O(\log N)$ : $18 μsec$ .
- $O(N)$ : $1 sec$ .
- $O(N \log N)$ : $19.8 sec$ .
- $O(N^2)$ : $11.6 days$ .
- $O(N^3)$ : $31.7 years$ .
- $O(2^N)$ : Practically infinite.
Mathematical Properties:
- Transitivity: If $f(n) = Θ(g(n))$ and $g(n) = Θ(h(n))$ , then $f(n) = Θ(h(n))$ .
- Reflexivity: $f(n) = Θ(f(n))$ .
- Symmetry: $f(n) = Θ(g(n)) \iff g(n) = Θ(f(n))$ .
- Transpose Symmetry: $f(n) = O(g(n)) \iff g(n) = Ω(f(n))$ .

Analysis of Linear Search

Input: Sequence of $n$ numbers and a key.
Operations:
- i ← 1: 1 time.
- while i ≤ n and A[i] != key: executes $x$ times.
- do i++: executes $x-1$ times.
Performance Cases:
- Best Case: Key found at index 1. Execution steps: $1+1+0+1+1 = 4$ . Complexity: $O(1)$ .
- Worst Case: Key not in list. Iterates through all $n$ elements. Execution steps: $1+(n+1)+n+1+1 = 2n+4$ . Complexity: $O(n)$ .
- Average Case: Assume search for random item (executes $n/2$ times). Steps: $1+n/2+n/2+1+1 = n+3$ . Complexity: $O(n)$ .

AVL Trees

Definition: Height-balanced binary search trees (BST).
Balance Factor (BF): $height(left\text{ }subtree) - height(right\text{ }subtree)$ .
Requirements: For every node, the heights of the left and right subtrees can differ by no more than 1. A node is balanced if $BF \in {-1, 0, +1}$ .
- Left-heavy: $BF = -1$ (depending on terminology, some systems use $+1$ for left-heavy; the transcript notes $BF = -1$ as left-heavy and $+1$ as right-heavy).
Rotations (Rebalancing):
- LL Rotation: Single right rotation at node A (where A has $BF = -2$ and its left child has $BF = -1$ or $0$ ).
- RR Rotation: Single left rotation at node A (where A has $BF = +2$ and its right child has $BF = +1$ or $0$ ).
- LR Rotation: Double rotation (left rotation at child B, then right rotation at A).
- RL Rotation: Double rotation (right rotation at child B, then left rotation at A).

m-Way Search Trees

Definition: Multi-way trees where each node contains multiple elements. In a tree of order $m$ , each node has a maximum of $m-1$ elements and $m$ children.
Complexity: Operation access is $O(h)$ , where height $h \approx \log_m(n + 1)$ .
Insertion Cases:
- Non-full leaf: Insert in sorted position.
- Full leaf: Split leaf, promote middle key to parent.
- Full parent: Continue splitting and promoting upward.
- Full root: Split root, create new root, increasing tree height.
Deletion Cases:
- Leaf key: Simple delete.
- Key with one subtree: Replace with largest from left or smallest from right, then delete replacing node.
- Key with both subtrees: Replace with largest from LST or smallest from RST, then delete replacement element.

Disjoint Sets and Union-Find (DSU)

Concept: Collections of non-overlapping sets. Represented as a forest where children point to parents.
Operations:
- Find: Determines the representative/root of the set containing an element.
- Union: Combines two disjoint sets. Make the root of one tree the child of the root of the other.
Array Representation: Array p[1:n] where p[i] is the parent. If p[i] = -1, index $i$ is a root.
Optimization Rules:
- Weighting Rule for Union: Link the root of the smaller tree to the root of the larger tree.
- Collapsing Rule for Find: Update the parent links of all nodes on the path from $i$ to the root to point directly to the root, improving future efficiency.

AND/OR Graphs and Problem Reduction

Representation: Directed graphs where nodes represent problems and edges represent subproblems.
Node Types:
- AND Node: All child subproblems must be solved to solve the parent.
- OR Node: Solving any one child solves the parent.
- Terminal Node: primitive, solvable problems.
Key Traits: AND/OR graphs are not necessarily trees; they can share subproblems or contain cycles. A "Solution Graph" is the subgraph proving solvability.

Graph Traversals

Reachability Problem: Determines if a path exists from vertex $v$ to $u$ .
Breadth First Search (BFS):
- Starts at source, marks as visited, explores all neighbors using a FIFO Queue.
- Complexity for identifying connected components: $Θ(n + e)$ .
Depth First Search (DFS):
- Explores a path as deeply as possible before backtracking using recursion or a stack.
- Assigns a Depth First Number (DFN) based on visit order.
- Tree Edge: Edge in the DFS spanning tree.
- Back Edge: Edge connecting a vertex to its ancestor in the DFS tree.

Connected and Biconnected Components

Connected Graph: All vertices reached in one BFS/DFS traversal.
Spanning Tree: Sub-graph connecting all vertices without cycles (using $n-1$ edges).
Articulation Point (Cut Vertex): A vertex whose removal disconnects the graph. Examples in the lesson include vertices 2, 3, and 5.
Biconnected Graph: Contains no articulation points; provides high fault tolerance.
Biconnected Component: A maximal biconnected subgraph.
DFS in Biconnectivity: Used to compute $L[u] = \min(dfn[u], \min(L[w] \text{ for child } w), \min(dfn[w] \text{ for back edge } (u,w)))$ . An articulation point exists if $L[child] \ge dfn[parent]$ .