Algorithms: Definition, Properties, and Euclid's Algorithm

Definition of Algorithm

• A sequence of unambiguous instructions for solving a problem in a finite amount of time, to obtain a required output for any legitimate input.

Properties of an Algorithm

• Definiteness: Each instruction needs to be clear and unambiguous.
• Finiteness: An algorithm must terminate after a finite number of steps.
• Effectiveness: Each step must be sufficiently simple and basic, making it possible to carry out the instructions.
• Input: The range of inputs for which an algorithm works must be clearly specified, accepting zero or more inputs.
• Output: An algorithm must produce at least one output.

Algorithms to Compute GCD

• Focus on algorithms to compute the Greatest Common Divisor (GCD) of two non-zero positive integers.

Euclid's Algorithm

• Based on the repeated application of the equality gcd(m, n) = gcd(n, m mod n) until the second number becomes 0, which gives the GCD.
• Example: gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.
• Algorithm Steps:
  • If n = 0, return m and stop.
  • Divide m by n and assign the value of the remainder to r.
  • Assign the value of n to m and the value of r to n, then return to Step 1.

Consecutive Integer Checking Algorithm

• Step 1: Assign the value of min{m, n} to t.
• Step 2: Divide m by t. If the remainder is 0, go to Step 3; otherwise, go to Step 4.
• Step 3: Divide n by t. If the remainder is 0, return the value of t; otherwise, proceed to Step 4.
• Step 4: Decrease the value of t by 1 and return to Step 2.
• Example: gcd(10, 6) = 2 is found when t=2, as 10%2 = 0 and 6%2 = 0.

Middle School Procedure to Compute GCD

• Step 1: Find the prime factors of m.
• Step 2: Find the prime factors of n.
• Step 3: Identify all the common factors in the two prime expansions.
  • If a common factor p occurs and times in m and n respectively, it should be repeated min{, } times.
• Step 4: Compute the product of all common factors and return it as gcd(m, n).
• The above procedure is not a legitimate algorithm as steps 2 and 3 are not clearly defined.
• Example: If m = 60 and n = 24, then 60 = 2 * 2 * 3 * 5, 24 = 2 * 2 * 2 * 3 and gcd(60, 24) = 2 * 2 * 3 = 12.

Sieve of Eratosthenes

• Used for generating prime numbers.
• Initialize a list of prime candidates with consecutive integers from 2 to n.
• Eliminate multiples of 2 (i.e., 4, 6, and so on).
• Move to the next item on the list, which is 3, and eliminate its multiples.
• No pass for number 4 is needed because its multiples are multiples of 2, and therefore, already eliminated.
• Continue until no more numbers can be eliminated from the list.
• Remaining integers are the primes needed.
• Optimization technique: if p is a number whose multiples are being eliminated, then p*p should not be greater than n, and therefore p cannot exceed √n.
• Example: For n = 25, the generated prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23.

Fundamentals of Algorithmic Problem Solving

• Algorithms are procedural solutions to problems, providing specific instructions rather than direct answers.
• A typical sequence of steps in designing and analyzing an algorithm:
• Understand the problem.
• Decide on computational means (exact vs. approximate solving), data structures, and algorithm design technique.
• Design an algorithm.
• Prove correctness.
• Analyze the algorithm.
• Code the algorithm.

Understanding the Problem

• Before designing an algorithm, thoroughly understand the problem.

Computational Device Capabilities

• Algorithms designed for machines that execute instructions sequentially are called sequential algorithms.
• Algorithms designed for computers capable of executing operations concurrently are called parallel algorithms.

Choosing Between Exact and Approximate Problem Solving

• Decide between solving the problem exactly (exact algorithm) or approximately (approximation algorithm).

Deciding on Appropriate Data Structures

• Choose proper data structures to represent data and for easy manipulation to achieve the required result.

Algorithm Design Techniques

• An algorithmic design technique is a general approach applicable to a variety of problems from different computing areas.

Methods of Specifying an Algorithm

