Euclid Algorithms

Provide an example of a simple real-world process that can be described as an algorithm.

Euclid's algorithm is based on the fundamental principle that the greatest common divisor of two integers m and n is the same as the greatest common divisor of n and the remainder of m divided by n.

More specifically, it relies on the equality:

gcd(m, n) = gcd(n, m mod n)

where m mod n is the remainder when m is divided by n. This equality holds true for any pair of positive integers m and n.

The algorithm proceeds by repeatedly applying this equality until the second number becomes zero. At that point, the first number is the GCD.

pseudo-code for Euclid's algorithm:

ALGORITHM Euclid(m, n)
//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, both-non-zero integers m and n
//Output: Greatest common divisor of m and n

while n ≠ 0 do
	r <- m mod n
	m <- n
	n <- r
return m

The algorithm is guaranteed to terminate because the value of n (the second integer) strictly decreases with each iteration, and it can never become negative. Eventually, n must reach 0, at which point the loop terminates and the GCD is found.

Computing the greatest common divisor using Euclid's algorithm

Algorithm Steps:

1. If n = 0, return m as answer and stop.

2. Otherwise, compute r = m mod n. (Divide m by n and assign the value of remainder to r)

3. Assign m = n, n = r, and repeat from step 1.

The value of the second number in the pair eventually becomes 0, and the algorithm stops.

Example: GCD(60, 24)

GCD(60, 24) = GCD(24, 60 mod 24) = GCD(24, 12)

GCD(24, 12) = GCD(12, 24 mod 12) = GCD(12, 0)

GCD = 12

Illustrate the prime factorization method to find the GCD of two specific numbers, for example, 180 and 30.

Applying Euclid's Algorithm to Find GCD(180, 30)

Let's compute GCD(180, 30) using Euclid's algorithm:

1. Initial call: gcd(180, 30)

   • Divide 180 by 30: 180 = 6 * 30 + 0
   • The remainder (r) is 0.
   • According to the algorithm, if n (which is 30) is not 0, we assign n to m and r to n.
   • However, since the remainder r is 0, the algorithm stops.

2. Result: The algorithm returns the value of m (the value of n from the previous step), which is 30.

Therefore, GCD(180, 30) = 30.

Middle-school procedure for computing the GCD.

This method involves finding the prime factors of each number and then identifying their common components.

1. Find the prime factorization of the first number, 180.

   • 180 = 10 * 18
   • = (2 * 5) * (2 * 9)
   • = 2 * 5 * 2 * 3 * 3
   • = 2² * 3² * 5¹

2. Find the prime factorization of the second number, 30.

   • 30 = 3 * 10
   • = 3 * (2 * 5)
   • = 2¹ * 3¹ * 5¹

3. Identify the common prime factors and their lowest powers present in both factorizations.

   • The common prime factors are 2, 3, and 5.
   • For each common factor, we take the minimum (lowest) power from their respective factorizations:
     • Lowest power of 2 is 2¹ (from 30, as 180 has 2²).
     • Lowest power of 3 is 3¹ (from 30, as 180 has 3²).
     • Lowest power of 5 is 5¹ (present in both).

4. Multiply these common prime factors raised to their lowest powers to find the GCD.
   GCD(180, 30) = 2¹ * 3¹ * 5¹ = 2 * 3 * 5 = 30

---

Finding GCD(31415, 14142)

Let's apply Euclid's algorithm to find the GCD of 31415 and 14142:

1. gcd(31415, 14142)
   • r = 31415 mod 14142 = 3131
   • New pair: gcd(14142, 3131)
2. gcd(14142, 3131)
   • r = 14142 mod 3131 = 1618
   • New pair: gcd(3131, 1618)
3. gcd(3131, 1618)
   • r = 3131 mod 1618 = 1513
   • New pair: gcd(1618, 1513)
4. gcd(1618, 1513)
   • r = 1618 mod 1513 = 105
   • New pair: gcd(1513, 105)
5. gcd(1513, 105)
   • r = 1513 mod 105 = 43
   • New pair: gcd(105, 43)
6. gcd(105, 43)
   • r = 105 mod 43 = 19
   • New pair: gcd(43, 19)
7. gcd(43, 19)
   • r = 43 mod 19 = 5
   • New pair: gcd(19, 5)
8. gcd(19, 5)
   • r = 19 mod 5 = 4
   • New pair: gcd(5, 4)
9. gcd(5, 4)
   • r = 5 mod 4 = 1
   • New pair: gcd(4, 1)
10. gcd(4, 1)
    • r = 4 mod 1 = 0
    • New pair: gcd(1, 0)

Since n is now 0, the algorithm returns m, which is 1. Therefore, GCD(31415, 14142) = 1. This example required 11 divisions.

Efficiency

Euclid's algorithm is remarkably efficient. It is much faster than other methods for computing GCD, such as the consecutive integer checking algorithm or the prime factorization method.

