Data Structure and Algorithm Design II

Sections

• Math review

• Algorithm analysis

• Amortized analysis

Math Concepts Review

Outline

• Exponents

• Logarithms

• Modular Arithmetic

• Proof methods

Exponents

• Definition: An exponent is a way of expressing repeated multiplication.

• Example: \(2^3 = 2 \times 2 \times 2 = 8\)

• Formula: \(a^n = \underbrace{a \times a \times a \times \ldots \times a}_{n \text{ times}}\)

• Properties

  • Product Rule: \(a^{m+n} = a^m \times a^n\)

  • Quotient Rule: \(a^{m-n} = \frac{a^m}{a^n}\)

  • Power Rule: \((a^m)^n = a^{m \cdot n}\)

  • Fractional Exponent Rule: \(a^{\frac{m}{n}} = \sqrt[n]{a^m}\)

  • Negative Exponent Rule: \(a^{-n} = \frac{1}{a^n}\)

  • Zero Exponent Rule: \(a^0 = 1, a \neq 0\)

Logarithms

• Definition: The logarithm of a number is the exponent to which another fixed value, the base, must be raised to produce that number.

• Example: \(\log_2 8 = 3\) because \(2^3 = 8\)

• Formula: \(\log_b x = y\) if and only if \(b^y = x\)

• Properties

  • Logarithmic Identity: \(\log_b b^x = x\)

  • Exponential Identity: \(b^{\log_b x} = x\)

  • Product Rule: \(\log_b xy = \log_b x + \log_b y\)

  • Quotient Rule: \(\log_b \frac{x}{y}\ = \log_b x - \log_b y\)

  • Power Rule: \(\log_b x^n = n \cdot \log_b x\)

Series

• Definition: A series in mathematics is the sum of terms in a sequence.

• Applications: algorithm analysis in computer science

• Arithmetic series

  • Example: \(1 + 2 + 3 + ... + n = n(n+1)/2\)

  • Formula: \(S_n = \frac{n}{2} \cdot (2a + (n-1)d)\)

  • where:

    • \(n\) is the number of terms,

    • \(a\) is the first term, and

    • \(d\) is the common difference between terms.

• Geometric series

  • Example: \(1 + 2 + 4 + 8 + ... + 2^n = 2^{n+1} - 1\)

  • Formula: \(S_n = \frac{a \cdot (1 - r^n)}{1 - r}\)

  • where:

    • \(a\) is the first term,

    • \(r\) is the common ratio between terms, and

    • \(n\) is the number of terms

Modular Arithmetic

• Definition: In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value—the modulus (plural moduli).

• A.k.a remainder

• Example: \(13 \equiv 1 \pmod{6}\) because \(7 = 1 + 6 \cdot 2\)

• Formula: \(a \equiv b \pmod{n}\) if and only if \(n | (a - b)\)

• Applications: array indexing, hash functions, pseudorandom number generators, etc.

Proof Methods

• Direct Proof

  \(A \Rightarrow B \quad \text{by assuming} \quad A \quad \text{and demonstrating} \quad B.\)

• Proof by Contradiction

  \(\text{Proof by contradiction assumes} \quad \neg A \quad \text{and derives a contradiction, implying} \quad A.\)

• Proof by Induction

  \(\text{Proof by induction involves base case} \quad (n = 1) \quad \text{and inductive step} \quad (k \Rightarrow k+1)\)

  \(\text{to prove statement for all} \quad n.\)

• Proof by Contrapositive

  \(\text{Proof by contrapositive shows} \quad A \Rightarrow B \quad \text{by proving} \quad \neg B \Rightarrow \neg A, \quad \text{its logical equivalent.}\)

Algorithm Analysis

Outline

• Motivation

• Type of Analysis

  • Empirical Analysis

  • Theoretical Analysis

    • Computational Complexity

      • Asymptotic Notation

      • Cases

      • Examples

Overview

• Motivation: To compare algorithms and select the best algorithm for a given problem.

• Types of Analysis

• Empirical Analysis (FYI)

  • Implement, run, and measure the performance of the algorithms.

  • Hardware and software dependent.

  • A simple approach: <chrono> library in C++.

Empirical analysis using <chrono> library

#include <iostream>
#include <chrono>

int main() {
    // Start the clock
    auto start = std::chrono::high_resolution_clock::now();
    // Call the function to be measured
    algorithm(parameter);
    // Stop the clock
    auto end = std::chrono::high_resolution_clock::now();
    // Calculate the duration
    std::chrono::duration<double> duration = end - start;
    // Print the duration in seconds
    std::cout << "Function took " << duration.count() << " seconds." << std::endl;
    return 0;
}

• Theoretical Analysis

  • Mathematical analysis of the algorithms.

  • Hardware and software independent.

  • Computational complexity.

Credit: https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

Computational Complexity

• Definition: The computational complexity of an algorithm is an estimation of the amount of resources required to run it. This model ignores the hardware and software details and focuses on the resources required by the algorithm as the problem size increases.

• Resources: Time, Space, power consumption, network traffic, etc.

• Time Complexity

  • The number of constant time operations performed by the algorithm.

  • A function of the input size n. \(T(n)\) or \(T(N)\)

  • Approximation: All constant time operations are considered one unit of time.