• An early method used flowcharts with geometric shapes to describe algorithms. These are suitable for small, simple problems, but not all types.
• The most widely used options for specifying algorithms are natural language and pseudocode.
  • Natural Language: Easy to use, but the ambiguity of any natural language makes the description of algorithms difficult, since each statement can be interpreted in multiple ways.
  • Pseudocode: A mixture of a natural language and programming language-like constructs, making it more precise than a natural language.

Proving an Algorithm's Correctness

• Prove that the algorithm yields a required result for every legitimate input in a finite amount of time.
• Example: In the GCD algorithm, gcd(m, n) = gcd(n, m mod n) is based on the second number getting smaller in every iteration of the algorithm, and the algorithm stopping when the second number becomes 0.
• A common technique for proving correctness is to use Mathematical Induction.
• To show that an algorithm is incorrect, provide an input instance for which it fails.

Analyzing an Algorithm

• Algorithm analysis involves two kinds of efficiency:
  • Time efficiency: How fast the algorithm runs.
  • Space efficiency: How much memory the algorithm needs.
• Other desirable characteristics are:
  • Simplicity: Simpler algorithms are easier to understand and program, resulting in fewer bugs.
  • Generality: Generalized algorithms can handle varying situations.

Coding an Algorithm

• An algorithm is coded using a suitable data structure in a programming language.

Analysis Framework

• Analysis of algorithms means investigating an algorithm's efficiency regarding running time and memory space.
  • Space complexity is the amount of memory the algorithm requires to run to completion.
  • Time complexity is the amount of computer time the algorithm requires to run to completion.

Measuring an Input's Size

• Time complexity depends on the number of inputs.
• It is logical to investigate an algorithm's efficiency as a function of a parameter n indicating the algorithm's input size.
• Example:
  • The size metric for sorting, searching, and finding the largest element is the size of the list.
  • Degree n can be represented as the algorithm's input size; then the degree becomes the amount of coefficients.
  • For computing the product of two n x n matrices, the natural size measures are matrix order n and the total number of elements N.

Units for Measuring Running Time

• Standard units of time measurements such as seconds and milliseconds can measure an algorithm's running time.
• Drawbacks of above approach:
  • Dependence on the machine specification of a particular computer
  • Dependence on the quality of implementing the algorithm
  • Compiler used in generating the machine code -Difficulty in calculating the actual running time of a program
• For measuring the algorithm's efficiency, a good metric should not depend on the mentioned hardware and software factors.
• One could count the number of times each algorithm operation is executed.
• Another approach is to identify the basic operation (primitive operation) contributing the most to the total running time, and compute the number of times the basic operation is executed on inputs of size n.
• For sorting algorithms, basic operation is a key comparison.
• Matrix multiplication and polynomial evaluation basic operations are multiplication and addition.
  • On most computers, multiplication takes longer time than addition.

Input Size and Basic Operation Examples

• Given a search for a key in a list of n items, the input size is the number of items in the list (n), and the basic operation is key comparison.
• Given the task to sort a list of n items, the input size is the number of items in the list (n), and the basic operation is key comparison.
• When adding two n by n matrices, the input size is the dimension of matrices (n), and the basic operation is addition.
• For polynomial evaluation, the input size is the order of the Polynomial (n), and the basic operation is multiplication.
• If multiplying two n by n matrices, the input size dimension of matrices (n), and the basic operation is multiplication.
• We look at time efficiency by counting the number of times the algorithm's basic operation is executed on input's of size n.
• Let C(n) be the number of times this basic operation should be executed for this algorithm's input of size n and let Cop be how long that algorithm takes to execute on a computer.
• The total running time is approximated to the formula
  • T(n) ≈ Cop . C(n)

Orders of Growth

• It is only when the input size is too large that the functions order of growth matters.
• A logarithmic function grows the slowest.
• An algorithm with a logarithmic basic operation count runs instantaneously on inputs of all realistic sizes.
• Exponential and factorial functions grow so fast that their values become large even for small values of n.
• Algorithms that require an exponential number of operations are practical for only very small problems.

Worst, Best and Average-Case Efficiencies

