# 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:
• Here's another example:
• 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:
• Sometimes, definitely no:
• Sometimes, it's hard to say:
• 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:

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 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.
• 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…