Name: coursera - Design and Analysis of Algorithms I - 1.1 Introduction : Why Study Algorithms ? (coursera - Design and Analysis of Algorithms I - 1.1 Introduction : Why Study Algorithms ?)
Uploaded: 2021-01-14T05:19:46.000Z
Duration: 18 min 35 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

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

coursera - Design and Analysis of Algorithms I - 1.1 Introduction : Why Study Algorithms ? (coursera - Design and Analysis of Algorithms I - 1.1 Introduction : Why Study Algorithms ?)