Algorithms

JMG

Initial Thoughts

• How would you define “algorithm” in your own words?

• Have you encountered or engaged with an algorithm(s)? Describe your experience(s).

• Can you think of a problem or task for which an algorithm(s) would be useful? Can you think of a problem or task for which an algorithm(s) would not be useful?

• What do you think is the relationship between computers and algorithms?

• What do you think the role of algorithms is in AI?

• Can you place algorithms in a social context? That is, how are or should algorithms be used and viewed in our society?

Overview

Algorithms: Etymology

Algorithms: Historical

Algorithms predate computers and even predate al-Khwarizmi. Examples of very early (perhaps ancient) algorithms include:

• an ancient multiplication method that does not require a multiplication table,

• Heron’s method (anticipated by Babylonian mathematicians) for computing the square root of a number (this is a special case of Newton’s method),

• Sieve of Eratosthense algorithm for prime detection and Archimedes’ approximation of \(\pi\).

• Let’s look integer division as an algorithm ¹.

1. As an exercise, look up and try running one or more of the other algorithms by hand. Even better, write a computer program that implements the algorithm.

Division With Remainder

• We can think of division with remainder as an algorithm.

• \(b = aq + r\), \(0 \leq r < a\)

• It is simply successive subtraction.

Division Algorithm

%%{
  init: {
    'theme': 'base',
    'themeVariables': {
      'primaryColor': '#BB2528',
      'primaryTextColor': '#fff',
      'lineColor': '#F8B229'
    }
  }
}%%
stateDiagram-v2
  s1 --> s2
  s2 --> s3 : Yes
  s2 --> s4 : No
  s4 --> s2
  
  s1 : Input a and b
  s2 : Is b-a negative
  s3 : Output b
  s4 : Replace b by b-a

• Let’s try it by hand.

Euclidean Algorithm

• Division with remainder leads to an even more interesting algorithm.

• The Euclidean algorithm (EA) is an algorithm for finding the greatest common divisor (GCD) of two numbers.

• Begin with two integers \(a\) and \(b\).

• Find the remainder \(r\) in dividing \(b\) by \(a\).

• If \(r\) is not zero, replace \(b\) with \(a\) and \(a\) with \(r\) and repeat.

EA Diagram

%%{
  init: {
    'theme': 'base',
    'themeVariables': {
      'primaryColor': '#BB2528',
      'primaryTextColor': '#fff',
      'lineColor': '#F8B229'
    }
  }
}%%
stateDiagram-v2
  s1 --> s2
  s2 --> s3 
  s3 --> s4 : Yes
  s3 --> s5 : No
  s5 --> s2
  
  s1 : Input a and b
  s2 : Divide b by a get r
  s3 : Is r zero?
  s4 : Output a
  s5 : Replace b w/ a, a w/ c

• Let’s try it by hand.

• Why does this algorithm stop, and why does the algorithm produce the GCD of \(a\) and \(b\)?

Reflection

• Relate the division and Euclidean algorithms with our initial discussion of algorithms.

• What are the key features of the division and Euclidean algorithms that you think should extend to algorithms generally?

• Are there any features of algorithms that are not represented by the division and Euclidean algorithms?

Algorithms as Functions

Note that we can think of the division and Euclidean algorithms in the following ways:

• the division algorithm inputs two integers, does something with those integers, and returns an integer, i.e., the remainder;

• the Euclidean algorithm inputs two integers, repeatedly applies the division algorithm, and returns an integer, i.e. the GCD.

• Many algorithms can be viewed as a “machine” that inputs some information or data, transforms the input, and outputs some information or data.

• Question: Can you think of a mathematical concept that takes input, does something, and returns an output?

• This perspective on algorithms reminds me of functions (functions also appear in the context of computer science).

• As we will discuss in detail later, a computer can be modeled as something that calculates functions. An important question is “which functions are computable”?

• Before getting into all of that, let’s examine computer implementations of the division and Euclidean algorithms.

Division: Implementations

Julia implementation:

function div_w_rem(a::Int,b::Int)::Int
    while b-a >= 0
        b = b-a;
    end
    return b
end

div_w_rem (generic function with 1 method)

Example:

r = div_w_rem(5,12);
println(r)

2

Python implementation:

def div_w_rem(a,b):
    while b-a >= 0:
        b = b-a
    return b

Example:

r = div_w_rem(5,12)
print(r)

2

R implementation:

div_w_rem <- function(a,b){
  while (b-a >= 0){
    b <- b - a
  }
  return(b)
}

Example:

r <- div_w_rem(5,12)
print(r)

[1] 2

EA: Implementations

Julia implementation:

function euc_alg(a::Int,b::Int)::Int
    c = div_w_rem(a,b);
    while c > 0
        b = a;
        a = c;
        c = div_w_rem(a,b);
    end
    return a
end

euc_alg (generic function with 1 method)

Example:

g = euc_alg(21,30);
println(g)

3

Python implementation:

def euc_alg(a,b):
    c = div_w_rem(a,b)
    while c > 0:
        b = a
        a = c
        c = div_w_rem(a,b)
    return a

Example:

g = euc_alg(21,30)
print(g)

3

R implementation:

euc_alg <- function(a,b){
  c <- div_w_rem(a,b)
  while (c > 0){
    b <- a
    a <- c
    c <- div_w_rem(a,b)
  }
  return(a)
}

Example:

g <- euc_alg(21,30)
print(g)

[1] 3

Reflection

• What are some aspects about the implementations of the division and Euclidean algorithms that stand out to you?

Algorithms in AI

• There are different approaches to AI including but not limited to

  • Good Old-Fashioned AI

  • Machine Learning

  • Evolutionary Programming

• We will discuss these topics later in the course.

• The role that algorithms play is different in different approaches to AI.

• In some way or another, algorithms determine how AI systems process information, make decisions, or learn.

• Algorithms, computation, and AI stemmed from investigations into mathematics and logic. Let’s touch upon this.

Entscheidungsproblem

Das Entscheidungsproblem ist gelost, wenn man ein Verfahren kennt, das bei einem vorgelegten Ausdruck durch endlich viele Operationen die Entscheidung uber die Allgemeingultigkeit bzw. Erfullbarkeit erlaubt.¹

The decision problem is solved if one knows a method that allows for the decision about the validity or feasibility through finitely many operations, given an presented expression.²

1. Quoted from Chapter 2 Algorithms: From Al-Khwarizmi to Turing and Beyond from Turing’s Revolution edited by Sommaruga and Strahm

2. Translation courtesy of ChatGPT.

Entscheidungsproblem

David Hilbert

• Entscheidungsproblem (decision problem) posed by Ackerman and Hilbert at the 1928 Bologna Congress

• Mathematics of the 19th century highlighted the need for a better understanding of the foundations of mathematics. This was of major concern to Hilbert and he challenged the mathematics community to address the problems in the foundations of mathematics.

• The Entscheidungsproblem arose from these challenges and essentially asked for a general procedure to determine the validity of a given mathematical statement.

• The resolution of the Entscheidungsproblem produced a formal perspective on algorithms and as a side effect resulted in a framework for theorizing about computation.

Coming Soon: Turing and His Machines

Alan Turing

• Alan Turing derived a negative answer to the Entscheidungsproblem.

• In the process, Turing developed a general concept now known as Turing Machines that is central to the theory of computation.

• Turing machines will be a major topic in the next lecture on computation and computers.

Questions and Discussion

References and Further Reading

1. Algorithms by Panos Louridas

2. Chapter 2 Algorithms: From Al-Khwarizmi to Turing and Beyond from Turing’s Revolution edited by Sommaruga and Strahm

3. The Emperor’s New Mind by Roger Penrose

4. Algorithms from the Book by Kenneth Lange

5. The Universal Computer: The Road from Leibniz to Turing by Martin Davis

6. The Honors Class: Hilbert’s Problems and Their Solvers by Ben Yandell