Unit I: Computational Problem Solving & Algorithms

Problem Analysis

• Problems vs. Instances:

  • A computational problem is a general, formal specification that defines a mapping or relationship between a set of input parameters and a set of desired output values.

  • A problem instance represents a concrete, specific assignment of values to the input parameters defined by a problem.

  • Example:

  • Problem: Given a sequence of $n$ integers, reorder the sequence into monotonically non-decreasing order.

  • Instance: Given the specific array input $[5, 2, 8, 1]$, produce the sorted output $[1, 2, 5, 8]$.

• Generalization vs. Special Cases:

  • Generalization: Designing algorithms that correctly solve all valid instances of a problem without placing artificial constraints on input domain or structure.

  • Special Cases: Specific subsets of problem instances that exhibit structural properties allowing for specialized optimizations or simpler algorithmic solutions.

  • Comparison:

  • General sorting algorithms (e.g., Merge Sort) operate on arbitrary input sequences with a time complexity lower bound of $\frac{n \times \text{log}(n)}{2}$ or asymptotically $\text{O}(n \times \text{log}(n))$.

  • Special-case sorting algorithms (e.g., Counting Sort) leverage specific input properties (such as integers bounded within a small range $[0, k]$) to achieve linear time complexity $\text{O}(n + k)$.

• Types of Computational Problems:

  • Decision Problems: Problems requiring a binary boolean response ($\text{true}$ or $\text{false}$, $\text{yes}$ or $\text{no}$) for a given input instance.

  • Example: Determining whether a given integer $n$ is prime.

  • Search Problems: Problems requiring the identification and retrieval of a specific element or structure from a search space that satisfies defined criteria.

  • Example: Finding the index of a key $k$ within a search array $A$, or returning a symbol indicating absence if $k \notin A$.

  • Optimization Problems: Problems requiring the discovery of the single best solution among all valid candidate solutions, maximizing or minimizing a specific objective function.

  • Example: Finding the shortest path between two vertices in a weighted graph (minimizing path length).

  • Counting Problems: Problems asking for the precise total number of valid solutions or structures that satisfy specified criteria, rather than producing the solutions themselves.

  • Example: Determining the total number of distinct simple paths between two nodes in a graph.

• Problem Analysis and Decomposition:

  • Problem Analysis: The detailed examination of a problem statement to identify explicit and implicit operational requirements, domain constraints, input bounds, and output criteria.

  • Decomposition: The process of breaking a complex, high-level computational problem into smaller, independent, and manageable subproblems (also known as modular design or step-wise refinement).

  • Subproblems are designed such that individual solutions can be independently developed, validated, and subsequently combined to form the solution to the overarching problem.

Four-Stage Problem-Solving Methodology

• Stage 1: Understand Problem:

  • Carefully analyze the problem domain to identify all inputs, expected outputs, constraints, operational boundaries, and edge cases.

  • Explicitly define the types, ranges, formats, and structural characteristics of incoming input data.

  • Identify edge cases, such as empty inputs, single-element collections, boundary value limits, duplicate elements, or negative numbers.

• Stage 2: Plan Strategy:

  • Formulate an algorithmic strategy or paradigm suited to the problem structure (e.g., Divide and Conquer, Greedy Choice, Dynamic Programming, Backtracking, or Brute Force).

  • Select appropriate abstract data types and concrete data structures that minimize computational overhead for required operations.

  • Trace proposed strategies on representative sample inputs and edge cases prior to implementation to establish feasibility.

• Stage 3: Execute Steps:

  • Construct detailed, step-by-step specifications of the algorithm using standardized notation (such as standard pseudocode or flowcharts).

  • Translate the algorithmic blueprint into executable programming code with modular organization and clear variable naming conventions.

  • Implement essential input validation routines to ensure operational bounds are maintained during execution.

• Stage 4: Review / Verify Correctness:

  • Evaluate the execution of the algorithm against a comprehensive battery of test suites, including standard cases, boundary conditions, and invalid inputs.

  • Perform dry runs (manual tracing) on complex logical branches and state modifications.

  • Verify mathematical and logical correctness using formal proofs or assertions (e.g., loop invariants).

Foundations of Algorithms

