Algorithms
What are algorithms?
A finite set of steps for performing a computation.
Finite in the sense of both the description and in that eventually the algorithm terminates. So not all programs are algorithms.
We typically use “algorithm” to describe parts of a program that have a particularly well-defined purpose.
Some important kinds of algorithms
-
Searching
-
Sorting
These are the two kinds the College Board wants you to know about.
What are some other things computers do?
Let’s find the algorithms.
“The Algorithm”
These days we also often talk about “The Algorithm” to describe things like how TikTok decides what videos you’re most likely to watch.
Those are indeed algorithms but they are hugely complex and made up of many, many little-“a” algorithms.
Analyzing algorithms
We can talk about algorithms independently of how they are expressed in code.
Actual code “implements” an algorithm.
But there are characteristics of an algorithm that all implementations of that algorithm will share.
Algorithms differ
Also there can be different algorithms for achieving the same ends.
So we sometimes need to analyze algorithms to see how they compare.
What we care about
-
Correctness
-
Time: how long does it take?
-
Space: how much memory does it need?
Searching, part 1
What is an algorithm to determine on what page, if any, the word “trellis” occurs in this book?
Searching, part 2
How about in this book?
What’s the difference?
Suppose I gave you a novel that was twice as long as Great Expectations, how much longer do you think it would take to find a random word in it?
Now suppose I gave you an unabridged dictionary that was twice as big as the original dictionary—how much longer would that take?
How we talk about time
Since algorithms aren’t tied to a particular implementation it’s not that useful to talk about how long they take in terms of actual time.
Instead we talk about how their runtime grows as the size of the problem grows.
Finding a word in a bigger book is a bigger problem than finding it in a smaller book. If the book doubles, what does that do to how long the algorithm takes?
