Welcome to this first course in the design and analysis of algorithms. I mentioned
many of you are already clear on your reasons for taking this course, but let me
begin by justifying the course's existence and 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 whether or not it's feasible to accomplish all of those tasks by the
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 at bachelors, a masters, or 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 your doing routing in a communication network,
that piggybacks on classical shortest path algorithms. The effectiveness. The public
key photography really rests on that, of number theoretic algorithms. In safe
computer graphics, you need to [inaudible] primitives. They're supplying those study
of geometric algorithms. Data base industries rely on balance search
[inaudible] data structures as covered in this course. [inaudible] Biology using
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, and 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 webpages. The most famous such algorithm which you may have heard of is
the PageRank algorithm, in use by Google. Indeed. In a December, 2010 report to the
United States White House, the President Council of Advisors on Science and
Technology argued that, in many areas, performance gains due to improvement 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 [inaudible]
Law. Third, although this is getting significantly outside the scope of this
course, algorithms are increasingly being used to provide a novel lense on processes
outside of computer science and technology. For example, the study of
quantum computation has provided a new and computational view point 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 a
surprisingly effective search algorithm. The last two reasons I'm gonna give you
might sound a little flippant, but, I think there's 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 like 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, on the one hand,
it's a bit of a struggle, you find the, the concepts challenging, but perhaps you
feel just a, 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 multiple 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 lets just make that a little
bit more precise. In this computational problem we're given as input two numbers
lets say we have ten 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 cryptography application where you need to
keep track of really quite large numbers. So if we call the two infinite numbers X
and Y, the problem is simply to compute their products X 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 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 gonna 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 later, but for multiplying two
numbers lets 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 take of n equals four, so it's like a two four digit numbers. Let's say five,
six, seven, eight. And one, two, three, four. [sound]. Now as you'll recall, the
procedure we learned way back when was just to take each digit at 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
multiple it by eight, you get 32, carry the three. Four times seven is 28, add the
three, you get one. Carry the three, and so on. So that gives you this first
partial product. 22 seven twelve. 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 can see 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 to N digit numbers as a function of N? Well, just to get sort of a ballpark
viewpoint 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 end by end. Give and
take a little bit. So just in ballpark terms. It seems that multiplying two end
numbers require essentially a quadratic number of operations. As the small numbers
operations to fill in the entry in this grid. The grid is end by end roughly. So
that's roughly n squared operations. And a little more detail. We can look at each of
the partial product separately. So, to compute say this first partial product,
what did we do. We took the four, we multiplied it by each of the N digits on
top. We also did some carries. So that affects things a little bit. But in the
end, we did somewhere between say N and 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, give you all of the partial products. Then we have to add all
up at the end, but that takes just an extra number of cost and times n primitive
operations. Do all of those additions. So summarizing, overall, the number of
primitive operations required to multiply two end digit numbers using this procedure
grows quadratically with the length end. So, for example, if you double the length
of two numbers, you expect to, to roughly four times as many primitive operations,
if you use this itirival rhythm 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 to N digit numbers
together. And if you wanna be an expert algorithm designer, that kind of obedient
attitude is something you're gonna 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 AO Hoftcroft and Olmond. 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 want to be a good algorithm designer, you should adopt the following
mantra. You should always be asking can we do better. This is a 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. This will come up over and over again. We'll see an algorithm, there
will be an obvious solution but, with some extra algorithmic ingenuity, by detecting
subtle structure in the problem, we'll be able to do significantly qualitatively
better than the naive or obvious solution to the problem. So let's apply this cocky
attitude to the problem of multiplying two integers. Let's just 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? Well, as reasonably
seasoned programmers, you all know that there are, on the one hand, iterative
programs, liked the one we just reviewed for integer multiplication. But there's
also recursive programs. So in a recursive program, what you do is you take the
problem at hand that you're trying to solve, and you identify smaller sub
problems of it which you then solve recursively, which you then call your
function once again on. So as someone with some programming experience, you know that
there are not only iterative algorithms, iterative programs like the one we just
outlined for multiplying two integers, but there are 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? [inaudible] 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 requisite attack on how to multiply two integers. So
we're gonna 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 digits, 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 the expansion, A, B, C, and D are all entered with two digit numbers. I'm
just assuming for convenience here that N is even. This would 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 5678 and Y
was 1234 we would have A being equal to 56, the first two digits of the four and X
and D would be the other two digits and similarly for C and D in a D composition
of Y. So now on just purely mechanical way we can expand the product of X times Y in
terms of misrepresentation in terms of these smaller numbers A, B, C and D. So X
times Y by representation, is just the same thing as 10N over two times A+B times
quantity ten to the N over two, C+D. And now, if we expand this in group like
terms, we get a ten to the N times AC+ a ten to the N over two times AD+BC. So
that's combining two terms from the expansion +BD. And I am gonna 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 circled and called star immediately
suggests a recursive algorithm for multiplying two integers. Now it's not
clear whether that algorithm's going to be fast or slow or whether this is a good
idea or a crack pot idea, but certainly it's a legitimate recursive approach to
multiplying two integers, specifically. The relevant products in star, namely AC,
AD, BC, and BD all involve smaller numbers than what we started with. Those are all N
over two digit numbers, whereas our original inputs had N digits. So we can
legitimately solve those recursively. You can invoke our same algorithm to
[inaudible], to compute those in a recursive way. [sound]. 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 pad both AC and the result of that
addition by a bunch of zeroes. And over two zeroes or N zeroes as appropriate. Now
we have these three constituent terms, and we just add them up again using the grade
school algorithm 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 gotta stop. Otherwise, your algorithm is never gonna terminate. So in
multiplication, all you do is if your past is 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 described here. If there's one
digit, you just compute them, and you're done. So who knows whether this
[inaudible] 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 [inaudible]
algorithm you learned back in elementary school. So in lieu of answering that
question, although we will answer it, several lectures hence. I wanna show you a
second, still more clever recursive algorithm for integer multiplication. So
this goes by the name [inaudible] multiplication, after the founder, sort of
the key point, is a trick pointed out by the mathematician Gauss, in the early
nineteenth century. So to explain this algorithm, let me write once again our
expansion in terms of the ampertuitive numbers, so we have the product X times Y
which we wrote as. Ten to the n a, c plus ten 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 [inaudible] 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. Coefficient of this
first term, there's AD+BC, the coefficient of this middle term, and there's BD. So we
care about AD and BC as quantities individually, only inasmuch 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
carat two by multiplication. So, to be more specific. Our first to recursive
calls are shared with the previous recursive algorithm. You go ahead and
compute A, C and B, D recursively. The third step 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' trick. [inaudible]
observation, which is that the result of the third recursive call minus each of the
first two what happens. Well the AC is gonna to cancel the AC, the BD is gonna to
cancel the BD. And we will be left with AD plus BC, which is exactly that middle
co-efficient 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 does this buy us? This gives us another second recursive algorithm for
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 zeros
and adding up the results. So there's two points I want you to appreciate about all
these image and multiplication items. The first point is [inaudible] design space is
incredibly rich. Much richer than you might have initially had intuition for.
Multiplying two integers what else can you do other than the elementary school
algebra. 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. And you'll 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 kind of performance guarantees those algorithms
enjoy. [inaudible]. Particular confronted with these three different integer
multiplication algorithms how can we not wonder which of the three is the best?
Which of these requires the fewest number of [inaudible] 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 non-obvious and it requires non-trivial mathematical analysis
to answer. [inaudible] lectures 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. Algorithms like
carrot tubal multiplication. So, stay tuned.