For instance, to find gcd(31415, 14142), Euclid's algorithm performs only 11 divisions, whereas the consecutive integer checking algorithm would require between 14142 and 28284 divisions, making Euclid's algorithm approximately 1300 to 2600 times faster.

The time efficiency of Euclid's algorithm is in O(log n), where n is the smaller of the two input numbers.

Its worst-case inputs are pairs of consecutive Fibonacci numbers. For example, to compute the GCD of F(n) and F(n-1), Euclid's algorithm needs n-2 divisions for n >= 3.

Justify the statement: “More than one algorithmic method can be used for solving the same problem.” Do this by:

Different algorithms can approach the same task using vastly different ideas, levels of sophistication, and resulting efficiencies. The problem of computing the Greatest Common Divisor (GCD) of two integers serves as a prime example of this phenomenon, with distinct methods offering varied performance and characteristics.

Here, we will describe and compare two distinct algorithms for computing the GCD: Euclid's algorithm and the Middle-School Procedure (Prime Factorization Method).

a) Describing Two Distinct Algorithms for Computing the Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two nonnegative, not-both-zero integers m and n, denoted gcd(m, n), is the largest integer that divides both m and n evenly, i.e., with a remainder of zero.

1. Euclid's Algorithm

Euclid's algorithm, is based on the fundamental principle that the greatest common divisor of two integers m and n is the same as the greatest common divisor of n and the remainder of m divided by n. This can be expressed by the equality:

gcd(m, n) = gcd(n, m mod n)

The algorithm repeatedly applies this equality until the second number (n) becomes zero. At that point, the first number (m) is the GCD, because gcd(m, 0) = m.

Pseudocode for Euclid's Algorithm:

ALGORITHM Euclid(m, n)
//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n != 0 do
    r ← m mod n
    m ← n
    n ← r
return m

The algorithm is guaranteed to terminate because the value of n (the second integer) strictly decreases with each iteration and cannot become negative, eventually reaching 0. This method is a variable-size-decrease algorithm as the size reduction pattern varies from one iteration to another.

Example: Finding GCD(180, 30) using Euclid's Algorithm

1. gcd(180, 30)

   • Divide 180 by 30: 180 = 6 * 30 + 0
   • The remainder (r) is 0.

2. Since the remainder is 0, the algorithm stops and returns the value of m (which was n in the previous step). Therefore, GCD(180, 30) = 30.

2. Middle-School Procedure (Prime Factorization Method)

This procedure for finding the GCD is typically taught in middle school. It relies on finding the prime factors of each number.

Steps for the Middle-School Procedure:

1. Find the prime factors of the first number (m).
2. Find the prime factors of the second number (n).
3. Identify all the common factors in the two prime expansions. If a prime factor p occurs p_m times in m and p_n times in n, it should be repeated min{p_m, p_n} times in the common factors.
4. Compute the product of all these common factors and return it as the GCD.

Example: Finding GCD(180, 30) using the Middle-School Procedure

1. Prime factorization of 180: 180 = 10 * 18 = (2 * 5) * (2 * 9) = 2 * 5 * 2 * 3 * 3 = 2² * 3² * 5¹
2. Prime factorization of 30: 30 = 3 * 10 = 3 * (2 * 5) = 2¹ * 3¹ * 5¹
3. Identify common prime factors and their lowest powers:
   • Common factor 2: Lowest power is 2¹ (from 30).
   • Common factor 3: Lowest power is 3¹ (from 30).
   • Common factor 5: Lowest power is 5¹ (from both).
4. Multiply these common factors: GCD(180, 30) = 2¹ * 3¹ * 5¹ = 2 * 3 * 5 = 30

b) Analyzing and Comparing these Two Algorithms

The two algorithms for GCD, while yielding the same correct result, differ significantly in their efficiency and their standing as strictly defined algorithms.

• Efficiency:

  • Euclid's algorithm is remarkably efficient and much faster than the middle-school procedure. Its time efficiency is in O(log n), where n is the smaller of the two input numbers. For instance, to find gcd(31415, 14142), Euclid's algorithm required only 11 divisions, significantly fewer than the thousands of divisions the consecutive integer checking algorithm (another brute-force method) would need. The worst-case inputs for Euclid's algorithm are consecutive Fibonacci numbers.

  • The middle-school procedure is "much more complex and slower" than Euclid's algorithm. The process of finding prime factors, especially for large numbers, can be computationally intensive and time-consuming.

• Algorithmic Legitimacy/Definition:

  • Euclid's algorithm is a legitimate algorithm. It provides a "sequence of unambiguous instructions for solving a problem... in a finite amount of time". Its correctness stems from the mathematical equality gcd(m, n) = gcd(n, m mod n) and the fact that the second integer decreases with each iteration until it reaches zero.

  • The middle-school procedure, "in the form presented, does not qualify as a legitimate algorithm". The primary reason is that its "prime factorization steps are not defined unambiguously" without further, more complex clarification. For example, the process requires knowing how to obtain a list of prime numbers, which itself needs an algorithm (like the Sieve of Eratosthenes). This means that the core steps of prime factorization are not, by themselves, elementary, unambiguously defined operations within the algorithm's description.