• Algorithm Specification:

  • An algorithm is a finite, well-defined sequence of step-by-step instructions designed to perform a specific task or solve a computational problem.

  • Specification demands complete clarity, standard syntax, finiteness (guaranteed termination), definiteness (every step is unambiguously defined), and effectiveness (operations are basic and executable).

• Preconditions and Postconditions:

  • Preconditions: Logical predicates or constraints that must hold true before the execution of an algorithm to guarantee correct operation.

  • Example: A binary search algorithm requires the precondition that the input array $A$ is sorted in non-decreasing order ($A[i] \le A[i+1]$ for all valid indices $i$).

  • Postconditions: Logical predicates guaranteed to hold true immediately after execution completes, assuming all preconditions were satisfied.

  • Example: For an array sorting algorithm, the postcondition asserts that the output array $A'$ contains a permutation of original elements such that $A'[i] \le A'[i+1]$ for all valid indices $i$.

• Input Validation:

  • The process of programmatically verifying that all runtime inputs satisfy designated preconditions prior to executing core algorithm steps.

  • Prevents fatal execution errors, infinite loops, memory corruptions, security vulnerabilities, or undefined operational behavior caused by malformed or out-of-bound inputs.

• Algorithm Efficiency (Time and Space):

  • Time Complexity: Measures how the execution time of an algorithm scales as a function of input size $n$

  • Big-O Notation ($\text{O}$): Upper bound representing the worst-case asymptotic runtime growth.

  • Big-Omega Notation ($\Omega$): Lower bound representing the best-case asymptotic runtime growth.

  • Big-Theta Notation ($\Theta$): Tight bound describing exact asymptotic runtime behavior when upper and lower bounds coincide.

  • Space Complexity: Measures total memory consumed by an algorithm as a function of input size $n$

  • Includes fixed space (for code and constants) and auxiliary space (temporary variables, dynamic allocation, call stack frames).

• Correctness Proofs:

  • Mathematical and logical frameworks used to rigorously prove that an algorithm correctly satisfies postconditions for all valid inputs.

  • Loop Invariants: Formal properties of loops used to establish correctness through three main requirements:

  • Initialization: The invariant holds true prior to the first iteration of the loop.

  • Maintenance: If the invariant holds true before an iteration, it remains true before the subsequent iteration.

  • Termination: When the loop terminates, the invariant yields a useful property that proves the algorithm postconditions are met.

Role of Data Structures, Flowcharts, and Pseudocode

• Data Organization and Impact on Algorithmic Efficiency:

  • Data structures define how data is stored, organized, and manipulated in memory.

  • Choice of data structure dictates the time complexity of core operations (access, search, insertion, deletion), which directly impacts overall algorithm efficiency.

  • Examples:

  • Array vs. Linked List: An array provides $\text{O}(1)$ random access by index but requires $\text{O}(n)$ insertion or deletion in the worst case. A linked list provides $\text{O}(1)$ insertion or deletion at known node pointers but $\text{O}(n)$ sequential access time.

  • Array vs. Hash Table: Searching an unsorted array takes $\text{O}(n)$ time, while searching a hash table provides expected $\text{O}(1)$ average time complexity.

  • Array vs. Min-Heap: Finding the minimum element in an unsorted array requires $\text{O}(n)$ comparisons, whereas a Min-Heap yields the minimum element in $\text{O}(1)$ time and allows extraction in $\text{O}(\text{log}(n))$ time.

• Flowchart Standards:

  • Flowcharts provide graphical representations of algorithmic processes and execution flow using standardized geometric symbols:

  • Oval / Pill Shape: Start and End points (Terminators).

  • Rectangle: Process step, execution step, or data assignment.

  • Diamond: Decision or conditional branching step (evaluating boolean condition).

  • Parallelogram: Input and Output operations.

  • Arrows (Flowlines): Control flow direction indicating order of execution.

• Pseudocode Standards:

  • Pseudocode is an informal, high-level, human-readable language used to express the logical structure of an algorithm without syntax restrictions of specific programming languages.

  • Key structural requirements:

  • Clear keyword usage in uppercase (e.g., IF, THEN, ELSE, WHILE, FOR, DO, RETURN).

  • Consistent indentation to explicitly denote code blocks and scope.

  • Unambiguous variable naming and variable assignment operators.

  • Explicit subprogram call and return conventions.