Implementing Algorithms Using Control Structures

Simple Numeric Algorithms

Let's start with some basic numeric algorithms that demonstrate conditional statements and loops.

Algorithm 1: Factorial Calculation

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It's denoted as n! and is a fundamental calculation in mathematics and computing.

Implementation

def factorial(n):
    """
    Calculate the factorial of a non-negative integer n.
    
    Args:
        n: A non-negative integer
        
    Returns:
        The factorial of n (n!)
    """
    # Handle base cases and input validation
    if not isinstance(n, int) or n < 0:
        raise ValueError("Input must be a non-negative integer")
    
    if n == 0 or n == 1:
        return 1
    
    # Calculate factorial using a loop
    result = 1
    for i in range(2, n + 1):
        result *= i
    
    return result

# Test cases
print(f"factorial(0) = {factorial(0)}")  # 1
print(f"factorial(1) = {factorial(1)}")  # 1
print(f"factorial(5) = {factorial(5)}")  # 120
print(f"factorial(10) = {factorial(10)}")  # 3628800

Analysis

This algorithm demonstrates:

• Conditional statements for handling base cases and input validation
• A for loop for iterating through a range of numbers
• The accumulation pattern, where we build up a result through repeated operations

Notice how we handle edge cases (0 and 1) differently, since their factorials are defined as 1. This is a common pattern in algorithm implementation: identify special cases and handle them separately.

Algorithm 2: Prime Number Check

A prime number is a natural number greater than 1 that is not divisible by any positive integer other than 1 and itself. Checking whether a number is prime is a classic algorithm with applications in cryptography and number theory.

Implementation

def is_prime(n):
    """
    Check if a number is prime.
    
    Args:
        n: An integer to check
        
    Returns:
        True if n is prime, False otherwise
    """
    # Handle special cases
    if n < 2:
        return False
    
    if n == 2:
        return True
    
    # Even numbers greater than 2 are not prime
    if n % 2 == 0:
        return False
    
    # Check odd divisors up to the square root of n
    # We only need to check up to the square root because
    # if n has a divisor larger than sqrt(n), it must also
    # have a smaller divisor already checked
    sqrt_n = int(n ** 0.5) + 1
    
    for divisor in range(3, sqrt_n, 2):
        if n % divisor == 0:
            return False
    
    return True

# Test cases
for num in [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 17, 19, 20, 23]:
    print(f"{num} is {'prime' if is_prime(num) else 'not prime'}")

Analysis

This algorithm demonstrates:

• Multiple conditional statements to handle special cases efficiently
• A for loop with a step parameter to iterate only through odd numbers
• Early return to terminate the function as soon as we know the answer
• Mathematical optimization by only checking divisors up to the square root

The optimization techniques used here significantly improve the algorithm's efficiency. For large numbers, checking every possible divisor would be impractical. By handling even numbers separately and only checking divisors up to the square root, we greatly reduce the number of iterations required.

Algorithm 3: Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. This sequence appears throughout nature and mathematics.

Implementation

def fibonacci_sequence(n):
    """
    Generate the first n numbers in the Fibonacci sequence.
    
    Args:
        n: The number of Fibonacci numbers to generate
        
    Returns:
        A list containing the first n Fibonacci numbers
    """
    # Handle edge cases
    if n <= 0:
        return []
    
    if n == 1:
        return [0]
    
    # Initialize the sequence with the first two Fibonacci numbers
    fib_sequence = [0, 1]
    
    # Generate the rest of the sequence
    for i in range(2, n):
        # Next number is the sum of the previous two
        next_fib = fib_sequence[i-1] + fib_sequence[i-2]
        fib_sequence.append(next_fib)
    
    return fib_sequence

# Test cases
print(f"fibonacci_sequence(0) = {fibonacci_sequence(0)}")   # []
print(f"fibonacci_sequence(1) = {fibonacci_sequence(1)}")   # [0]
print(f"fibonacci_sequence(2) = {fibonacci_sequence(2)}")   # [0, 1]
print(f"fibonacci_sequence(10) = {fibonacci_sequence(10)}")  # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Analysis

This algorithm demonstrates:

• Special case handling for small input values
• List manipulation, including initialization and appending
• A pattern where each new value depends on previously computed values
• Using array indexing inside a loop

The Fibonacci sequence is a classic example of a recurrence relation, where each term depends on previous terms. This implementation stores all the Fibonacci numbers in a list, making it memory-efficient for small values of n but potentially memory-intensive for large values.