Hello everybody. I'm Daniel Kane. Welcome to the data structures and algorithms specialization. For this very first lecture, we're going to start at the very beginning and talk about why do you need to study algorithms in the first place. So the basic goal in this lecture is to sort of talk about what are the sorts of problems that we're going to be discussing in this algorithms class and why they're important. And in the context of doing this, we're also going to discuss some problems that you might run into when writing computer programs that might not actually require sophisticated techniques that we'll be discussing in this course. And on the other hand, we'll discuss some other sorts of problems that you might want to solve that go beyond the sort of material that we will be talking about here. So, to begin with, suppose that you're writing a computer program. There are a lot of tasks that you might want to perform that you don't really need to think about very hard. These are things like displaying a given text on the screen, or copying a file from one location to another, or searching a file for a given word. Each of these algorithms has essentially a linear scan. You go through every word in the file, one at a time and you do the appropriate thing. And for each of these problems there's essentially a linear scan that you really can't do much better than. In order to do whatever task it is you're doing, you have to go through all the data one at a time and process it appropriately. And so when you do more or less the obvious thing, you have a program that works. It solves the problem that you need. And it does so approximately as efficiently as you could expect. So for these sorts of problems you might not have to think very hard about what algorithm you are using. On the other hand, there are some other problems, actual algorithms problems, where it's not so clear what it is you need to do. For example, you might be given a map and need to find the shortest path between two locations on this map. Or you might be given, you might be trying to find the best pairing between students and dorm rooms given some sort of list of preferences, or you might be trying to measure the similarity of two different documents. Now, for these problems it's a lot more complicated, it's not immediately clear how to solve these problems. And even when you do come up with solutions, often the simple solutions to these problems are going to be far too slow. You could end up with some simple algorithm, you could try all possible pairings between people and dorm rooms and return the one that optimizes some function that you're trying to deal with. On the other hand, if you did that, it would probably take a very, very, very long time. And you might not have enough time to wait, and so you might need to do something better. And then even once you have a reasonably efficient algorithm for these problems, there's often a lot of room for further optimization. Improve things so that things run in an hour rather than a day. Or a minute rather than an hour. Or a second rather than a minute. And all of these improvements will have a large effect on how useful this program you've written is. Now, on the other hand, there are some things that you might want to try and do with your computer that go a little bit beyond the sort of things we're discussing in this course. We might want to call these Artificial Intelligence Problems. And these are problems where it's sort of hard to clearly state what it is that you're trying to do. An example of this might be, to try and write a computer program to understand natural language. That is, write a program where I can type something in, some English sentence, asking it, you know, what's the price of milk at the local food store today? And you want the computer to then take this sentence that I wrote, and figure out what it means, figure out some way to parse it. And then do an appropriate lookup and return a useful answer to me. And the problem with doing this isn't so much that anything involved here is actually difficult to perform, but the problem is that fundamentally we don't really understand what it means to interpret an English sentence. Now, I mean we can all speak English, hopefully, if you're listening to this lecture, but we don't sort of really fundamentally understand what it means. It's hard to put it into precise enough language that you can actually write a computer program to do that. Now you have similar problems, like if you want to identify objects in a photograph. You've got a picture, with maybe with a dog and tree and a cloud and you want the computer to identify what's what. Then once again, this is a thing that our brains have gotten very good at doing, and we understand what the question is. However, it's hard to really put into words how you identify that this thing's a dog and this thing's a tree. And this sort of business makes it very difficult to teach a computer to do the same thing. Another thing that you might want to do is teach a computer to play games well like play chess effectively. And, once again, this is a thing where we can sort of identify what it means to do this. But, actually how you want to do it, there's a lot of sort of very vague, intuitive things that go on there. It's not a clearly defined problem that you're trying to solve. And so, for all of these problems sort of the difficulty is not so much that it's hard to do things quickly. But it's hard to even state what it is that you're trying to do and figure out how to approach it. Now, these are problems that we're not going to really cover in this class, we're going to focus on algorithms, how to do things quickly and efficiently. But if you do want to get into AI and want to try and solve these problems, it will be very important that you have a solid grounding in algorithms, so that once you have some idea of what does it mean to identify trees in pictures, you will have an idea of what sort of algorithms can actually support these ideas, which sort of ideas you can actually implement in a reasonable amount of time. And so, what we're going to focus on in this course are the algorithms problems. So, we want problems that are cleanly formulated, like clear mathematical problems. And some of the things we looked at maybe aren't immediately clear, like if you want to find the shortest route between two points on a map, that's not immediately a math problem. But, pretty quickly you can interpret it as such. You can say, well, I want some sequence of intersections, I'm traveling between such that each pair is connected by a road, and the sum of the lengths of the roads is as small as possible. And so, pretty quickly this just becomes a problem where we can very clearly state what it is that we're trying to do but, for which it is still nontrivial to solve it. And so, that's the sort of thing we're going to be talking about in this class. And, hopefully, by the end of it you will have a good idea of how to solve these problems, how to write programs that will solve them very quickly and very efficiently. And that's what we'll be talking about. I hope you enjoy the rest of the class.
