Overview

Our goal is to be able to:

1. Analyze algorithms in terms of correctness and time/space complexity, and
2. Design algorithms efficiently.

Algorithms

Algorithm: Sequence of unambiguous instructions¹1. Meaning each step is clearly defined and leaves no room for subjective interpretation. for solving a problem in a finite amount of time²2. An algorithm must eventually terminate. If it runs forever, it is a process, not an algorithm..

Design & Analysis

The Process

1. Understand the problem
2. Decide on computational means³3. e.g., will the solution be exact or approximate?
3. Design an algorithm
4. Prove correctness
5. Analyze the algorithm
6. Code the algorithm

Techniques & Strategies

• Brute Force
• Divide and Conquer
• Decrease and Conquer
• Transform and Conquer
• Space and Time Tradeoffs
• Greedy Approach
• Dynamic Programming
• Iterative Improvement
• Backtracking
• Branch and Bound

Note — We’ll be going through these in this course.

Important Problem Types

• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial
• Geometric
• Numerical

Note — We’ll be doing lots of graph problems.

Analysis of Algorithms

1. How good is it?
   • Time efficiency
   • Space efficiency
2. Does a better one exist?
   • Lower bounds
   • Optimality
3. Other characteristics
   • Simplicity
   • Generality

And now, some introductory problems.

While following along, note how:

• Our definitions for algorithms must be unambiguous.
• You can describe an algorithm in many ways.
• You can solve a problem in many ways.
  • But some ways are faster than others.

Problem: Greatest Common Divisor

Problem: Find gcd(m,n), the greatest common divisor of two nonnegative, nonzero integers m and n.

Suppose gcd(60,24). We can figure out the GCD is 12 in our heads, but what about an algorithm to get there?

Approach 1: Consecutive Integer Checking

A naive brute-force approach where we let t = \min(m,n), and then:

1. Divide m by t, go to step 2 if remainder if 0.
2. Divide n by t, return t and stop if remainder is 0. Otherwise, go to step 3.
3. Decrease t by 1 and go to Step 2.

Approach 2: Euclid’s Algorithm

Euclid’s Algorithm is an efficient solution that is based on the repeated application of the equality:

\gcd(m,n) = \gcd(n, m \bmod n)

Aside — Why this equality is true is irrelevant to us, just take it as a given.

Describing the Algorithm in English:

Apply the above equality repeatedly until the second parameter becomes zero. At this point the problem becomes trivial to solve⁴4. Because \gcd(x,0) = x..

Describing the Algorithm in Steps:

1. If n=0, return m and stop; otherwise go to Step 2.
2. Divide m by n and assign the remainder to r
3. Assign the value of n to m and the value of r to n. Go to Step 1.

Describing the Algorithm in Pseudocode:

// GCD via Euclid's Algoritm
// Input: Two nonnegative, nonzero integers m and n
// Output: The greatest common divisor of m and n
while n \ne 0 do
    r \leftarrow m \% n
    m \leftarrow n
    n \leftarrow r
return m

Analysis — Time complexity is O(\log(\min(m, n))). Space complexity is O(1).

Aside — Professor’s Recommendation: It’s better to write pseudocode last.

Problem: Finding Primes

Note — For this problem, we’re just going to skip ahead to the interesting solution.

Problem: How can you find all prime numbers (up to some given n) with an algorithm?

Key Property: It’s easier to tell if a number isn’t prime⁵5. A composite number must have a prime factor less than or equal to its square root.

• Example: Half of all numbers are divisible by 2, a third of all numbers are divisible by 3, et cetera.
• This property is exactly what the next algorithm uses.

Approach: Sieve of Eratosthenes

This algorithm finds all prime numbers less than or equal to a given interger n.

Describing the Algorithm in Steps:

1. Create a list of consecutive integers from 2 through n.
2. Initialize p=2 (the first prime number).
3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (2p, 3p, 4p, etc.);
4. Find the first number greater than p in the list that is not marked. If there’s no such number, stop. Otherwise, let p equal this new number (the next prime) and repeat from Step 3.

Describing the Algorithm in Pseudocode:

// Sieve of Eratosthenes
// Input: Integer n >= 2
// Output: List of primes that are <= n

// Generate list
for p \leftarrow 2 to n do A[p] \leftarrow p

// The sieve part
for p \leftarrow 2 to \lfloor\sqrt{n}\rfloor do
    // if p hasn't been eliminated...
    if A[p] \ne 0
        // ... derive all non-primes ...
        j \leftarrow p \large{*} p
        while j \le n do
            // ... and eliminate them 
            A[j] \leftarrow 0
            j \leftarrow j \text{$+$} p

Analysis — Time complexity is O(n \log \log n). Space complexity is O(n) to store the array.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2 3   5   7   9    11    13    15    17    19

2 3   5   7        11    13          17    19