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.
