Module 1: Preliminaries

An example of computing with integers: Euclid's GCD algorithm:

• For positive integers \(m\) and \(n\), \(GCD(m,n) \defn \) the largest integer that divides both \(m\) and \(n\).

• The symbol \(\defn\) means "is defined as".

• Example:
  • 48 has divisors 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
  • 32 has divisors 1, 2, 4, 8, 16, 32.
  • Thus, GCD (32, 48) = 16.

• Algorithm 1:
  • Factorize \(m\) and \(n\) separately.
  • Search factors to find largest common factor.

• Analysis of Algorithm 1: factorization is hard.
       ⇒ No polynomial-time algorithm is known.

• Some observations:
  • Suppose \(m \gt n\) and \(k\) divides both.
         ⇒ Then \(k\) divides \((m - n)\).
  • In fact, as long as these numbers are positive, \(k\) divides \((m - n), (m - 2n), (m - 3n) \ldots \)
  • What is the smallest positive number in this list?
         ⇒ \(m \mmod n\)
  • Thus, \(GCD (m, n)\) divides \(m \mmod n\).
  • And because \(GCD (m, n)\) already divides \(n\), it's among the common divisors of both \(n\) and \(m \mmod n\).
  • Any of these common divisors of \(n\) and \(m \mmod n\) must also divide \(m\), in particular, the largest one, \(GCD (n, m \mmod n)\).
  • Thus, \(GCD (m, n) \eql GCD (n, m \mmod n)\).
         ⇒ Divide and conquer!

  Algorithm 2 (Euclid): (in Java)

       Algorithm: gcd (m, n)
       Input: integers m, n > 0
  
            // Check for bad input.
       1.   if n > m
       2.       return gcd (n,m)
       3.   endif
       
            // The algorithm.
       4.   if n = 0
       5.       return m;
       6.   else
       7.       return gcd (n, m mod n)
       8.   endif
       

• Analysis:
  • Note that \(m \mmod n \lt n\).
  • If \(n \leq \dv{m}{2}\), then \(m \mmod n \;\;\lt \;\; n \;\;\leq \;\; \dv{m}{2}\).
  • If \(n \gt \dv{m}{2}\), then \(m \mmod n \eql m - n \;\;\leq\;\; \dv{m}{2}\).
  • Thus, the larger number is reduced by \(\dv{1}{2}\) each time.
         ⇒ Thus, the running time is at most \(O(\log m)\).

A few more observations:

• Euclid's algorithm is recursive.

• The size of the problem is small:
       ⇒ We need \(O(\log m)\) bits to represent the numbers.

• The running time is linear in the size of the problem.

As it turns out, these characteristics (recursion, problem-size) are classically associated with discrete algorithms.
     ⇒ Algorithms for continuous structures rarely have these properties.

Now let's look at real numbers:

• Informally, we think of real numbers as "possibly having digits after the decimal point."

• Examples: 3.141, 2.718.

  In-Class Exercise 1: Are integers also real numbers? What are rational numbers and how are they different from integers or reals?

• As it turns out, a careful definition is not trivial.

• We know that no integer exists between 5 and 6, but given any two real numbers, there is another real between them.

  In-Class Exercise 2: What about rationals? Is there a rational number between every two rationals?

Countability:

• For finite sets, the size of the set is the number of elements.

• For infinite sets, it's a little more complicated:
       ⇒ Two infinite sets A and B have the same cardinality if there is a 1-1 mapping between their elements.

  In-Class Exercise 3: How do the sizes of the naturals compare with the integers? What about the size of the rationals compared to integers?

• The size of the reals is much larger than that of integers: (Proof by contradiction)
  • Suppose that integers and reals had the same size.
         ⇒ Then, there is a 1-1 mapping
         ⇒ Then, one could list the reals according to this mapping

    1. \(r_1\)
    2. \(r_2\)
    3. \(r_3\)
    ....

  • Consider the real number \(s\) constructed as follows: the \(i\)-th digit of \(s\) differs from the \(i\)-th digit of \(r_i\).
  • Then, \(s\) is not in the list.
         ⇒ A contradiction!

Consider a computational problem with real numbers: finding square roots.

• Suppose we want to find the square-root of a number, e.g., \(3\).

• Define the function \(f(x) = x^2 - 3\).

• Then the solution of the equation \(f(x) = 0\) is what we want.

• Notice: \(f(x) = 0\) is where \(f(x)\) cuts the x-axis.
       ⇒ It must be below \(0\) just before and above \(0\) just after (or vice-versa).
       ⇒ There is some interval \([a,b]\) that surrounds the solution where \(f(a)\) and \(f(a)\) are of opposite sign.

• For our problem, take \(a=0\) and \(b=2\).

• Key ideas in algorithm:

  

  • At each step, reduce the size of the interval by half.
  • Compute \(f(m)\) where \(m = \dv{(a+b)}{2}\).
  • Decide whether to "move" \(a\) or \(b\) based on whether \(m\) is on the same side of \(a\) or \(b\).
         ⇒ i.e., whether \(f(m)\) has the same sign as \(f(a)\) or \(f(b)\).

• Pseudocode:

       Algorithm: Bisection (a, b, f)
       Input: real numbers a,b where a < b, and function f
       1.    m = (a + b) / 2
       2.    while f(m) not close enough to zero
       3.        if f(m) < 0
       4.            a = m
       5.        else
       6.            b = m
       7.        endif
       8.        m = (a + b) / 2
       9.    endwhile
       10.   return m
       

• Sample Java code: Bisection.java.

In-Class Exercise 4: In the above example, we knew that \(f(a) \lt 0\). Re-write the pseudocode to make it more general: replace the test \(f(m)\lt 0\) with a test to see if \(f(a)\) and \(f(m)\) are of the same sign. Modify the code in Bisection.java accordingly.

In-Class Exercise 5: Examine the code in Bisection.java:

• Use a calculator to compute \(\sqrt{3}\) and compare with the output of the program. How would you increase the accuracy of the program?
• Can the bisection() method be written recursively? What would that do to efficiency?

1.2   Some interesting tidbits about real numbers

In no particular order, here are some interesting facts about real numbers:

• What is an irrational number? A real number that's not rational.
  • A rational can be expressed as a ratio of integers: \(r = \dv{p}{q}\), where \(p, q\) are integers.
  • How do we know irrational numbers exist? Example: \(\sqrt{2}\).

• Proof that \(\sqrt{2}\) is irrational:
  • Assume that \(\sqrt{2}\) is rational.
  • Express \(\sqrt{2}\) as \(r = \dv{p}{q}\) where the fraction \(\dv{p}{q}\) cannot be reduced.
  • Then, \(\dv{p^2}{q^2} = 2 \) $$\eqb{ \implies & p^2 \eql 2 q^2 \\ \implies & p^2 \mbox{ is even}\\ \implies & p \mbox{ is even}\\ }$$
  • By a similar argument (can you explain?), \(q\) is even.
         ⇒ Contradicts the assumption that the fraction is reduced.

• We know that rationals and integers are of the same cardinality.
       ⇒ The irrationals are uncountable.

• Most famous real number constants are irrational, e.g. \(\pi, e\). (Proofs are not straightforward)

• Numbers that are solutions of some polynomial with integer coefficients are called algebraic,
       e.g., \(\sqrt{2}\) is the solution of \(x^2 - 2 = 0\).

• Another example: \(\Phi\), the golden ratio is the solution to \(x^2 - x - 1 = 0\).

• Real numbers that are not algebraic are called transcendental
       e.g, \(\pi, e\)

• The real number system is unique:
  • One can describe properties that define the real number system.
         ⇒ For example: closure with respect to arithmetic, existence of a least-upper-bound.
  • One can show: any number system with these properties must be equivalent to the real number system.

• The continuum hypothesis: there is no set whose countability lies between that of the naturals and the reals.
       What is known: cannot be proved or disproved using standard set theory.

public class RandomSequence {

    public static void main (String[] argv)
    {
        for (int n=1; n<=10; n++) {
            System.out.println ("Un, n=" + n + ": " + computeU(n));
        }
    }

    static double computeU (int n)
    {
        return RandTool.uniform ();
    }
    
}
  

import java.util.*;

public class FunctionExample1 {

    public static void main (String[] argv)
    {
        // This is what reads from the keyboard:
        Scanner scanner = new Scanner (System.in);

        // Put out a prompt:
        System.out.print ("Enter x: ");

        // Read in a "double" (real) value:
        double x = scanner.nextDouble ();

        // Compute function:
        double f = 3*x*x + 5;

        // Print result (output):
        System.out.println (f);
    }

}

import java.util.*;

public class FunctionExample2 {

    public static void main (String[] argv)
    {
        System.out.println (" x   f(x)");         // Table header
        System.out.println ("---------");
        for (double x=1; x<=10; x=x+1) {
            double f = 3*x*x + 5;                 // Compute function.
            System.out.println (x + "  " + f);    // Print result.
        }
    }

}

