Tags: #◇Computer Science #◇CSALGCM #◇Algorithms and Complexity #◇Problems, Problem Types, and Algorithms

Problems, Problem Types, and Algorithms

◇Overview

In the realm of Computer Science, the systematic approach to formulating and solving problems is paramount. A computational problem is a formalized question that computers can theoretically solve. It is defined strictly by its input and output specifications. Bridging the gap between these inputs and outputs is the algorithm—a rigorous, unambiguous sequence of steps designed to transform an input state into a desired output state, satisfying the problem's criteria.

◇Key Concepts

1. Computational Problems

A computational problem mathematically captures a task that a computer needs to perform.

• Input Specifications: The precise format, type, and constraints of the data provided to the system.
• Output Specifications: The precise format and properties of the data that must be produced relative to the given input.

2. Definition of an Algorithm

An algorithm is a finite sequence of exact, unambiguous instructions that operate on the specified input to produce the correct output in a finite amount of time. Every algorithm must eventually halt, either returning a valid output or indicating that no solution exists.

3. Algorithm Analysis Framework

To critically evaluate an algorithm, we look at three fundamental pillars:

• Correctness: Does the algorithm mathematically guarantee the correct output for every valid input? This often requires rigorous mathematical proofs (e.g., loop invariants, induction). When mathematical proof is intractable, rigorous software testing and evaluation techniques (like property-based testing) are employed.
• Efficiency: How does the resource consumption scale as the input size grows?
  • Time Complexity: The number of basic operations executed as a function of the input size.
  • Space Complexity: The amount of auxiliary memory required as a function of the input size.
• Elegance: Based on Occam's Razor, the simplest solution is often the best. An elegant algorithm avoids unnecessary complexity, making it easier to read, maintain, and verify.

◇Algorithms & Formulas

Computational problems can be classified into several broad types based on the nature of their desired output:

1. Decision Problem: Asks a "YES" or "NO" question.
   • Example: Is integer $N$ a prime number? Is string $S$ a palindrome?
2. Search Problem: Requires finding a specific configuration or path that satisfies a set of constraints.
   • Example: Solving a Sudoku puzzle, navigating a maze (Pathfinding), or finding a sequence of moves to solve a Rubik's cube.
3. Counting Problem: Asks for the total number of valid solutions that satisfy specific constraints.
   • Example: How many distinct paths exist from node $A$ to node $B$ in a Directed Acyclic Graph (DAG)? How many ways can you make change for $100$ using given coin denominations?
4. Optimization Problem: Seeks the "best" solution from a vast pool of valid solutions, minimizing or maximizing a particular objective function.
   • Example: Finding the Shortest Path in a network, the Minimum Spanning Tree of a graph, or generating an optimal Huffman Encoding for data compression.
5. Function Problem: Requires computing a specifically defined mathematical or algorithmic function.
   • Example: Calculating the arithmetic mean or standard deviation of an array, computing the Euler Totient (Phi) function.

◇Code Examples

1. SORT-SEQUENCE (Bubble Sort)

Input: A sequence of $n$ integers $a_1, a_2, \ldots, a_n$.
Output: A permutation of the input $b_1, b_2, \ldots, b_n$ such that $b_{i+1} \ge b_i$ for all $i$.

def bubble_sort(arr):
    """
    Takes an array of integers arr.
    Returns a non-decreasing permutation of arr.
    """
    n = len(arr)
    # Loop from n down to 2
    for i in range(n - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                # Swap elements if they are out of order
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Analysis: The nested loops give this algorithm an $O(N^2)$ time complexity. While not the most efficient, it is highly elegant and simple to implement.

2. COUNT-FACTORS

Input: A positive integer $n$.
Output: An integer $m$ denoting the number of distinct positive integers $k$ that divide $n$.

def count_factors(n):
    """
    Takes a positive integer n.
    Returns an integer denoting the number of factors of n.
    """
    i = 1
    ctr = 0
    while i <= n:
        if n % i == 0:
            ctr += 1
        i += 1
    return ctr

Analysis: This simple algorithm iterates exactly $n$ times, resulting in an $O(n)$ time complexity. (Note: A more efficient approach would iterate up to $\sqrt{n}$).

◇References & Navigation

• Previous Topic: None
• Next Topic: ◇Complexity Analysis
• Related Notes: