Algorithms

In the first lecture, we said that CS is “the study of algorithms, including…”.
- Mostly, we'll leave algorithms themselves to other courses.
- But we need to discuss some basic mathematical ideas behind analysis of algorithms here.
- So we can't ignore them entirely.
An algorithm is…
- … a finite set of precise instructions for performing a computation or for solving a problem. [from our text]
- … a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time. [Levitin, Introduction to The Design & Analysis of Algorithms]
- … an effective method expressed as a finite list of well-defined instructions for calculating a function. [Wikipedia “Algorithms”]
Common ideas in those definitions:
- precise/unambiguous/well-defined: There can be no question about what it means.
- performing a computation/solving a problem/calculating a function: It has a job to do.
- solving/required output/effective: It should do the job correctly.
- finite/finite amount of time/finite list: It can't go on forever (either in definition or before finishing the calculation).
The requirement for for precision means we need some formal way to describe an algorithm.
- We usually use a programming language for that (assuming a programming language is actually defined precisely enough).
- … but we aren't programming in this course.
- This is really a problem for a programming language semantics course.
- … so is the correctness question.
We will use pseudocode to describe algorithms.
- We will write something like a well-structured programming language, but with less restrictions imposed by the language.
- We will write procedural pseudocode: describe the steps the computer should follow to do the required computation.
There are perfectly good ways to describe an algorithm that aren't procedural.
- For more about non-procedural/imperative programming, take a comparative programming languages course.
- CMPT 383 at SFU is an excellent choice, especially when I'm teaching it.
Other options to describe an algorithm: a well-defined programming language, flowcharts, Turing machines, lambda calculus,…

Pseudocode

Here is an example of some pseudocode of a procedure to find the smallest of three values:

procedure find_smallest(a, b, c)
    if a < b and a < c
        result = a
    elseif b < c
        result = b
    else
        result = c

Here's another example:

procedure do_something(list)
    for i from 0 to length(list)-2
        small = list[i]
        smallpos = i
        for each j from i+1 to length(list)-1
            if list[j] < small then
                small = list[j]
                smallpos = j
        swap list[i] and list[smallpos]

We won't worry about a strict definition of what is and isn't pseudocode.
- As long as it's unambiguous to us, it's good enough.

Halting Problem

When defining “algorithm”, we thought it would be nice if the algorithm finished (halts) in a finite amount of time.
- One of the definitions demanded it.

Can we tell if a particular algorithm halts when given specific input?

Sometimes, definitely yes:

procedure halt_quickly()
    print "Hello world"

Sometimes, definitely no:

procedure loop_forever()
    while true
        print "Hello world"

Sometimes, it's hard to say:

procedure collatz(n)
    while n != 1
        if n is even
            n = n/2
        else
            n = 3n+1

Can an algorithm decide for us?
- Unfortunately, no.
- Theorem: There does not exist an algorithm \(H(P,I)\) that can determine if procedure \(P\) halts when given input \(I\).
  
  Proof: Suppose for contradiction that there is a \(H(P,I)\) that can correctly return true iff computing \(P(I)\) halts.
  
  Define this algorithm, which takes another procedure as input:
```
procedure C(P)
    if H(P,P)
        loop_forever()
    else
        halt_quickly()
```
  Now, does \(C(C)\) halt? If it does, then \(H(C,C)\) should return true. But then the condition in the definition of \(C\) is be false, and it will actually loop forever. Similarly, if \(C(C)\) doesn't halt, then we find from the definition that it must.
  
  Since we have reached a contradiction, no such \(H\) can exist.∎
Implication: coding tools can never be as good as you'd like.
- It would be nice if your IDE would look at a function you're writing and warn you that it's going to enter an infinite loop.
- But that would require solving the halting problem, which we just proved was impossible.
Can we patch up the halting problem and solve it for algorithms that don't take other algorithms as input? (or some other restriction that would leave us with something useful?)
- Still no.
- Rice's Theorem says (basically) that any question about algorithms is either trivial (always say yes, or always say no), or uncomputable.
The implication of that is that you can't really compute anything about a program.
- Will this code ever call this function? Uncomputable.
- Will this program need access to the printer/network/disk? Uncomputable.
- Will this program give me a virus? Uncomputable.
- Any program that claims to answer those questions is wrong (at least some of the time).
- That doesn't mean you can't write a virus checker that's kind of useful, only that it must be wrong some of the time.

Algorithm Running Time: a start

When looking at algorithms, one of the most important questions is how long it will take them to finish.
- Obviously, a fast algorithm is better than a slow one.
- There may even be times that a fast algorithm that gives approximately-correct answers is preferred over a slow but perfect one.
There are a lot of factors involved in how long it takes for a program to run: processor speed, compiler optimizations, cleverness of the implementation,….
- We want to think about algorithms without worrying about those things.
We will basically be counting the number of “steps” an algorithm requires to complete.
- But even there, we have a problem of too much detail making it hard to reason about how fast an algorithm is.
- How many steps do these algorithms take? They look different, but are fundamentally the same.
```
procedure one(a,b,c)
    result = a+b+c
procedure two(a,b,c)
    x = a+b
    result = x+c
procedure three(a,b,c)
    x = a
    y = x+b
    result = y+c
```
- An optimizing compiler would hopefully turn those into the same machine code anyway.
We need a way to quantify the number of “steps” with those details washed away too.
Also remember that the number of steps is going to be a function of the input.
- It takes longer to sort a million items than five.
- The real question is: how does the running time change as the input grows?
- Also, how does that compare to another algorithm for the same problem?
So we need a function (to express the number of steps an algorithm takes for a particular input) and some way to express how that grows as the input grows…