import java.util.*;

public class FunctionExample3 {

    public static void main (String[] argv)
    {
        // Make a Function object and give it a name.
        Function F = new Function ("Silly function");

        for (double x=1; x<=10; x=x+1) {
            double f = 3*x*x + 5;              
            // Feed the x,f(x) combinations into the object.
            F.add (x, f);
        }

        // Write to screen.
        System.out.println (F);

        // Display.
        F.show ();
    }

}

public class FunctionComparison {

    public static void main (String[] argv)
    {
        // Make two objects, one for each function.
        Function F = new Function ("3x+5");
        Function G = new Function ("4x+5");

        // Generate 100 values in the range [0,10]
        for (double x=0; x<=10; x+=0.1) {
            F.add (x, 3*x+5);
            G.add (x, 4*x+5);
        }

        // Display both together.
        Function.show (F, G);
    }

}

public class FunctionComparison2 {

    public static void main (String[] argv)
    {
        // Initialize sum.
        double distance = 0;
        
        // Generate 50 values in the range [0,10]
        for (double x=0; x<=10; x+=0.2) {
            double f = 3*x + 5;
            double g = 3*x + 10;
            double diff = g - f;
            distance = distance + diff;
        }

        System.out.println ("Distance: " + distance);
    }

}

public class FunctionComparison3 {

    public static void main (String[] argv)
    {
        // Initialize sum.
        double sum= 0;

        // Generate 50 values in the range [0,10]
        for (double x=0; x<=10; x+=0.2) {
            double f = 3*x + 5;
            double g = 3*x + 10;
            sum += Math.abs (f - g);
        }

        // Compute the average distance:
        double distance = sum / 50;

        System.out.println ("Distance f to g: " + distance);
    }

}

public class FunctionComparison4 {

    public static void main (String[] argv)
    {
        // Initialize sum.
        double sum= 0;

        // Generate 50 values in the range [0,10]
        for (double x=0; x<=10; x+=0.2) {
            double f = 3*x + 5;
            double g = 3*x + 10;
            sum += Math.abs (f - g);
        }

        // Compute the average distance, multiplied by length of interval:
        double distance = (10-0) * sum / 50;

        System.out.println ("Distance f to g: " + distance);
    }

}

public class FunctionComparison5 {

    public static void main (String[] argv)
    {
        // Initialize sum.
        double sum= 0;

        // Compute interval = range/number-of-points:
        double interval = (10.0 - 0.0) / 50.0;

        // Generate 50 values in the range [0,10]
        for (double x=0; x<=10; x+=0.2) {
            double f = 3*x + 5;
            double g = 3*x + 10;
            sum += interval * Math.abs (f - g);
        }

        System.out.println ("Distance f to g: " + sum);
    }

}

      double interval = (10 - 0) / 50;
  

public class FunctionComparison6 {

    public static void main (String[] argv)
    {
        // Initialize sum.
        double sum= 0;

        // Compute interval = range/number-of-points:
        double interval = (10.0 - 0.0) / 50.0;

        // Generate 50 values in the range [0,10]
        for (double x=0; x<=10; x+=interval) {
            double f = 3*x + 5;
            double z = 0;
            sum += interval * Math.abs (f - z);
        }

        System.out.println ("Distance f to x-axis: " + sum);
    }

}

public class SinCos {

    public static void main (String[] argv)
    {
        // First, some sin examples;
        double s = Math.sin (0);
        System.out.println ("sin(0)=" + s);
        s = Math.sin (Math.PI/2);
        System.out.println ("sin(pi/2)=" + s);
        s = Math.sin (Math.PI/4);
        System.out.println ("sin(pi/4)=" + s);

        // Now some cos examples:
        double c = Math.cos (0);
        System.out.println ("cos(0)=" + c);
        c = Math.cos (Math.PI/2);
        System.out.println ("cos(pi/2)=" + c);
        c = Math.cos (Math.PI/4);
        System.out.println ("cos(pi/4)=" + c);
    }

}

public class SinCos2 {

    public static void main (String[] argv)
    {
        // Create two Function objects.
        Function sinFunc = new Function ("sin");
        Function cosFunc = new Function ("cos");
        
        // Put values into them.
        for (double x=0; x<=8*Math.PI; x+=0.1) {
            sinFunc.add (x, Math.sin(x));
            cosFunc.add (x, Math.cos(x));
        }
        
        // Display.
        Function.show (sinFunc, cosFunc);
    }

}