In summary, while both methods correctly compute the GCD, Euclid's algorithm stands out as a more efficient and rigorously defined algorithmic solution, highlighting how different approaches can tackle the same problem with varying degrees of practicality and theoretical elegance.

---

Not Answered / Not Covered

Explain the concepts of a graph and a weighted graph, using examples.

Describe the two primary methods for representing graphs in computer memory (e.g., adjacency matrix, adjacency lists). Provide an example for each method.

Graph

A graph is a set of nodes (also called vertices) and edges (connections between nodes).

Formally, a graph G is defined by a pair of two sets: a finite nonempty set V of vertices and a set E of pairs of these items called edges.

• Nodes represent entities.
• Edges represent relationships between those entities.

There are two primary types of graphs based on the nature of their edges:

• Undirected Graphs: In an undirected graph, edges are unordered pairs of vertices (u, v), meaning that the pair (u, v) is the same as (v, u). Vertices u and v are considered adjacent to each other and are connected by the undirected edge (u, v).

• Directed Graphs (Digraphs): In a directed graph, edges are ordered pairs of vertices (u, v), meaning (u, v) is not the same as (v, u). The edge (u, v) is said to be directed from the vertex u (tail) to the vertex v (head). It is also described as leaving u and entering v.

A weighted graph (or weighted digraph) is a graph (or digraph) where numbers are assigned to its edges. These numbers are referred to as weights or costs and are often used to represent values such as distances, capacities, or costs between connected vertices.

Important applications of weighted graphs include finding the shortest path between two points or solving the traveling salesman problem.

Graphs can also have other properties:

• Loops: Edges connecting a vertex to itself. Unless explicitly stated, graphs are generally considered without loops.

• Complete Graph: A graph where every pair of its vertices is connected by an edge.

• Dense vs. Sparse Graphs: A dense graph has relatively few possible edges missing, while a sparse graph has few edges relative to its number of vertices. This distinction can influence the choice of graph representation and algorithm efficiency.

• Connected Graph: A graph is connected if there is a path between every pair of its vertices. If a graph is not connected, it consists of several connected components.

• Acyclic Graph: A graph with no cycles (a path of positive length that starts and ends at the same vertex and does not traverse the same edge more than once). A connected acyclic graph is called a tree.

Primary Methods for Representing Graphs in Computer Memory

Graphs for computer algorithms are typically represented in one of two main ways: the adjacency matrix or adjacency lists. The choice between these representations often depends on the nature of the problem, the algorithm used, and whether the graph is sparse or dense.

Adjacency Matrix : The adjacency matrix of a graph with n vertices is an n × n Boolean matrix. It has one row and one column for each vertex.

For unweighted graphs: An element in the i-th row and j-th column is 1 if there is an edge from the i-th vertex to the j-th vertex, and 0 if there is no such edge.

Graph: A ↔ B, A ↔ C, B ↔ C, C ↔ D
Unweighted adjacency matrix:

    A  B  C  D
A [ 0  1  1  0 ]
B [ 1  0  1  0 ]
C [ 1  1  0  1 ]
D [ 0  0  1  0 ]

weighted graphs: The element A[i, j] will contain the weight of the edge from the i-th to the j-th vertex if such an edge exists, and a special symbol (e.g., ∞) if there is no such edge. This is called a weight matrix or cost matrix.

Weighted adjacency matrix (distance as weight, 0 means no edge to itself, ∞ for no connection):

    A    B    C    D
A [ 0    5    3   ∞ ]
B [ 5    0    2   ∞ ]
C [ 3    2    0   4 ]
D [ ∞    ∞    4   0 ]

Easy to check if two vertices are connected (O(1) lookup). Good for dense graphs.

---

Adjacency Lists : Adjacency lists are a collection of linked lists, one for each vertex, that contain all the vertices adjacent to that vertex. Each list typically starts with a header identifying the vertex for which the list is compiled.

For unweighted graphs: Each node in a linked list simply contains the name of an adjacent vertex.

Same graph: A ↔ B, A ↔ C, B ↔ C, C ↔ D

Unweighted adjacency list:

A: [B, C]
B: [A, C]
C: [A, B, D]
D: [C]

For weighted graphs: Nodes in the adjacency lists must include not only the name of an adjacent vertex but also the weight of the corresponding edge.

Weighted adjacency list:

A: [(B, 5), (C, 3)]
B: [(A, 5), (C, 2)]
C: [(A, 3), (B, 2), (D, 4)]
D: [(C, 4)]

Properties:

• For directed graphs, an edge (u, v) only appears in u's adjacency list, unlike undirected graphs where it would implicitly appear in both u's and v's lists in some forms of representation.

• The space efficiency is Θ(|V| + |E|).

• It is generally more space-efficient for sparse graphs compared to adjacency matrices.

• Efficient for sparse graphs (space = O(V + E)).

• Easy to iterate over neighbors.

• Checking if two vertices are connected can take O(degree of vertex) time.