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