• Algorithms have different run times, not because input size varies, but because there are a variety of inputs that have differing specifications.
• This affects the difficulty of finding the appropriate outputs, thereby changing the efficiency.

Sequential Search Algorithm

• This shows that the run time can be drastically change, leading to difficulties arising for algorithm size n.

Worst Case Efficiency

• Algorithms get their largest key comparison from either no matching elements or the first element matching the very last one.
• We then analyze the algorithm to check which inputs yield the largest amount count C(n), which allows the formation of Cworst(n).

Best Case Efficiency

• This sees the algorithm run the fastest from the best case input for size n, in terms of efficiency. It analyzes which inputs yield the smallest operation inputs, C(n), and we then compute Cbest(n).
• For sequential search, this is the case when the lists have the first elements equal to the key search. -Cbest(n) = 1 successful = N unsuccessful.

Average Case Efficiency

• The worst and best case do not provide sufficient information about the behaviors of a typical input; because of this, we need more.

Assumptions for Sequential Search

• This assumes that P gives the percentage of a successful search and they are all identical for any given number. Then, we get that Cavg(n) = [1 . P + 2 . P + ... + i . P + ... + n . P] + n . (1 - P) / n From this final formula, if P=1, the average successful search would be (n+1)/2 and unsuccessful = n.

Recapitulation of Analysis Framework

• The efficiency is determined by size rather than how well it operates.
• We differentiate between the best, worst, and average types.
• These have a primary focus towards order of growth as the input increases towards infinity.

Asymptotic Notations

• The main indicator will still be the order of growth for a basic operation count.
• We compare with three notations
• Big Oh (O(g(n)), Big Omega ( Ω(g(n) ) and Big-Theta (O(Big-theta).
• We have running time t(n) being defined as some non negative function g(n) that will compare with the count.
• O(g(n)): The function is represented by a smaller order of growth, and thus follows the definition given after.
• n Є O(n²), 100n + 5 Є O(n²).
• Ω(g(n)): The function has a larger order of growth, and fits the definitions. -1 n(n − 1) ΕΩ(n²)
• (g(n)): The function here has a same order of growth as g(n).
• For everything shown above, the functions follow the definition of which set they originate from.
• If the growth for an algorithm is higher than algorithm2, then the latter runs faster than the first.

Formal Definition of Asymptotic Notations

• Formal Definition: -A function t(n) is said to be in O(g(n)), denoted t(n) \in O(g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer no such that t(n) \le c*g(n) for all n \ge no
• If you are trying to solve the inequality, you can pick whatever numbers are easiest in order to prove the initial inequality.

Rules of Sum Manipulation

-∑ca₁ = c∑ai

• ∑ (a₁ ± b₁) = ∑a₁ ±∑b₁
• ∑ 1 = u − 1 + 1 where 1 ≤ u are some lower and upper integer limits -∑ i = ∑ i = 1 + 2 + ... + n = n(n + 1) ≈ 1 n² € Θ(n²)

Mathematical Analysis of Recursive Algorithms

• Deciding on a parameter than indicating that inputs size Identifying basic algorithm operation
• Check of the operation depends of the same size or not.
• Setting up recurrence relation with appropriate input
• Solving for a recurrence or order of growth solution For simplicity, consider n itself as an indicator of this algorithm.

Tower of Hanoi Problem

• With n disks and the difficulty is placing a larger top on top on a smaller one. To perform these disks of peg 1 to peg 3, we first move the peg from peg one to peg 2, this means the number of disks will equal to the input indicator. The movement involves one disk and clearly affects output. Because of the recurrence and initial, we need them for solving for an amount.

Using limits for Comparing Orders of Growth

• Lim n-> infinity t(n) / g(n) - If we use that it makes calculus easier.
• The 2nd 2 cases involve t(n) and the string of g(n)

Basic Efficiency Classes

• Algorithms scan through the total listing
• We must establish a growth order.

Two Rule Basic Manipulation

• Can't have more terms than the equation
• Simplify notation is 1 and 2.

Basic Efficiency Tips

• Parameter operation
• Checking for what the loop contains.
• The case equals arrays where there is also a large elements