0:00

In this video I'll talk about various aspects of the course, the topics that

Â we'll cover, the kinds of skills you can expect to acquire, the kind of background

Â that I expect, the supporting materials and the available tools for self

Â assessment. Let's start with the specific topics that this course is going to cover.

Â The course material corresponds to the first half of the ten week Stanford

Â course. It's taken by all computer science undergraduates, as well as many of our

Â graduate students. There will be five high level topics, and at times these will

Â overlap. The five topics are first of all, the vocabulary for reasoning about

Â algorithm performance, the design and conquer algorithm design paradigm,

Â randomization and algorithm design, primitives for reasoning about graphs, and

Â the use and implementation of basic data structures. The goal is to provide an

Â introduction to and basic literacy in each of these topics. Much, much more could be

Â said about each of them, than we'll have time for here. The first topic is the

Â shortest, and probably also the driest. But it's a prerequisite for thinking

Â seriously about the design and analysis of algorithms. The key concept here is big-O

Â notation, which, conceptually, is a modeling choice about the granularity with

Â which we measure a performance metric like the running time of an algorithm. It turns

Â out that the sweet spot for clear high level thinking about algorithm design, is

Â to ignore constant factors and lower-order terms. And to concentrate on how well

Â algorithm performance scales with large input sizes. Big O notation is the way to

Â mathematize this sweet spot. Now, there's no one silver bullet in algorithm design.

Â No single problem solving method that's guaranteed to unlock all of the

Â computational problems that you're likely to face. That said, there are a few

Â general algorithm design techniques. High level approaches to algorithm design that

Â find successful application across a range of different domains. These relatively

Â widely applicable techniques are the backbone of a general algorithms course

Â like this one. In this course, we'll only have time to deeply explore one such

Â algorithm design paradigm, namely that of the divide and conquer algorithms. In the

Â sequel course as we'll discuss, there's two other major algorithms on paradigms to

Â get covered. But for now, divide and conquer algorithm, the idea is to first

Â break the problem into smaller problems which then gets solved recursively, and

Â then to somehow quickly combine the solutions to the sub problems into one for

Â the original problem that you actually care about. So for example, in the last

Â video. We saw two algorithms of this sort, two divide and conquer algorithms from

Â multiplying two large integers. In later videos we will see a number of different

Â applications. We'll see how to design fast divide and conquer algorithms for problems

Â ranging from sorting to matrix multiplication to nearest neighbor-type

Â problems and computation of geometry. In addition, we'll cover some powerful

Â methods for reasoning about the running time of recursive algorithms like these.

Â 2:37

As for the third topic. A randomized algorithm is one that, in some sense,

Â flips coins while it executes. That is, a randomized algorithm will actually have

Â different executions if you run it over and over again on a fixed input. It turns

Â out, and this is definitely not intuitive, that allowing randomization internal to an

Â algorithm, often leads to simple, elegant, and practical solution to various

Â computational problems. The canonical example is randomized quick sort, and that

Â algorithm and analysis we will cover in detail in a few lectures. Randomized

Â primality testing is another killer application that we'll touch on. And we'll

Â also discuss a randomized approach to graph partitioning. And finally

Â we'll discuss how randomization is used to reason about hash functions and hash maps.

Â One of the themes of this course, and one of the concrete skills that I hope you

Â take away from the course, is, literacy with a number of computational primitives

Â for operating on data, that are so fast, that they're, in some sense, essentially

Â free. That is, the amount of time it take to invoke one of these computational

Â primitives is barely more than the amount of time you're already spending just

Â examining or reading the input. When you have a primitive which is so fast, that

Â the running time is barely more than what it takes to read the input, you should be

Â ready to apply it. For example, in a preprocessing step, whenever it seems like

Â it might be helpful. It should just be there on the shelf waiting to be applied

Â at will. Sorting is one canonical example of a very fast, almost for-free

Â primitive of this form. But there are ones that operate on more complex data as well.

Â So recall that a graph is a data structure that has, on the one hand, vertices, and

Â on the other hand, edges. Which connects pair of vertices. Graphs model, among any

Â other things, different types of networks. So even though graphs are much more

Â complicated than mere arrays, there's still a number of blazingly fast primitives

Â for reasoning about their structure. In this class we'll focus on primitives for

