Algorithm Analysis

CMPUT 175 Introduction to Foundations of Computing

Algorithm Analysis Post-test

• This document includes vignettes on:

  • Objects and Classes

  • Fibonacci sequences

Objectives

• Understand performance differences between various algorithm solutions to the same problem.

• Recognize the significance of algorithm analysis in programming.

• Learn about "Big-O" notation to describe execution times for algorithms.

• Introduction to algorithm techniques.

• Importance of making the right choice regarding data structures and their implementations in Python.

What is an Algorithm?

• Definition: A step-by-step procedure to solve a specific problem.

• Characteristics:

  • Well-specified procedure using input values to produce output values.

  • Sequence of computational steps to transform input into output.

  • Analogous to a recipe transforming ingredients (input) into a dish (output).

Example of an Algorithm

• Input: An array of numbers [25, 90, 53, 23, 11, 34]

• Output: The smallest number in the array, which is 11.

• Algorithm Steps:

  • Initialize m with the first element of the array.

  • Iterate through the array to check if any other element is smaller than m.

  • Update m to the smaller element if found.

  • Return m as the smallest number.

What is a Program?

• Definition: An implementation of an algorithm in a programming language.

• Characteristics:

  • Programming languages have specific grammar and syntax.

  • Python is one example of many programming languages, each designed to communicate instructions to a computer.

Program vs. Algorithm

• Relationship:

  • An algorithm is essential for any program; without it, no program can exist.

  • Algorithms should be expressed in high-level language before translating them to programs.

  • Algorithms can be implemented using various programming languages such as:

    • Old languages: Fortran, PL/I, COBOL, Pascal, BASIC, C, etc.

    • Common languages: Java, C++, Python, JavaScript, Perl, etc.

Algorithm Implementation Example

• Examples of implementations in programming languages to find the smallest number:

  int main()  
  { 
      int numbers[6] = {25, 90, 53, 23, 11, 34};  
      int i, m = numbers[0];  
      for (i = 1; i < sizeof(numbers); i++) { 
          if (m > numbers[i]) { 
              m = numbers[i];  
          }  
      }  
      printf(m);  
      return 0;  
  } 

• Other implementations in Python, Pascal, Perl, and more illustrate the algorithm visually with similar logic.

Study of Algorithms

• Key aspects:

  • Analyze how to measure the performance of algorithms.

  • Analyze an algorithm’s running time without coding it.

  • Devise algorithms using various techniques.

  • Validation and testing of algorithms and programs.

Analysis Criteria for Algorithms

• Essential to assess:

  • Execution time: Time complexity.

  • Memory utilization: Space complexity.

  • Search for the optimal solution: Potentially better alternatives.

Comparing Algorithms

• Comparison based on the resources utilized by each algorithm.

• An algorithm is more efficient than another if it uses fewer resources or performs better with resource allocation.

• Benchmarking involves analyzing execution time (running time) and memory usage.

Problem Example: Summing the First n Numbers

• Analysis of two algorithms performing the same task, with one being more readable but both providing the same execution results.

  def sum1(n):  
      theSum = 0  
      for i in range(1, n+1):  
          theSum += i  
      return theSum  
  
  def myFunction(something):  
      me = 0  
      for alpha in range(1, something + 1):  
          me += alpha  
      return me  

Fibonacci Sequence

• Problem: Compute Fibonacci numbers defined by the relation:

  • F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2.

• Noticed relationship to the golden ratio and how Fibonacci numbers approach this ratio.

Fibonacci Algorithm Implementation

• Multiple implementations of Fibonacci sequences including:

  • Iterative, recursive, recursive with caching, and use of the golden ratio.

Benchmarking Fibonacci Algorithms

• Performance measures showed that different algorithms had varied execution times; iterative solutions performed optimally, caching techniques reduced repeated calculations, while direct recursion was inefficient.

Performance Metrics of Algorithms

• Algorithms can be analyzed based on the number of operations required to solve a problem, rather than actual CPU cycle time.

• Asymptotic performance, Big-O notation helps classify algorithm efficiency in terms of the growth rate of these operations relative to input size.

Growth Rates of Algorithms

• Various growth rates are presented, such as linear, logarithmic, polynomial, and exponential.

• Comparative analysis of different Fibonacci algorithms shows notable time complexity differences.

Conclusion

• Understanding the performance of algorithms through analyzing time and space complexity is crucial.

• Selection of appropriate data structures can significantly impact the execution efficiency of algorithms.

• Techniques such as dynamic programming and divide-and-conquer strategies provide efficient methods for problem-solving.