[Java] Analysis of Algorithms

📋 This is the notetaking from what I learned from the course!

Analysis of Algorithms

Fundamental Data Structures - Review

Circularly Linked Lists

• Definition: A singly linked list where the next reference of the tail node refers back to the head of the list, instead of being null.
• Uses: Useful for cyclic-order systems like round-robin schedulers.
• Advantages:
  • No need to track the head node separately.
  • Ability to add a rotate() method to move the first element to the end of the list.

Equivalency Testing

• Arrays:
  • Use Arrays.equals for one-dimensional arrays.
  • Use Arrays.deepEquals for multi-dimensional arrays.
• Singly Linked Lists:
  • Implement the equals method to check lengths and verify elements one by one using the equals method.

Cloning Data Structures

• Object’s clone Method: Returns a shallow copy.
• Deep Cloning: Implement your own clone method for a deeper copy.
  • Implement the Cloneable interface.
  • Clone individual elements.

Analysis of Algorithms

Algorithm Basics

• Definition: A data structure is a way of organizing and accessing data. An algorithm is a step-by-step procedure for performing a task in a finite amount of time.
• Goodness: Algorithms and data structures are classified as “good” based on their running times, which is crucial as time is a valuable resource.
• Focus: Characterizing running time as a function of input size.

Running Time Scenarios

• Best-case: Shortest running time scenario.
• Worst-case: Longest running time scenario.
• Average-case: Running time averaged over all possible inputs.
• Example: Linear search in an array:
  • Element could be at the beginning, end, or somewhere in between.

Running Time

• Input to Output: Most algorithms transform input objects into output objects.
• Growth with Input Size: Running time typically grows with input size.
• Focus on Worst Case: Easier to analyze and crucial for applications in games, finance, and robotics.

Experimental Studies

1. Write a program implementing the algorithm.
2. Run the program with various input sizes and note the time needed.
3. Plot the results.

Limitations of Experiments

• Implementation Required: May be difficult.
• Non-Indicative Results: May not reflect running time on all inputs.
• Environment Dependency: Comparisons require the same hardware and software environments.

Theoretical Analysis

• High-Level Description: Uses pseudocode or language-independent descriptions.
• Input Size Function: Characterizes running time as a function of input size.
• All Possible Inputs: Considers all inputs for evaluation.
• Hardware Independence: Evaluates speed independently of the environment.

Pseudocode

Definition

• High-Level Description: More structured than English prose but less detailed than a program.
• Preferred Notation: Hides program design issues.

Example

Algorithm sum(arr):
    Input: an array of integers arr
    Output: the sum of array elements sum

    sum = 0
    for i = 0 to arr.length - 1 do
        sum ← sum + arr[i]
    return sum

Details

• Control Flow: Uses if, while, repeat, for.
• Method Declaration: Algorithm method (arg [, arg...])
• Method Call: method (arg [, arg...])
• Return Value: return expression
• Expressions: Use ← for assignment, = for equality testing.

Random Access Machine (RAM) Model

Components

• CPU: Central processing unit.
• Memory Cells: Unbounded bank, each holding an arbitrary number or character, accessed in unit time.

RAM Model Assumptions

• Single Processor: No concurrent operations.
• Simple Operations: Each takes 1 time step.
• Memory Access: Each access takes one time step.

Running Time

• Time Steps: Number of time steps for running time.
• Space: Number of RAM memory cells used.

Important Functions in Algorithm Analysis

Seven Functions

1. Constant (1)
2. Logarithmic (log n)
3. Linear (n)
4. N-Log-N (n log n)
5. Quadratic (n^2)
6. Cubic (n^3)
7. Exponential (2^n)

Graphing Functions

• Normal Scale: Functions graphed on a normal scale to show growth rates.

Primitive Operations

Definition

• Basic Computations: Performed by an algorithm, identifiable in pseudocode.
• Constant Time: Assumed to take constant time in the RAM model.

Examples

• Evaluating an expression.
• Assigning a value to a variable.
• Indexing into an array.
• Calling or returning from a method.
• Comparing two numbers.
• Following an object reference.

Estimating Running Time

Example

• Algorithm arrayMax:
  • Worst-case: 5n + 5 primitive operations.
  • Best-case: 4n + 5 primitive operations.
• Time Bounds:
  • a (4n + 5) ≤ T(n) ≤ b (5n + 5)
  • Running time is bounded by two linear functions.

Growth Rate

Importance

• Hardware/Software Changes: Affects running time by a constant factor but does not alter the growth rate.
• Intrinsic Property: Linear growth rate of running time is an intrinsic property.
• Constant Factors: Do not matter for growth rate.

Comparison Example

• Insertion Sort: n^2 / 4
• Merge Sort: 2 n log n
• Sorting a Million Items:
  • Insertion sort: 70 hours.
  • Merge sort: 40 seconds (or 40 minutes vs. less than 0.5 seconds on faster machines).

Big-Oh Notation

Definition

• Upper Bound: Provides an upper bound on the growth rate of a function.
• Example: Sequential search in arrays.
  • Best-case: Constant function.
  • Worst-case: Linear function.
  • Expression: Growth rate of f(n) is bounded above by a linear function.

Big-Oh Example

Example: The function `2n + 10` is `O(n)`
- Let `g(n) = n`
- Let `f(n) = 2n + 10`
- Find `c` and `n0` such that `2n + 10 ≤ cn`
- `(c - 2)n ≥ 10`
- `n ≥ 10/(c - 2)`
- Pick `c = 3`, then `n ≥ 10`
- Picking `n0 = 10`, the inequality holds for `n ≥ n0`

Big-Oh and Growth Rate

• Function Comparison: Use big-Oh notation to compare growth rates of functions.
• Example: 3 n^3 + 20 n^2 + 5 is O(n^3)

Rules

1. Drop lower-order terms.
2. Drop constant factors.
3. Use the smallest possible class of functions.
4. Use the simplest expression of the class.

Asymptotic Algorithm Analysis

• Determine: Worst-case number of primitive operations.
• Express: Function with big-Oh notation.
• Example: Algorithm arrayMax runs in O(n) time.

Relatives of Big-Oh

• Big-Omega (Ω): f(n) is Ω(g(n)) if f(n) ≥ c g(n) for n ≥ n0
• Big-Theta (Θ): f(n) is Θ(g(n)) if c’g(n) ≤ f(n) ≤ c’’g(n) for n ≥ n0

Example Code

Prefix Averages (Quadratic Time)

public static double[] prefixAverage1(double[] X) {
    int n = X.length;
    double[] A = new double[n];
    for (int i = 0; i < n; i++) {
        double sum = 0;
        for (int j = 0; j < i; j++)
            sum += X[j];
        A[i] = sum / (i + 1);
    }
    return A;
}

Prefix Averages (Linear Time)

public static double[] prefixAverage2(double[] X) {
    int n = X.length;
    double[] A = new double[n];
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += X[i];
        A[i] = sum / (i + 1);
    }
    return A;
}

Math Review

• Powers and Logarithms:
  • a^(b+c) = a^b * a^c
  • a^(b*c) = (a^b)^c
  • a^b / a^c = a^(b-c)
  • b = a^(log_a b)
  • b^c = a^(c * log_a b)
• Logarithm Properties:
  • log_b(x*y) = log_b x + log_b y
  • log_b (x/y) = log_b x - log_b y
  • log_b x^a = a * log_b x
  • log_b a = log_x a / log_x b
• Summations and Proof Techniques.
• Basic Probability.

---

Back to Top

See other articles in Category Java