Â competing connectivity information and also shortest paths. We'll also touch on how some primitives have been

Â used to investigate the structure of information in social networks. Finally,

Â data structures are often a crucial ingredient in the design of fast

Â algorithms. A data structure's responsible for organizing data in a way that supports

Â fast queries. Different data structures support different types of queries. I'll

Â assume that you're familiar with the structures that you typically encounter in

Â a basic programming class including arrays and vectors. Lists, stacks, and queues.

Â Hopefully, you've seen at some point both trees and heaps, or you're willing to read

Â a bit about them outside of the course, but we'll also include a brief review of

Â each of those data structures as we go along. There's two extremely useful data

Â structures that we'll discuss in detail. The first is balanced binary search trees.

Â These data structures dynamically maintain an ordering on a set of elements, while

Â supporting a large number of queries that run in time logarithmic in the size of

Â the set. The second data structure we'll talk a fair bit about is hash tables or

Â hash maps, which keep track of a dynamic set, while supporting extremely fast

Â insert and lookup queries. We'll talk about some canonical uses of such data

Â structures, as well as what's going on under the hood in a typical

Â implementation of such a data structure. >> There's a number of

Â important concepts in the design and analysis of algorithms that we won't have

Â time to cover in this five week course. Some of these will be covered in the

Â sequel course, Design and Analysis of Algorithms II, which corresponds to the

Â second half of Stanford's ten week course on this topic. The first part of this

Â sequel course focuses on two more algorithm design paradigms. First of

Â all, the design analysis of greedy algorithms with applications to minimum

Â spanning trees, scheduling, and information theoretic coding. And

Â secondly, the design analysis of dynamic programming algorithms with example

Â applications being in genome sequence alignment and the shortest path protocols

Â in communication networks. The second part of the sequel course concerns NP complete

Â problems, and what to do about them. Now, NP complete problems are problems that,

Â assuming a famous mathematical conjecture you might have heard of, which is called the

Â "P not equal to NP" conjecture, are problems that cannot be solved under this

Â conjecture by any computationally efficient algorithm. We'll discuss the

Â theory of NP completeness, and, with a focus on what it means for you as an

Â algorithm designer. We'll also talk about several ways to approach NP complete

Â problems, including: fast algorithms that correctly solve special cases; fast

Â heuristics with provable performance guarantees; and exponential time

Â algorithms that are qualitatively faster than brute force search. Of course there

Â are plenty of important topics that can't be fit into either of these two five-week

Â courses. Depending on the demand, there might well be further courses on more

Â advanced topics. Following this course is going to involve a fair amount of time and

Â effort on your part. So it's only reasonable to ask: What can you hope to get

Â out of it? What skills will you learn? Well. Primarily, you know, even though

Â this isn't a programming class per se, it should make you a better programmer.

Â You'll get lots of practice describing and reasoning about algorithms, you'll learn

Â algorithm design paradigms, so really high level problem-solving strategies that are

Â relevant for many different problems across different domains, and tools for

Â predicting the performance of such algorithms. You'll learn several extremely

Â fast subroutines for processing data and several useful data structures for

Â organizing data that can be deployed directly in your own programs. Second,

Â while this is not a math class per se, we'll wind up doing a fair amount of

Â mathematical analysis. And this in turn will sharpen your mathematical analytical

Â skills. You might ask, why is mathematics relevant for a class in the design and

Â analysis of algorithms, seemingly more of a programming class. Well let me be clear.

Â I am totally uninterested in merely telling you facts or regurgitating code

Â that you can already find on the web or in any number of good programming books. My

Â goal here in this class, and the way I think I can best supplement the resources

Â that you probably already have access to is to explain why things are

Â the way they are. Why we analyze the algorithms in the way that we do, why

Â various super fast algorithms are in fact super fast, and so on. And it turns out

Â that good algorithmic ideas usually require nontrivial mathematical analysis

Â to understand properly. You'll acquire fundamental insights into the specific

Â algorithms and data structures that we discuss in the course. And hopefully, many

Â of these insights will prove useful, more generally, in your other work. Third, and

Â perhaps the most relevant for those of you who work in some other discipline: this

Â course should help you learn how to think algorithmically. Indeed after studying

Â algorithms it's hard enough not to see them pretty much everywhere, whether you

