пожалуйста, возвращайтесь позднее
пожалуйста, возвращайтесь позднее
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 [inaudible] 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. 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.