1 00:00:00,000 --> 00:00:02,885 In this video I'll talk about various aspects of the course. 2 00:00:02,885 --> 00:00:06,058 The topics that we'll cover. The kinds of skills you can expect to 3 00:00:06,058 --> 00:00:08,222 acquire. The kind of background that I expect. 4 00:00:08,222 --> 00:00:11,540 The supporting materials, and the available tools for self assessment. 5 00:00:13,960 --> 00:00:17,445 Let's start with specific topics that this course is going to cover. 6 00:00:17,445 --> 00:00:21,545 The course material corresponds to the first half of a ten week Stanford course. 7 00:00:21,545 --> 00:00:25,286 It's taken by all computer science undergraduates, as well as many of our 8 00:00:25,286 --> 00:00:28,310 graduate students. There will be five high level topics and 9 00:00:28,310 --> 00:00:31,641 at times these will overlap. The five topics are, first of all, the 10 00:00:31,641 --> 00:00:35,537 vocabulary for reasoning about algorithm performance, the design and conquer 11 00:00:35,537 --> 00:00:39,432 algorithm design paradigm, randomization and algorithm design, primitives for 12 00:00:39,432 --> 00:00:43,481 reasoning about graphs, and the use and implementation of basic data structures. 13 00:00:43,481 --> 00:00:47,581 The goal is to provide an introduction to, and a basic literacy in each of these 14 00:00:47,581 --> 00:00:49,991 topics. Much, much more could be said about each 15 00:00:49,991 --> 00:00:54,332 of them then we'll have time for here. The first topic is the shortest, and 16 00:00:54,332 --> 00:00:58,431 probably also the driest, but it's a prerequisite for thinking seriously about 17 00:00:58,431 --> 00:01:02,531 the design and analysis of algorithms. The key concept here is Begona notation, 18 00:01:02,531 --> 00:01:06,526 which is conceptually is a modeling choice about the granularity with which 19 00:01:06,526 --> 00:01:10,205 we measure a performance metric, like the running time of an algorithm. 20 00:01:10,205 --> 00:01:13,832 It turns out that the sweet spot for clear, high level thinking about 21 00:01:13,832 --> 00:01:17,669 algorithm design, is to ignore constant factors in low order terms and to 22 00:01:17,669 --> 00:01:21,348 concentrate on how well algorithm performance scales, with large input 23 00:01:21,348 --> 00:01:23,871 sizes. Begona notation is a way to mathematicize 24 00:01:23,871 --> 00:01:27,320 the sweet spot. Now, there's no one silver bullet in 25 00:01:27,320 --> 00:01:30,792 algorithm design, no single problem solving method that's guaranteed to 26 00:01:30,792 --> 00:01:34,118 unlock all of the computational problems that you're likely to face. 27 00:01:34,118 --> 00:01:37,688 That said, there are a few general algorithm design techniques, high level 28 00:01:37,688 --> 00:01:41,698 approaches to algorithm design that find successful application across a range of 29 00:01:41,698 --> 00:01:44,290 different domains. These relatively widely applicable 30 00:01:44,290 --> 00:01:47,860 techniques are the backbone of a general algorithms course like this one. 31 00:01:47,860 --> 00:01:51,728 In this course, we'll only have time to deeply explore one such algorithm design 32 00:01:51,728 --> 00:01:53,807 paradigm. Namely, that of divide and conquer 33 00:01:53,807 --> 00:01:56,177 algorithms. In the sequel course, as we'll discuss, 34 00:01:56,177 --> 00:01:59,465 there's two other major algorithm design paradigms that get covered. 35 00:01:59,465 --> 00:02:01,447 But for now, divide and conquer algorithm. 36 00:02:01,447 --> 00:02:05,364 The idea is to first break the problem into smaller sub-problems which then gets 37 00:02:05,364 --> 00:02:08,217 solved recursively. And then to somehow quickly combine the 38 00:02:08,217 --> 00:02:11,553 solutions to the sub-problems. Into one for the original problem that 39 00:02:11,553 --> 00:02:14,310 you actually care about. So for example, in the last video. 40 00:02:14,310 --> 00:02:17,778 We saw two algorithms of this sort two divide and conquer algorithms for 41 00:02:17,778 --> 00:02:21,152 multiplying two large integers. In later videos we will see a number of 42 00:02:21,152 --> 00:02:25,143 different applications we will see how to design fast divide and conquer algorithms 43 00:02:25,143 --> 00:02:28,897 for problems ranging from sorting to matrix multiplication to nearest neighbor 44 00:02:28,897 --> 00:02:32,698 type problems in computational geometry. In addition we will cover some powerful 45 00:02:32,698 --> 00:02:36,500 methods for reasoning about the running time of recursive algorithms like these. 46 00:02:36,500 --> 00:02:39,962 . As for the third topic a randomized 47 00:02:39,962 --> 00:02:43,633 algorithm is one that in some sense flips coins while it executes. 48 00:02:43,633 --> 00:02:47,972 That is a randomized algorithm will actually have different executions if you 49 00:02:47,972 --> 00:02:50,420 run it over and over again on a fixed input. 50 00:02:50,420 --> 00:02:54,759 It turns out and this is definitely not intuitive, that allowing randomization 51 00:02:54,759 --> 00:02:57,956 internal to an algorithm. Often leads to simple, elegant and 52 00:02:57,956 --> 00:03:00,826 practical solutions to various computational problems. 53 00:03:00,826 --> 00:03:05,183 The canonical example is randomize quick sort and that algorithm analysis we will 54 00:03:05,183 --> 00:03:08,956 cover detail in a few lectures. Randomized primality testing is another 55 00:03:08,956 --> 00:03:13,048 killer application that we'll touch on, and we will also discuss a randomized 56 00:03:13,048 --> 00:03:16,927 approach to graph partitioning. Finally we will discuss how randomization 57 00:03:16,927 --> 00:03:20,960 is used to reason about hash functions. Hash mats. 58 00:03:20,960 --> 00:03:24,527 One of the themes of this course. And one of the concrete skills that I 59 00:03:24,527 --> 00:03:27,742 hope you take away from the course. Is literacy with a number of 60 00:03:27,742 --> 00:03:31,761 computational primitives for operating on data that are so fast that they're, in 61 00:03:31,761 --> 00:03:35,127 some sense, essentially free. That is, the amount of time it takes to 62 00:03:35,127 --> 00:03:38,945 invoke one of these computational primitives is barely more than the amount 63 00:03:38,945 --> 00:03:42,362 of time you're already spending just examining or reading the input. 64 00:03:42,362 --> 00:03:46,180 When you have a primitive which is so fast that the running, running time is 65 00:03:46,180 --> 00:03:48,642 barely more than what it takes to read the input. 66 00:03:48,642 --> 00:03:52,269 You should be ready to apply it. For example, in a pre-processing step, 67 00:03:52,269 --> 00:03:54,617 whenever it seems like it might be helpful. 68 00:03:54,617 --> 00:03:58,274 It should just be there on the shelf waiting to be applied at will. 69 00:03:58,274 --> 00:04:02,478 Sorting is one canonical example of a very fast, almost [INAUDIBLE] primitive 70 00:04:02,478 --> 00:04:05,371 of this form. But, there are ones that operate on more 71 00:04:05,371 --> 00:04:08,319 complex data as well. So recall that a graph of a data 72 00:04:08,319 --> 00:04:12,250 structure that has on the one hand vertices, and on the other hand edges. 73 00:04:12,250 --> 00:04:15,605 Which connect pairs of vertices. Graphs model among many other things 74 00:04:15,605 --> 00:04:19,301 different types of networks, so even though graphs are much more complicated 75 00:04:19,301 --> 00:04:22,948 than mere arrays, there are still a number of blazingly fast primitives for 76 00:04:22,948 --> 00:04:26,449 reasoning about their structure. In this class we'll focus on primitives 77 00:04:26,449 --> 00:04:29,513 for computing conductivity information and also shortest paths. 78 00:04:29,513 --> 00:04:33,111 We'll also focus on how such primitives have been used to investigate the 79 00:04:33,111 --> 00:04:35,880 structure of information and social networks. 80 00:04:35,880 --> 00:04:39,856 Finally, data structures are often a crucial ingredient in the design of fast 81 00:04:39,856 --> 00:04:42,283 algorithms. A data structure is responsible for 82 00:04:42,283 --> 00:04:44,968 organizing data in a way that supports fast queries. 83 00:04:44,968 --> 00:04:48,118 Different data structures support different types of queries. 84 00:04:48,118 --> 00:04:52,353 I'll assume that you're familiar with the structures that you typically encounter 85 00:04:52,353 --> 00:04:55,658 in a basic programming class. Including arrays and vectors, lists, 86 00:04:55,658 --> 00:04:56,224 stacks. Q's. 87 00:04:56,224 --> 00:05:00,357 Hopefully, you've seen at some point both trees and heaps, or your willing to read 88 00:05:00,357 --> 00:05:04,491 a bit about them sometime outside of the course, but we will also include a brief 89 00:05:04,491 --> 00:05:07,298 review of each of those data structures as we go along. 90 00:05:07,298 --> 00:05:11,074 There's two extremely useful data structures that we'll discuss in detail. 91 00:05:11,074 --> 00:05:13,166 The first, is balance binary search trees. 92 00:05:13,166 --> 00:05:16,891 These data structures dynamically maintain ordering on a set of elements 93 00:05:16,891 --> 00:05:20,719 while supporting a large number of queries that run in time logarithmic on 94 00:05:20,719 --> 00:05:23,795 the size of the set. The second data structure we'll talk a 95 00:05:23,795 --> 00:05:27,957 fair bit about is hash tables or hash mats which keep track of the dynamic set 96 00:05:27,957 --> 00:05:31,066 while supporting extremely fast insert and look up queries. 97 00:05:31,066 --> 00:05:35,229 We'll talk about some canonical uses of such data structures as well as what's 98 00:05:35,229 --> 00:05:37,970 going on under the hood in a typical implementation. 99 00:05:37,970 --> 00:05:42,272 Of such a data structure. There's a number of important concepts in 100 00:05:42,272 --> 00:05:46,134 the design and analysis of algorithms that we won't have time to cover in this 101 00:05:46,134 --> 00:05:48,774 five week course. Some of these will be covered in the 102 00:05:48,774 --> 00:05:52,537 sequel course, Design and Analysis of Algorithms two, which corresponds to the 103 00:05:52,537 --> 00:05:55,275 second half of Stanford's ten week course on this topic. 104 00:05:55,275 --> 00:05:58,892 The first part of this sequel course focuses on two more algorithm design 105 00:05:58,892 --> 00:06:01,140 paradigms. First of all the design analysis if 106 00:06:01,140 --> 00:06:05,149 greedy algorithms with applications to minimum spanning trees, scheduling, and 107 00:06:05,149 --> 00:06:08,521 information theoretic coding. And secondly, the design and analysis of 108 00:06:08,521 --> 00:06:12,090 dynamic programming algorithms with example applications being in genome 109 00:06:12,090 --> 00:06:14,826 sequence. And shortest path protocols in 110 00:06:14,826 --> 00:06:18,399 communication networks. The second part of the sequel course 111 00:06:18,399 --> 00:06:21,228 concerns NP complete problems, and what to do about them. 112 00:06:21,228 --> 00:06:24,966 Now NP complete problems are problems that, assuming a famous mathematical 113 00:06:24,966 --> 00:06:28,755 conjecture you might have heard of, which is called the P not equal to NP 114 00:06:28,755 --> 00:06:32,544 conjecture, are problems that cannot be solved under this conjecture by any 115 00:06:32,544 --> 00:06:35,929 computationally efficient algorithm. We'll discuss the theory on NP 116 00:06:35,929 --> 00:06:39,769 completeness, with a focus on what it means for you as an algorithm designer. 117 00:06:39,769 --> 00:06:43,204 We'll also talk about several ways to approach NP complete problems. 118 00:06:43,204 --> 00:06:46,286 Including fast algorithms that correctly solve special cases. 119 00:06:46,286 --> 00:06:48,963 Fast heuristics with provable performance guarantees. 120 00:06:48,963 --> 00:06:52,915 And exponential time algorithm. that are qualitatively faster than brute 121 00:06:52,915 --> 00:06:55,300 force search. Of course there are plenty of important 122 00:06:55,300 --> 00:06:57,370 topics that can't be fit into either of these. 123 00:06:57,370 --> 00:07:01,025 two 5-week courses. Depending on the demand, there might well 124 00:07:01,025 --> 00:07:04,300 be further courses on more advanced topics. 125 00:07:04,300 --> 00:07:08,147 Following this course is going to involve a fair amount of time and effort on your 126 00:07:08,147 --> 00:07:10,233 part. So, it's only reasonable to ask, what can 127 00:07:10,233 --> 00:07:12,690 you hope to get out of it? What skills will you learn? 128 00:07:12,690 --> 00:07:15,114 Well, primarily even though this isn't a 129 00:07:15,114 --> 00:07:18,049 programming class per se, it should make you a better programmer. 130 00:07:18,049 --> 00:07:21,259 You'll get lots of practice describing and reasoning about algorithms. 131 00:07:21,259 --> 00:07:24,790 You'll learn algorithm design paradigms, so really high level problem solving 132 00:07:24,790 --> 00:07:28,184 strategies that are relevant for many different problems across different 133 00:07:28,184 --> 00:07:31,302 domains and tools for predicting the performance of such algorithms. 134 00:07:31,302 --> 00:07:34,603 You'll learn several extremely fast subroutines for processing data and 135 00:07:34,603 --> 00:07:37,997 several useful data structures for organizing data that could be deployed 136 00:07:37,997 --> 00:07:39,508 directly. In your own programs. 137 00:07:39,508 --> 00:07:43,850 Second while this is not a math class per say, we'll wind up doing a fair amount of 138 00:07:43,850 --> 00:07:47,721 mathematical analysis and this in tern with sharper your mathematical and 139 00:07:47,721 --> 00:07:51,854 analytical skills you might ask why is mathematics relevant for a class in the 140 00:07:51,854 --> 00:07:55,621 design and analysis of algorithms seemingly more of a programming class, 141 00:07:55,621 --> 00:07:58,756 well let me be clear. I am totally uninterested in merely 142 00:07:58,756 --> 00:08:03,282 telling you facts, or regurgitating code that you can already find on the web, or 143 00:08:03,282 --> 00:08:07,865 in any number of good programming books. My goal here in this class, and the way I 144 00:08:07,865 --> 00:08:12,561 think I can best supplement the resources that you probably already have access to, 145 00:08:12,561 --> 00:08:15,390 is to explain why. Things are the way they are. 146 00:08:15,390 --> 00:08:18,096 Why we analyze the algorithms in the way that we do. 147 00:08:18,096 --> 00:08:21,582 Why various super fast algorithms are, in fact, super fast, and so on. 148 00:08:21,582 --> 00:08:25,381 And it turns out that good algorithmic ideas usually require non trivial 149 00:08:25,381 --> 00:08:27,723 mathematical analysis to understand properly. 150 00:08:27,723 --> 00:08:31,574 You'll require fundamental insights into the specific algorithms and data 151 00:08:31,574 --> 00:08:35,633 structures that we discuss in the course. And hopefully, many of these insights 152 00:08:35,633 --> 00:08:38,340 will prove useful, more generally, in your other work. 153 00:08:39,440 --> 00:08:43,298 Third, and perhaps most relevant for those of who, who work in some other 154 00:08:43,298 --> 00:08:47,263 discipline, this course should help you learn how to think algorithmically. 155 00:08:47,263 --> 00:08:51,068 Indeed, after studying algorithms, it's hard not to see them pretty much 156 00:08:51,068 --> 00:08:53,480 everywhere. Whether you're riding an elevator, 157 00:08:53,480 --> 00:08:56,909 watching a flock of birds, buying and selling stocks out of your 158 00:08:56,909 --> 00:08:59,213 portfolio, or even watching an infant learn. 159 00:08:59,213 --> 00:09:02,697 As I said in the previous video, algorithmic thinking is becoming 160 00:09:02,697 --> 00:09:06,823 increasingly useful and prevalent in the fields outside computer science and 161 00:09:06,823 --> 00:09:09,074 technology. Like, in biology, statistics, and 162 00:09:09,074 --> 00:09:11,505 economics. Fourth, if you're interested in feeling 163 00:09:11,505 --> 00:09:15,248 like a card-carrying computer scientist in some sense, then you'll definitely 164 00:09:15,248 --> 00:09:18,359 want basic literacy in all of the topics that we'll be covering. 165 00:09:18,359 --> 00:09:22,053 Indeed, one of the things that makes studying algorithms so fun is it really 166 00:09:22,053 --> 00:09:25,942 feels like you're studying a lot of the greatest hits from the last 50 years of 167 00:09:25,942 --> 00:09:28,664 computer science. So after this class, no longer will you 168 00:09:28,664 --> 00:09:32,601 feel excluded at that computer science cocktail party when someone cracks a joke 169 00:09:32,601 --> 00:09:35,810 about Dijkstra's algorithm. Now you'll know exactly what they mean. 170 00:09:35,810 --> 00:09:40,003 Finally there's no question that setting this material is helpful for technical 171 00:09:40,003 --> 00:09:43,252 interview questions. To be clear my sole goal here is to teach 172 00:09:43,252 --> 00:09:46,030 you algorithms. And not to prepare you for interviews, 173 00:09:46,030 --> 00:09:49,280 for interviews perse. But over the years countless students of 174 00:09:49,280 --> 00:09:53,526 mine have regaled me with stories about how mastering the concepts of this class 175 00:09:53,526 --> 00:09:56,880 enabled them to ace any technical question they were ever asked. 176 00:09:56,880 --> 00:10:02,323 I told you this is fundamental stuff. So what do I expect from you? 177 00:10:02,323 --> 00:10:07,937 Well, honestly, the answer is nothing. After all isn't the whole point of a free 178 00:10:07,937 --> 00:10:12,142 online class like this one that anyone can take it and devote as much effort to 179 00:10:12,142 --> 00:10:14,927 it as they like. So that said as a teacher it's still 180 00:10:14,927 --> 00:10:17,766 useful to have one or more canonical students in mind. 181 00:10:17,766 --> 00:10:21,287 And I thought I go ahead and be transparant with you about how I'm 182 00:10:21,287 --> 00:10:24,966 thinking about these lectures. Who I have in mind that I'm teaching to. 183 00:10:24,966 --> 00:10:28,750 Though again please don't feel discouraged if you don't conform to this 184 00:10:28,750 --> 00:10:32,114 canonical student template. I'm happy to have the opportunity to 185 00:10:32,114 --> 00:10:34,690 teach you about algorithms no matter who you are. 186 00:10:34,690 --> 00:10:38,730 So first I have in mind someone who knows at least some programming. 187 00:10:38,730 --> 00:10:40,890 For example consider the previous lecture. 188 00:10:40,890 --> 00:10:45,005 We talked about a recursive approach to multiplying two numbers, and I mentioned 189 00:10:45,005 --> 00:10:48,811 how a certain mathematical expression. Back then we labeled it in star, and 190 00:10:48,811 --> 00:10:51,730 circled it in green. How that expression naturally translated 191 00:10:51,730 --> 00:10:54,818 in to a recursive algorithm. In particular, I was certainly assuming 192 00:10:54,818 --> 00:10:57,492 that you had some familiarity with the recursive programs. 193 00:10:57,492 --> 00:11:01,226 If you feel comfortable with my statement in that lecture, if you feel like could 194 00:11:01,226 --> 00:11:04,268 code up a recursive integer multiplication algorithm based on the 195 00:11:04,268 --> 00:11:07,818 high-level outline that I gave you, then you should be in good shape for this 196 00:11:07,818 --> 00:11:09,293 course. You should be good to go. 197 00:11:09,293 --> 00:11:12,474 If you weren't comfortable with that statement, well, you might not be 198 00:11:12,474 --> 00:11:15,885 comfortable with the relatively high conceptual level at which we discuss 199 00:11:15,885 --> 00:11:18,743 programs in this course. But I encourage you to watch the next 200 00:11:18,743 --> 00:11:22,523 several videos anyways to see if you get enough out of them to make it worth your 201 00:11:22,523 --> 00:11:24,888 while. Now while I'm aiming these lectures at 202 00:11:24,888 --> 00:11:29,064 people who knows some programming, I'm not making any assumptions what so ever 203 00:11:29,064 --> 00:11:31,795 about exactly which programming languages you know. 204 00:11:31,795 --> 00:11:36,025 Any standard imperative languages you know, like C Java or Python is totally 205 00:11:36,025 --> 00:11:39,345 fine for this course. Now to make these lectures accessible to 206 00:11:39,345 --> 00:11:43,789 as many programmers as possible and to be honest you know, also to promote thinking 207 00:11:43,789 --> 00:11:47,377 about programming at a relatively abstract and conceptual level. 208 00:11:47,377 --> 00:11:51,232 I won't be describing algorithms in any particular programming language. 209 00:11:51,232 --> 00:11:55,676 Rather when I discuss the algorithms I'll use only high level pseudo code or often 210 00:11:55,676 --> 00:11:58,422 simply English. My inductive hypothesis is that you are 211 00:11:58,422 --> 00:12:02,260 capable of translating such a high level description into a working program in 212 00:12:02,260 --> 00:12:05,611 your favorite program language. In fact, I strongly encourage everyone 213 00:12:05,611 --> 00:12:09,448 watching these lectures to do such a translation of all of the algorithms that 214 00:12:09,448 --> 00:12:11,925 we discussed. This will ensure your comprehension and 215 00:12:11,925 --> 00:12:14,597 appreciation of them. Indeed many professional computer 216 00:12:14,597 --> 00:12:18,434 scientists and programmers don't feel that they really understand an algorithm 217 00:12:18,434 --> 00:12:21,737 until they've coded it up. Many of the courses assignments will have 218 00:12:21,737 --> 00:12:24,214 a problem in which we ask you to do precisely this. 219 00:12:24,214 --> 00:12:28,002 Put another way, if you're looking for a sort of coding cookbook, code that you 220 00:12:28,002 --> 00:12:30,480 can copy and paste directly into your own programs. 221 00:12:30,480 --> 00:12:34,413 Without necessarily understanding how it works, then this is definitely not the 222 00:12:34,413 --> 00:12:37,101 course for you. There are several books out there that 223 00:12:37,101 --> 00:12:40,120 cater to programmers, looking for such coding cookbooks. 224 00:12:40,120 --> 00:12:44,122 Second for these lectures I have in mind someone who has at least a modest amount 225 00:12:44,122 --> 00:12:47,929 of mathematical experience though perhaps with a fair bit of accumulated rust 226 00:12:47,929 --> 00:12:51,199 concretely I expect you to be able to recognize a logical argument. 227 00:12:51,199 --> 00:12:53,891 That is, a proof. In addition two methods of proof that I 228 00:12:53,891 --> 00:12:57,522 hope you've seen before are proofs by induction and proofs by contradiction. 229 00:12:57,522 --> 00:13:01,441 I also need you to be familiar with basic mathematical notation like the standard 230 00:13:01,441 --> 00:13:04,738 quantifier and summation symbols. A few of the lectures on randomized 231 00:13:04,738 --> 00:13:08,560 algorithms and hashing will go down much easier for you if you've seen discreet 232 00:13:08,560 --> 00:13:12,431 probability at some point in your life, but beyond these basics the lectures will 233 00:13:12,431 --> 00:13:15,250 be self contained. You don't even need to know any calculus, 234 00:13:15,250 --> 00:13:19,216 say for a single integral that magically pops up in the analysis of the randomized 235 00:13:19,216 --> 00:13:22,449 quick sort algorithm. I imagine that many of you have studied 236 00:13:22,449 --> 00:13:24,622 math in the past but you could use a refresher. 237 00:13:24,622 --> 00:13:27,396 You're a bit rusty. And there's plenty of free resources out 238 00:13:27,396 --> 00:13:30,956 there on the Web that I encourage you to explore and find something you like. 239 00:13:30,956 --> 00:13:34,515 But one that I want to particularly recommend is a great set of free lecture 240 00:13:34,515 --> 00:13:36,503 notes. It's called Mathematics for Computer 241 00:13:36,503 --> 00:13:38,769 Science. it's authored by Eric Lehmann and Tom 242 00:13:38,769 --> 00:13:41,034 Layton. And it's quite easy to find on the Web if 243 00:13:41,034 --> 00:13:43,854 you just do a Web search. And, those notes cover all of the 244 00:13:43,854 --> 00:13:46,860 prerequisites that we'll need in addition to tons of other stuff. 245 00:13:48,440 --> 00:13:52,166 In the spirit of keeping the course as widely accessible as possible we're 246 00:13:52,166 --> 00:13:55,396 keeping the required supporting materials to an absolute minimum. 247 00:13:55,396 --> 00:13:59,471 Lectures are meant to be self contained and we'll always provide you with lecture 248 00:13:59,471 --> 00:14:03,197 notes and power point in pdf format. Once in awhile we'll also provide some 249 00:14:03,197 --> 00:14:06,366 additional lecture notes. No textbook is required for this class, 250 00:14:06,366 --> 00:14:10,317 but that said, most of the material that we'll study is well covered in a number 251 00:14:10,317 --> 00:14:12,738 of excellent algorithms books that are out there. 252 00:14:12,738 --> 00:14:16,936 So I'll single out four such books here. The first three I mention because they've 253 00:14:16,936 --> 00:14:20,740 all had a significant influence on the way that I both think about and teach 254 00:14:20,740 --> 00:14:23,456 algorithms. So it's natural to acknowledge, that debt 255 00:14:23,456 --> 00:14:25,531 here. One very cool thing about the second 256 00:14:25,531 --> 00:14:29,482 book, the one by Dasgupta, Papadimitriou, and Vazirani, is that the authors have 257 00:14:29,482 --> 00:14:32,412 made a version of it. Available online for free and again if 258 00:14:32,412 --> 00:14:36,487 you search on the authors name and the textbook in the textbook title you should 259 00:14:36,487 --> 00:14:38,621 have no problem coming up with a web search. 260 00:14:38,621 --> 00:14:42,260 Similarly that's the reason I've listed the fourth book, those authors have 261 00:14:42,260 --> 00:14:46,287 likewise made essentially complete version of that book available online and 262 00:14:46,287 --> 00:14:49,780 it's, it's a good match with the material that we're going to cover here. 263 00:14:49,780 --> 00:14:53,263 If you're looking for more details about something covered in this class or simply 264 00:14:53,263 --> 00:14:56,453 a different explanation than the one that I give you, all of these books are going 265 00:14:56,453 --> 00:14:59,475 to be good resources for you. There's also a number of good algorithm 266 00:14:59,475 --> 00:15:01,447 textbooks that, that I haven't put on this list. 267 00:15:01,447 --> 00:15:03,840 I encourage you to explore and find your own favorite. 268 00:15:03,840 --> 00:15:07,663 In our assignments, we'll sometimes ask you to code up an algorithm and use it to 269 00:15:07,663 --> 00:15:10,495 solve a concrete problem that is too large to solve by hand. 270 00:15:10,495 --> 00:15:14,035 Now, we don't care what programming language or development environment you 271 00:15:14,035 --> 00:15:17,339 use to do this, as we're only going to be asking you for the final answer. 272 00:15:17,339 --> 00:15:20,973 Thus, we're never requiring anything specific, just that you are able to write 273 00:15:20,973 --> 00:15:23,852 and execute programs. If you need help or advice about how to 274 00:15:23,852 --> 00:15:27,156 get set up with a suitable coding environment, we suggest that you ask 275 00:15:27,156 --> 00:15:29,800 other students for help via the course discussion forum. 276 00:15:29,800 --> 00:15:32,700 Finally, let's talk a bit more about assessment. 277 00:15:32,700 --> 00:15:36,132 Now this course doesn't have official grades per se, but we will be assigning 278 00:15:36,132 --> 00:15:38,672 weekly homeworks. Now we're going to assign homeworks for 279 00:15:38,672 --> 00:15:42,149 three different reasons, the first is just for self assessment, it's to give 280 00:15:42,149 --> 00:15:45,314 you the opportunity to test your understanding of the material, so that 281 00:15:45,314 --> 00:15:48,880 you can figure out which topics you've mastered and which ones that you haven't. 282 00:15:48,880 --> 00:15:52,862 The second reason we do it is to impose some structure on the course, including 283 00:15:52,862 --> 00:15:55,181 deadlines. To provide you with some additional 284 00:15:55,181 --> 00:15:57,450 motivation to work through all of the topics. 285 00:15:57,450 --> 00:15:59,920 Deadlines also have a very important side effect. 286 00:15:59,920 --> 00:16:02,743 That it synchronizes a lot of the students in the class. 287 00:16:02,743 --> 00:16:06,474 And this, of course, makes the course discussion forum a far more effective 288 00:16:06,474 --> 00:16:09,852 tool to seek and provide help in understanding the course material. 289 00:16:09,852 --> 00:16:13,784 The final reason that we give homeworks is, for, to satisfy those of you, who, on 290 00:16:13,784 --> 00:16:17,313 top of learning the course material, are looking to challenge yourself 291 00:16:17,313 --> 00:16:20,158 intellectually. Now, this class has tens of thousands of 292 00:16:20,158 --> 00:16:22,559 students. So, it's obviously essential that the 293 00:16:22,559 --> 00:16:26,526 assignments can be graded automatically. Now, we're currently only in the 1.0 294 00:16:26,526 --> 00:16:29,189 generation of free online courses, such as this one. 295 00:16:29,189 --> 00:16:32,895 So the available tools for auto graded assessment are currently rather 296 00:16:32,895 --> 00:16:35,453 primitive. So we'll do the best we can, but I have 297 00:16:35,453 --> 00:16:38,690 to be honest with you. It's difficult, or maybe even impossible. 298 00:16:38,690 --> 00:16:42,516 Test deep understanding of the design analysist of algorithms, using the 299 00:16:42,516 --> 00:16:45,280 current set of tools, thus while the lecture content. 300 00:16:45,280 --> 00:16:48,911 And this online is, in no way, watered down from the original Stanford version. 301 00:16:48,911 --> 00:16:52,683 The required assignments and exams we'll give you are not as demanding as those 302 00:16:52,683 --> 00:16:55,230 that are given in the on campus version of the course. 303 00:16:55,230 --> 00:16:58,578 To make up for this fact, we'll occasionally propose optional algorithm 304 00:16:58,578 --> 00:17:01,691 design problems, either in a video or via supplementary assignment. 305 00:17:01,691 --> 00:17:05,228 We don't have the ability to grade these. But we hope that you'll find them 306 00:17:05,228 --> 00:17:08,104 interesting and challenging. And that you'll discuss possible 307 00:17:08,104 --> 00:17:11,028 solutions with other students via the course discussion forum. 308 00:17:11,028 --> 00:17:14,848 So I hope this discussion answered most of the questions that you have about the 309 00:17:14,848 --> 00:17:16,970 course. Let's move on to the real reason that 310 00:17:16,970 --> 00:17:19,140 we're all here, to learn more about algorithms.