Â are riding an elevator, watching a flock of birds, buying and selling stocks out of

Â your portfolio, even watching an infant learn. As I said in the previous video

Â algorithm thinking is becoming increasingly useful and prevalent if you

Â are outside of computer science and technology like in biology, statistics and

Â economics. Fourth, if you're interested in feeling like a card carrying computer

Â scientist, in some sense, then you'll definitely want basic literacy in all of

Â the topics that we'll be covering. Indeed, one of the things that makes studying

Â algorithms so fun, is, it really feels like you're studying a lot of the greatest

Â hits from the last 50 years of computer science. So, after this class, no longer

Â will you feel excluded at that computer science cocktail party when someone cracks

Â a joke about Dijkstra's Algorithm. Now you'll know exactly what they mean.

Â Finally, there's no question that studying this material is helpful for technical

Â interview questions. To be clear, my sole goal here is to teach you algorithms, not

Â to prepare you for interviews, per se. But over the years, countless students of mine

Â have regaled me with stories about how mastering the concepts in this class

Â enabled them to ace every technical question they were ever asked. I told you,

Â this is fundamental stuff. So, what do I expect from you? Well, honestly, the

Â answer is nothing. After all isn't the whole point of a free online class like

Â this one that anyone can take it and devote as much effort to it as they like.

Â So that said, as a teacher it's still useful to have one or more canonical

Â students in mind. And I thought I'd go ahead and be transparent with you about

Â how I'm thinking about these lectures. Who I have in mind that I'm teaching to. So

Â again, please don't feel discouraged if you don't conform to this canonical

Â student template. I'm happy to have the opportunity to teach you about algorithms

Â no matter who you are. So first, I have in mind someone who knows at least some

Â programming. For example, consider the previous lecture. We talked about a

Â recursive approach to multiplying two numbers and I mentioned how in certain

Â mathematical expression, back then we labeled it star and circled it in green.

Â How that expression naturally translated into a recursive algorithm. In particular,

Â I was certainly assuming that you had some familiarity with recursive programs.

Â If you feel comfortable with my statement in that lecture, if you feel like you

Â could code up a recursive integer multiplication algorithm based on the high

Â level outline that I gave you, then you should be in good shape for this course.

Â You should be good to go. If you weren't comfortable with that statement, well, you

Â might not be comfortable with the relatively high conceptual level at which

Â we discuss program in this course. But I encourage to watch the next several videos

Â anyway, to see if you get enough out of them to make it worth your while. [sound].

Â 11:24

Now, while I'm aiming these lectures at people who know some programming, I'm not

Â making any assumptions whatsoever about exactly which programming languages you know. Any

Â standard imperative language you know, something like C, Java or Python, is

Â totally fine for this course. Now, to make these lectures accessible to as many

Â programmers as possible, and to be honest, you know, also to promote thinking about

Â programming at a relatively abstract conceptual level, I won't be describing

Â algorithms in any particular programming language. Rather, when I discuss the

Â algorithms, I'll use only high-level pseudo-code, or often simply English. My

Â inductive hypothesis is that you are capable of translating such a high level

Â description into a working program in your favorite programming language. In fact, I

Â strongly encourage everyone watching these lectures to do such a translation of all

Â of the algorithms that we discussed. This will ensure your comprehension, and

Â appreciation of them. Indeed, many professional computer scientists and

Â programmers don't feel that they really understand an algorithm until they've

Â coded it up. Many of the course's assignments will have a problem in which

Â we ask you to do precisely this. Put another way, if you're looking for a sort

Â of coding cookbook, code that you can copy and paste directly into your own programs.

Â Without necessarily understanding how it works, then this is definitely not the

Â course for you. There are several books out there that cater to programmers

Â looking for such coding cook books. Second, for these lectures I have in mind

Â someone who has at least a modest amount of mathematical experience though perhaps

Â with a fair bit of accumulated rust. Concretely I expect you to be able to

Â recognize a logical argument that is a proof. In addition, two methods of proof

Â that I hope you've seen before are proofs by induction and proofs by contradiction.

Â I also need you to be familiar with basic mathematical notation, like the standard

Â quantifier and summation symbols. A few of the lectures on randomized algorithms

Â and hashing will go down much easier for you if you've seen discrete probability

