Welcome to this first course in the design and analysis of algorithms.
I imagine many of you are already clear on your reasons for taking this course,
but let me begin by justifying the course's existence.
I'm giving you several different motivations for learning about
algorithms. So, what is an algorithm?
Well, we're not going to be needing a precise definition in this course, but
essentially, an algorithm is a well-defined set of rules.
A recipe in effect for solving some kind of computational problem.
So, for example, maybe you're given a bunch of numbers and you want to
rearrange them into sorted order. Maybe you're given a road network with an
origin and a destination, and you want to compute the shortest path from point a to
point b. Maybe you're given a bunch of tasks with
deadlines and you want to know weather or not it's feasible to accomplish all of
those tasks by their respective deadlines.
So, why study algorithms? Well, first of all, understanding the
field of algorithms, and also the related field of data structures, is crucial for
doing serious work in pretty much any other branch of Computer Science.
That's the precise reason why here at Stanford University, this is the course
that's required for all of the degrees that the Computer Science Department
grants, be it a Bachelors, a Masters, or a PhD degree, we insist that you have
mastery of the field of algorithms. So, what are some examples of uses in the
rest of Computer Science? Well, if you're doing routing and
communication network, that piggybacks on classical shortest path algorithms.
the effectiveness of public key cryptography really rests on that,
of number theoretic algorithms. In, say, computer graphics, you need the
computational primitives that are supplied by the study of geometric
algorithms. Database indices rely on balance search
tree data structures, as covered in this course.
and computational biology uses dynamic programming algorithms to measure
similarity among genomes. And the list goes on and on.
A second reason to study algorithms is that they play a key role in modern
technological innovation. Obviously, I could give any number of
examples here. Let me just state one super obvious one.
which is that search engines use a tapestry of algorithms to efficiently
compute the relevance of various web pages.
The most famous search algorithm which you may have heard of is the page rank
algorithm in use by Google. Indeed,
in a December 2010 report to the United States Whitehouse, the President's
Counsel of Advisers on Science and Technology argued that in many areas,
performance gains due to improvements in algorithms, have vastly exceeded even the
dramatic performance gains due to increased processor speed, as you'd be
familiar with in the form of Moore's Law. Third, although this is getting
significantly outside the scope of this course, algorithms are increasingly being
used to provide a novel lens on processes outside of Computer Science and
Technology. For example, the set of quantum
computation has provided a new and computational viewpoint on quantum
mechanics, price fluctuations in economic markets can be fruitfully viewed as an
algorithmic process, and even evolution can be usefully thought of as, as a
surprisingly search algorithm. The last two reasons I'm going to give
you might sound a little flipping but, you know, I, I think there is more than a
grain of truth to both of them. Now, I don't know about you but back when
I was a student my favorite classes were always challenging classes but after I
struggled through them, I somehow felt I had a few more IQ points than when I
started. So, I hope this course provides a similar
experience for many of you that one the one hand it's a bit of a struggle.
You find the, the concepts challenging but perhaps you feel just a tinge smarter
after we're done. Finally, I hope that by the end of the
course, a constant fraction of you will agree with me that designing and
analyzing algorithms is simply fun. It's an endeavor that requires a rare
blend of creativity and precision and it can certainly be frustrating at times,
but even more than that, it is addictive. So, let's now descend from these lofty
generalities and get much more concrete. And also, let's remember that we've all
been learning and using algorithms since we were little kids.
So, once upon a time, in roughly third grade or so, you learned how to multiply
two numbers. Now, you probably weren't thinking in
these terms at the time, but multiplying two numbers is certainly a well-defined
computational problem and that procedure you learned back in third grade or so, is
indeed an algorithm. So, let's just make that a little bit
more precise. In this computational problem, we're
given as input, two numbers, let's say with n digits.
And to make things interesting, why don't you think about n as being really quite
large, say in the thousands? Maybe we're implementing an algorithm
that's going to be used in a cryptography application where you need to keep track
of really quite large numbers. So, if we call the two input numbers x
and y, the problem is simply to compute their product, xy.
times y. So, a quick digression.
I'll certainly be the first to admit that my handwriting is not the greatest.
I got a C in penmanship back in elementary school, and I think the
teacher was being a little generous but, you know, it's got an acquired taste, but
trust me, you will get used to it. Okay, back to integer multiplication.
Now, when we talk about procedures for multiplying two numbers, we're going to
be interested in counting how many steps are required, in order to execute the
multiplication. So, how do we count a step?
We'll talk more about this more later, but for multiplying two numbers, let's
just call a step, the addition or multiplication of two single digit
numbers. So, let's review the integer
multiplication algorithm that we learned back in grade school, just by working
through a concrete example. Specifically, let's think of n equals 4.
So, let's look at two four-digit numbers let's say, five, six, seven, eight, and
one, two, three, four. Now, as you'll recall, the procedure we
learned way back when was just to take each digit of the bottom number and
multiply it by each of the top numbers. And then to take each of those n partial
products, and add them up. So, for example, you start with the four.
You multiply it by eight, so you get 32. Carry the three.
4 times 7 is 28, add the three, you get one,
carry the three, and so on. So, that gives you this first partial
product. 22, 7, 12.
Then, you do a shift, so you effectively put a zero in this final digit, and you
repeat that procedure using the next digit, the three.
So again, three times eight is four, carry the two, and so on.
And you compute the final two partial products using the two and the one.
And having computed all of the partial products, you just add them up to get the
final product. Now, the question I'm interested in is,
how much work, how many primitive operations did we do to multiply these
two numbers. And more generally, how many does it
require to multiply two n digit numbers as a function of n.
Well, just to get sort of a ballpark view for what's going on,
we started with two n digit numbers. And at the end of the day, we basically
filled out a grid of size roughly n by n, give or take a little bit.
So, just in ballpark terms, it seems that multiplying two n digit numbers required
essentially a quadratic number of operations, a small number of operations
to fill in each entry in this grid. The grid is n by n roughly so that is
roughly n squared operations. In a little more detail, we could look at
each of the partial products separately. So, to compute, say, this first partial
product, what do we do? We take the four we multiplied it by each
of the n digits on top. We also did some carries, so that effects
things a little bit. But, in the end, we did somewhere
between, say, n and the 2n, primitive operations to compute this first partial
product. And that's true, of course, for each of
the n partial products. So, that's roughly n operations for each
of the n partial products. So, that's roughly n squared operations.
It could be all of the partial products. Then, we have to add it all up at the
end. But that takes just an extra number of
constant times n primitive operations to do all of those additions.
So summarizing, overall, the number of primitive operations required to multiply
to n digit numbers using this procedure grows quadratically with the length N.
So, for example, if you double the length of two numbers, you expect to do roughly
four times as many primitive operations if you use this iterative algorithm for
multiplying two numbers. Now, depending on what type of third
grader you were, you might well have accepted this
procedure as being the unique or at least the optimal way of multiplying two n
digit numbers together. And if you want to be an expert algorithm
designer, that kind of obedient attitude is something you're going to have to
learn to discard. Here's a favorite quote of mine.
It's from a quite early textbook in the field The Design and Analysis of Computer
Algorithms by Aho, Hopcroft, and Ullman, and after highlighting a number of
algorithmic design techniques, they conclude by saying, perhaps the most
important principle for the good algorithm designer is to refuse to be
content." So, that's a beautifully accurate quote.
I might rephrase it more succinctly by just saying, if you're, want to be a good
algorithm designer, you should adopt the following mantra.
You should always be asking, can we do better?
This is particularly appropriate question to ask when you're faced with some kind
of naive or obvious algorithm for solving a problem, like the third grade algorithm
for energy multiplication. So, this will come up over and over
again. We'll see an algorithm.
There'll be an obvious solution but with some extra algorithmic ingenuity by
detecting subtle structure in the problem,
we'll be able to do signifigantly, qualitatively better than the naive or
the obvious solution to the problem. So, let's apply this cocky attitude to
the problem of multiplying two integers. Let's just take, suppose as a working
hypothesis that there is some procedure which is better than what we learned back
in elementary school. What could it possibly look like?
So, as someone with some programming experience, you know that they are not
only iterative algorithms, iterative programs, like the one we just outlined
for multiplying two integers. But they're also recursive programs.
These are programs that call themselves, typically, on an input of a similar form,
but with smaller size. So, as a working hypothesis, let's
imagine that there's some interesting recursive approach to multiplying two
integers. What must such an algorithm look like?
Well, it must somehow fundamentally involve calling itself on smaller
problems. That is, on smaller numbers,
numbers with fewer digits. So, what kind of decomposition on numbers
could be used to enable this kind of recursive approach?
Well, if you think about it, there's a pretty natural way to break a number with
a bunch of digits into a couple numbers with fewer digits.
Namely, just take the first half of the digits, the first n over two digits,
regard that as a number in its own right. And the second half of the digits, regard
that as a number in its own right. So, perhaps this decomposition will have
some use, in enabling a recursive attack on how to multiply two images.
So, we're going to investigate that in more detail on this next slide.
Given x and y, each with n over two digits, we're going to represent x as
terms of its first half of the digits a and its second half of the digit to b.
Similarly, we will write y, the second input in terms of its first half and
second half of digits, c and d. And in this expansion, a and b, c and d
are all n over two digit numbers. I'm assuming for convenience here, that n
is even. This will extend to the case where n is
odd in the natural way, where you break it into n over two rounded up and n over
two rounded down. So, in our previous example, where x was
5,678 and y was 1,234, we would have a being equal to 56.
The first two digits of the four in x. And then b would be the other two digits.
And then similarly for c and d. They have decomposition of y.
So now, in a purely mechanical way, we can expand the product of x times y in
terms of this representation. In terms of these smaller numbers, a, b,
c, and d. So, x times y, by a representation, is just the same thing as
ten n over two times a plus b times quantity ten to the n over two c plus d.
And now, if we expand this in grouplike terms,
we get a ten to the n times ac plus ten to the n over two times ad plus bc.
So, that's combining two terms from the expansion, plus bd.
And I'm going to call this expression circled in green, star.
Now, what I want you to think about and make sure you understand is that, this
expansion that I've circled and called star, immediately suggests a recursive
algorithm for multiplying two integers. Now, it's not clear whether that
algorithm is going to be fast or slow, whether this is a good idea or a crackpot
idea. But certainly, it's a legitimate
recursive approach to multiplying two integers.
Specifically, the relevant product in star namely ac,
ad, bc, and bd all involve smaller numbers than what we stared with.
Those are all n over two digit numbers. Those all original inputs at n digits so
we can legitimately solve those recursively.
We can invoke our same algorithm to compute those in a recursive way.
Now, once we've invoked our multiplication algorithm recursively four
times to compute these four relevant products,
now we can just compute the expression in star in the obvious way.
We take ad and bc. We add them together, using the just,
standard first grade iterative addition algorithm.
Then, we add both ac and the result of that addition by a bunch of zeros,
n over 2 zeros or n zeros as appropriate. Now, we have these three constituent
terms and we just add them up again using the grade school algorithms to compute
the overall expression. So, to keep this intro lecture brisk, I
haven't discussed the base case of this recursive algorithm.
As, hopefully, you all know, recursive algorithms do need base cases.
At some point, the recursion has got to stop.
Otherwise, your algorithm is never going to terminate.
So, in multiplication, all you'd do is, if your past as input two single digit
numbers, you'd multiply them in one primitive operation, and return the
result. If the numbers have two or more digits,
you would recurse in the way we have described here.
If there's one digit, you just compute them and you're done.
So, who knows whether this recursive algorithm is a good idea or not, it's
totally not obvious, you should not even necessarily have any intuition about how
this compares to the iterative algorithm you learned back in elementary school.
So, in lieu of answering that question, although we will answer it several
lectures hence, I want to show you a second, still more
clever, recursive algorithm, for integer multiplication, so this goes by the name
of Karatsuba multiplication after the founder, although really it's sort of the
key point, there's a trick pointed out by the mathematician, Gauss, in the early
19th century. So, to explain this algorithm, let me
write once again our expansion in terms of the n over two digit numbers.
So, we have the product x times y, which we wrote as 10 to the n ac plus 10 to the
n over two ad plus bc plus bd. Now, the previous approach was in
recognition of the four products that we see in this expression.
We made four recursive calls. So, here's the trick, and this is really
what Gauss figured out over 200 years ago which is that it seems there are four
products. But fundamentally, in this expression,
there's really only three quantities that we care about.
There's the ac, the coefficient of this first term.
There's ad plus bc, the coefficient of this middle term, and there's bd.
So, we care about ad and bc as quantities individually, only in as much as we care
about their sum. We really don't care about them
individually. So, that motivates the question, perhaps
we can somehow uncover these three different quantities using only three
recursive calls rather than four. In fact, we can't, and that's Karatsuba
multiplication. So, to be more specific,
our first two recursive calls are shared with the previous recursive algorithm.
We go ahead and compute ac and bd recursively.
The third step is the, is the clever one where we recursively compute the product
of quantity a plus b with c plus d. Now, expanding what are we going to get
when we recursively compute this product, we're going to get ac plus bd plus ad
plus bc. And here is Gauss's trick for observation
which is that the result of the third recursive call minus each of the first
two, what happens? Well, the ac is going to cancel the ac,
the bd is going to cancel the bd and we will be left with ad + bc, which is
exactly that middle coefficience that we cared about.
So, we can indeed compute the sum of ad and bc without separately computing each
of them, and that's exactly what we wanted.
So, what is this bias? This gives us another second recursive
algorithm from multiplying two integers that makes use of fewer recursive calls.
Only three recursive calls rather than four.
And as before, there's a little bit of work to do beyond the recursive calls but
not much. You just have to do some padding by
zeroes and adding up the results. So, there is two points I want you to
appreciate about all these energy multiplication algorithms.
The first point is that the algorithm design space is incredibly rich.
Much richer than you might have had initially had intuition for.
Multiply two integers. What else could you do with the
elementary algorithm? Well, what have we seen?
You can do a lot of other things. In particular the second recursive
algorithm looks nothing like what we learned back in grade school.
We will see this over and over again, that with sufficient ingenuity,
sufficient cleverness you can solve problems in ways much differently and
sometimes much better than using the naive straightforward algorithm.
The second takeaway point from this discussion of integer multiplication
algorithms is that sometimes you have interesting algorithmic ideas for which
it's totally not obvious what kinds of properties or what kinds of performance
guarantees those algorithms enjoy. So, in particular, confronted with these
three different integer multiplication algorithms, how could we not wonder which
of the three is the best? Which of these three requires the fewest
number of cumulative operations to multiply two integers?
In particular, does one of these novel recursive approaches do better than the
algorithm we learned back in elementary school?
The answer to that question is totally not obvious and it requires nontrivial
mathematical analysis to answer. In the upcoming lectures, I will provide
you with the tools to not only precisely understand and answer this question but
more generally, to predict the running times of an entire genre of divide and
conquer algorithms like Karatsuba multiplication.
So, stay tuned.