Hi, my name's Tim Roughgarden. I'm a professor here at Stanford
University. And I'd like to welcome you to this first
course on the Design and Analysis of Algorithms.
Now, I imagine many of you are already clear on your reasons for taking this
course. But let me begin by justifying this
course's existence. And giving you some reasons why you
should be highly motivated to learn about algorithms.
So what is an algorithm anyways? Basically it's a set of well defined
rules, a recipe in effect for solving some computational problem.
Maybe you have a bunch of numbers and you want to rearrange them so that they're in
sorted order. Maybe you have a roadmap and an origin
and a destination And you want to compute the shortest path from that origin to
that destination. May be you face a number of different
tasks that need to be completed by certain deadlines and you ant to know in
what order you should accomplish the task.
So that you complete them all by their respective deadlines.
So why study algorithms? Well first of all, understanding the
basics of algorithms and the related field of data structures is essential for
doing serious work in pretty much any branch of computer science.
This is the reason why here at Stanford, this course is required for every single
degree that the department offers. The bachelors degree the masters degree
and also the PHD. To give you a few examples routing and
communication networks piggybacks on classical shortest path algorithms.
The effectiveness of public key cryptography relies on that of
number-theoretic algorithms. Computer graphics needs the computational
primitives supplied by geometric algorithms.
Database indices rely on balanced search tree data structures.
Computational biology uses dynamic programming algorithms to measure genome
similarity. And the list goes on.
Second, algorithms play a key role in modern technological innovation.
To give just one obvious example, search engines use a tapestry of algorithms to
efficiently compute the relevance of various webpages to it's given search
query. The most famous such algorithm is the
page rank algorithm currently in use by Google.
Indeed in a December 2010 report to the United States White House, 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 event he dramatic performance gains due to increased processor speeds.
Third, although this is outside of the score, 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 study of quantum
computation has provided a new Computational viewpoint on quantum
mechanics. Price fluctuations in economic markets
can be fruitfully viewed as an algorthmic process and even evolution can be
usefully thought of as a surprisingly effect search algorthim.
The last two reasons for studying algorthims might sound flippant but both
have more than a grain of truth to them. I don't know about you, but back when I
was a student, my favorite classes were always the challenging ones that, after I
struggled through them, left me feeling a few IQ points smarter than when I
started. I hope this course provides a similar
experience for many of you. Finally, I hope that by the end of the
course I'll have converted some of you to agree with me that the design and
analysis of algorithms is simply fun. It's an endeavor that requires a rare
blend of precision and creativity. It can certainly be frustrating at times,
but it's also highly addictive. So let's descend from these lofty
generalities and get much more concrete. And let's remember that we've all been
learning about and using algorithims since we were little kids.