Â at some point in your life. But beyond these basics, the lectures will be self

Â contained. You don't even need to know any calculus, save for a single simple

Â integral that magically pops up in the analys of the randomized quick sort

Â algorithm. I imagine that many of you have studied math in the past, but you could

Â use a refresher, you're a bit rusty. And there's plenty of free resources out there

Â on the web, and I encourage you to explore and find some that you like. But one that

Â I want to particularly recommend is a great set of free lecture notes. It's

Â called Mathematics for Computer Science. It's authored by Eric Lehman and Tom

Â Layden, and it's quite easy to find on the web if you just do a web search. And those

Â notes cover all of the prerequisites that we'll need, in addition to tons of other

Â stuff. In the spirit of keeping this course as widely accessible as possible,

Â we're keeping the required supporting materials to an absolute minimum. Lectures

Â are meant to be self-contained and we'll always provide you with the lecture notes

Â in PowerPoint and PDF format. Once in a while, we'll also provide some additional

Â lecture notes. No textbook is required for this class. But that said, most of the

Â material that we'll study is well covered in a number of excellent algorithms books

Â that are out there. So I'll single out four such books here. The first three I

Â mention because they all had a significant influence on the way that I both think

Â about and teach algorithms. So it's natural to acknowledge that debt here. One

Â very cool thing about the second book, the one by Dasgupta, Papadimitriou and Vazirani, is that the authors

Â have made a version of it available online for free. And again, if you search on the

Â authors' names and the textbook title, you should have no trouble coming up with it

Â with a web search. Similarly, that's the reason I've listed the fourth book because

Â those authors have likewise made essentially a complete version of that

Â book available online and it's a good match for the material that we're going to

Â cover here. If you're looking for more details about something covered in this

Â class, or simply a different explanation than the one that I give you, all of these

Â books are gonna be good resources for you. There are also a number of excellent

Â algorithm textbooks that I haven't put on this list. I encourage to explore

Â and find you own favorite. >> In our assignments, we'll sometimes ask you to

Â code up an algorithm and use it to solve a concrete problem that is too large to

Â solve by hand. Now, we don't care what program and language and development

Â environment you use to do this as we're only going to be asking you for the final

Â answer. Thus, we're not requiring anything specific, just that you are able to write

Â and execute programs. If you need help or advice about how to get set up with a

Â suitable coding environment, we suggest that you ask other students for help via

Â the course discussion forum. Finally, let's talk a bit more about assessment.

Â Now this course doesn't have official grades per se, but we will be assigning

Â weekly homeworks. Now we're going to assign homeworks for three different

Â reasons. The first is just for self-assessment. It's to give you the

Â opportunity to test your understanding of the material so that you can figure out

Â which topics you've mastered and which ones that you haven't. The second reason

Â we do it is to impose some structure on the course, including deadlines, to

Â provide you with some additional motivation to work through all the topics.

Â Deadlines also have a very important side effect that synchronizes a lot of the

Â students in the class. And this of course makes the course discussion forum a far

Â more effective tool for students to seek and provide help in understanding the

Â course material. The final reason that we give homeworks is to satisfy those of you

Â who, on top of learning the course material, are looking to challenge

Â yourself intellectually. [sound]. Now, this class has tens of thousands of

Â students. So it's obviously essential that the assignments can be graded

Â automatically. Now, we're currently only in the 1.0 generation of free online

Â courses such as this one. So the available tools for auto graded assessment are

Â currently rather primitive. So, we'll do the best we can, but I have to be honest

Â with you. It's difficult, or maybe even impossible to test deep understanding of

Â the design and analysis of algorithms, using the current set of tools. Thus,

Â while the lecture content in this online course is in no way watered down from the

Â original Stanford version. The required assignments and exams we'll give you, are

Â not as demanding as those that are given in the on campus version of the course. To

Â make up for this fact, we'll occasionally propose optional algorithm design

Â problems, either in a video or via supplementary assignment. We don't have

Â the ability to grade these, but we hope that you'll find them interesting and

Â challenging, and that you'll discuss possible solutions with other students via

Â the course discussion forum. So I hope this discussion answered most of the

Â questions you have about the course. Lets move on to the real reason that we're all

Â here, to learn more about algorithms.

Â