• Space Complexity

  • The amount of storage space (usually memory) required by the algorithm.

  • Auxiliary space: The extra space required by the algorithm, excluding the input size.

  • A function of the input size n. \(S(n)\) or \(S(N)\)

Asymptotic Notation

• Complexity can be a complicated and non-intuitive function and we need a simple way to describe it.

• A.k.a Bachmann–Landau notation. A mathematical notation system to describe the limiting behavior of a function.

• Provides a simple way to describe the complexity of an algorithm.

• Big O notation \(T(n) = O(f(n))\) describes the upper bound of the function \(T(n)\).

• Big Omega notation \(T(n) = \Omega(f(n))\) describes the lower bound of the function \(T(n)\).

• Big Theta notation \(T(n) = \Theta(f(n))\) describes the tight bound of the function \(T(n)\).

• Little o notation \(T(n) = o(f(n))\) describes the strict upper bound of the function \(T(n)\). (FYI)

How bounds work and which one to choose

• Infinite upper and lower bounds exist and we only care the ‘tightest’ ones.

• If exist, the exact bound is the tightest upper and lower bound at the same time. Thus, this is the most helpful bound.

• If big theta does not exist, the tightest upper bound is the most helpful bound.

• E.g. Mark Zuckerberg’s income is an upper bound to your income but it is not helpful to estimate your income because it is not a “tight” upper bound.

Considering Cases

In complexity analysis, various cases are considered to assess the efficiency and performance of algorithms. These cases help us understand how algorithms behave under different scenarios and input distributions.

• Best Case: The minimum amount of resources required by the algorithm.

• Worst Case: The maximum amount of resources required by the algorithm.

• Average Case: The average amount of resources required by the algorithm.

Checkpoint

• How many searching and sorting algorithms do you know so far?

• What is the complexity of each algorithm?

• Is a Merge sort (\(\Theta(n \log n)\)) always faster than an Insertion sort (\(\Theta(n^2)\))?

Answers

• You should have learned

  • Linear search (\(\Theta(n)\))

  • Binary search (\(\Theta(\log n)\))

  • Selection sort (\(\Theta(n^2)\))

  • Insertion sort (\(\Theta(n^2)\))

  • Maybe Bubble sort (\(\Theta(n^2)\))

• As a programmer, we should no longer use the term “faster” to compare algorithms. We should use the term “more or less complex/efficient” instead. Less complex means more efficient. It also means slower growth rate.

• Merge sort is more efficient than Insertion sort in terms of time complexity. However, it is not always faster than Insertion sort. The efficiency of an algorithm depends on the problem size, the input distribution, and the hardware characteristics.

Find \(T(n)\) 1

int search(int * arr, int size, int val) {
  for (int i = 0; i < size; ++i)
    if (arr[i] == val)
      return i;
  return -1;
}

\(T(n)\) of for loops

for (init; condition; update) {
  body statements;
}

Find \(T(n)\) Selection Sort

// Sort an array to ascending order
// arr: array to be sorted, must not be nullptr
// size: must be greater than 0
void selectionSort(int * arr, int size) {
  for (int i = 0; i < size - 1; ++i) {
    int min = i;
    for (int j = i + 1; j < size; ++j)
      if (arr[j] < arr[min])
        min = j;
    if (min != i)
      std::swap(arr[i], arr[min]);
  }
}

Find \(\Theta(f(n))\) given \(T(n)\)

Find \(\Theta(f(n))\) directly

• Much easier than finding \(T(n)\) first.

• additive (sequential, branch)

  • \(\Theta(f(n)) + \Theta(g(n)) = \Theta(f(n) + g(n))\)

  • E.g. Initialize an array and then sort it using selection sort: \(\Theta(n) + \Theta(n^2) = \Theta(n^2)\)

• multiplicative (nested loop, recursion)

  • \(\Theta(f(n)) \times \Theta(g(n)) = \Theta(f(n) \times g(n))\)

  • Where \(f(n)\) and \(g(n)\) are outer loop complexity and per iteration complexity respectively.

  • Examples:

    • Selection sort \(\Theta(n) \times \Theta(n) = \Theta(n^2)\)

    • Binary search \(\Theta(\log n) \times \Theta(1) = \Theta(\log n)\)

    • Merge sort \(\Theta(\log n) \times \Theta(n) = \Theta(n \log n)\)

Algorithms of Certain Complexity

Exercise

• Given the following function:

  bool isReverse(const char* arr1, const char* arr2, int length) {
      for (int i = 0; i < length; ++i)
          if (arr1[i] != arr2[length - 1 - i])
              return false;
      return true;
  }

• What is the best and worst case time complexity function?

• What is the problem size?

• What is the worst case bound? (which bound to use?)

Answers

• Best case is when the first comparison fails. The loop will only run once.

• Worst case is when all comparisons passes or the last comparison fails. The loop will run \(n\) times.

• The problem size is the length of the arrays.

• The worst case bound is \(\Theta(n)\).

Amortized Analysis

• Motivation: To analyze the average time complexity of a sequence of operations performed on a data structure.

• When best, worst, and average cases are not enough to describe the performance of an algorithm or a data structure.

• Types of amortized analysis:

  • Aggregate analysis

  • Accounting method

  • Potential method

• Example of dynamic data structures that require amortized analysis:

  • Dynamic arrays (resizing)

  • Hash tables (rehashing)

  • Self-balancing binary search trees (balancing)

  • Splay trees (splaying)