cs313 ยป

**Introduction**

This course is about really challenging computer problems,
and the area of computer science that deals with these challenging problems
is called theoretical computer science, or more specifically, complexity theory.

**Challenging Problems**

Welcome to our course on dealing with challenging problems. First off, I should probably start by telling you what a challenging problem actually is. Normally, the situation is as follows: When you want to solve a problem with a computer, you write some program on your computer to tell it what you want to do with a certain input. Then you take your input, you feed it into the computer, and the computer will work on your problem. So it'll probably tell you to wait if you've written your program like this, might make some noises, and after a certain time the computer will be done, and it will produce your output. Now, you would think that computers today are powerful enough to basically do this for any problem for which you can write a program. But you might already know that sometimes this is not the case. So sometimes problems are so challenging to solve, even for a computer, even for a very, very fast computer, that you will not get the output. Instead, all that will happen is that the computer will tell you to wait. It might make noises again, and it will keep on telling you to wait. Might make more noise because it's working so hard. But no matter how long you wait, the computer is not able to produce an output because the problem that you're giving it is just too hard, even for a computer.

This course is about exactly these challenging problems. Problems that are really, really tough for computers to solve. But it is also a course about what to do with those challenging problems. So how you can solve them using a computer despite them being very hard to solve. Now, the part of computer science that deals with challenging problems is called theoretical computer science. The first part of theoretical computer science that we will be looking at is called complexity theory. And complexity theory is the science of how much, or more specifically, how much resources. So time, or memory, and also other resources a computer will need to solve a given problem. The other part of theoretical computer science that we'll be looking at is called computability. And computability asks the more fundamental question. Computability asks, can a computer solve a given problem at all, given as much time and as much memory as you want? Now, this course will be mostly looking at complexity theory, but we'll also do computability for 2 reasons: First of all, it kind of belongs in the whole picture, to say what computers can do and cannot do. And the other reason is that many problems that fall into the area of computability are actually very relevant, and it's important to understand computability to know what is doable and what isn't. And it's also important to understand computability to know what's possible in general and what isn't.

This course has, mainly, 3 goals. After having taken this course, you will be able to recognize what makes a problem challenging for a computer to solve. You will also have an understanding of why these problems are challenging. And through that understanding, I will show you a number of techniques that you can use to navigate around computational complexity. So this course will not only enable you to recognize and understand tough problems but also give you many tools and techniques that you can use to actually solve them in practice. And this is something that, in my experience, is not taught very often. So some people will be able to recognize that a problem is challenging; fewer people will understand what makes these problems challenging. But when it comes down to knowing the techniques that you can use to solve these challenging problems, despite their computational complexity, then my experience is that knowing these techniques can really make you stand out. During this course we will come across many algorithms especially when we study complexity theory, but this is not a course about algorithms in general. Rather, they will be a means to an end, to understand what makes problems hard, and, of course, also to navigate around computational complexity. So for taking this course you should have a basic understanding of algorithms, although we'll also cover the basics to make sure that you all start out on the same level.

So to familiarize yourself with complexity theory and computability, here's our first quiz. As in any Udacity course, the quizzes are here to help you see if you have understood the content, and they do not count toward your final grade. So our first quiz will be about familiarizing yourself with the areas of computability and complexity theory. Here I have 3 questions that you could ask in theoretical computer science. So how fast can a computer find a way between 2 points on a map? Can a program decide if another program is malware? So, for example, a virus or trojan. And how much memory is needed to sort a given database? What I would like to know from you, for each of these 3 questions here, is if that question would be studied in computability or if that question would be studied in complexity theory. Please make your selection for each of these questions.

And, of course, there's going to be more challenging quizzes here, but for a warmup I think it is very good to understand the difference between computability and complexity theory. The first question, how fast a computer can find a way between 2 points on a map, belongs in complexity theory because here it's a question of resources. So "how fast," that is a question about the time that a computer needs, and therefore, investigating this question belongs in complexity theory. Asking if a program can decide if another program is malware, that belongs in computability because we are not asking about any resources, we're just if it's possible in principle. We're asking, "Can a program do that?" We're not asking how fast or with how much memory it can do that. In the third question we are, again, asking about resources. We're asking about how much memory, and therefore, this 1 belongs in complexity theory. The question about memory is something we are not going to look at much in this course. Actually, I think we are not going to look at it at all. We're going to be concerned mostly with time, how fast a computer can solve a given problem, and, toward the end of this unit, we are going to pose the ultimate resource question and ask, "What are the limits of computation in general?

This course has 7 units, and I'm now going to give you a brief overview of what we have planned. The first 3 units will introduce you to challenging problems, and I'm going to do this by telling you about some problems that are really relevant in practice, yet very, very hard to solve. We're also going to do a bit of the formal background of challenging problems through a concept known as NP-completeness. And I'm going to show you how to recognize NP-completeness so that you'll be able to develop an intuition when you encounter a challenging problem. So the first 3 units are basically about recognizing the hardness of a problem. In units 4 to 6 we are then going to discuss what to do if you encounter a hard problem, because, as I told you in the beginning, many people, once they've recognized that their problem is hard to solve, actually tend to stop. And these units here will give you various techniques for solving hard problems. Solving them very exactly using techniques such as optimized search trees and pre-processing, but also solving them almost optimally using techniques such as approximation and randomization. So this will give you an aresenal of tools that you can use to try and tackle any hard problem, should you encounter it. And then in the final unit we'll be going into computability and talk about unsolvable problems, problems that no computer can ever solve, and how you could solve them, nevertheless, if you come across them.

In this unit I'm going to introduce you to 3 computer problems that will actually turn out to be quite challenging. And I'm going to do this by introducing you to 3 computer scientists, Alice, Bob, and Carol. All 3 haven't yet had the chance to learn theoretical computer science or about challenging problems. Maybe they just didn't have the time or didn't think it was useful to them. But they're all pretty good practical computer scientists. So they have experience in programming, and know their way around basic algorithms. That's also why all of them work in very high-profile jobs. Alice works in telecommunications; Bob works in biotech or bioinformatics, and Carol works in finance. Throughout this unit, you'll learn more about the problems that Alice, Bob, and Carol are working on, and you'll also meet some additional computer scientists throughout this course. But let's focus on Alice first.

Alice is working for a global telecommunications company that owns a telecommunications network around the world. So the network of her company looks something like this. And, of course, this is just to give you an idea; in reality the network is much larger. But they basically have telecommunications centers that are spread out around the world. And these communication centers are connected through cables, something like this. And again, there's many more communication centers, and many more cables here, of course. But this is just to illustrate the problem to you that she is working on. So you see, not every communications center is connected to every other communications center, but they're selectively connected through these blue cables here. Now, of course, for the company that Alice is working for, it's very important to check the integrity of the whole network, which basically means that you have to check if every single cable here is working. Now, to do this, her company can install monitoring devices, which I'm going to draw with a green circle like this here. So the company could, for example, install a monitoring device here. And what that monitoring device does is, it checks the integrity of all cables that are connected to that communications center where you install the device. So it looks something like this. So installing a device here would allow you to monitor all these 5 cables that are drawn green here, and of course in order to monitor the whole network, you would need more than 1 device. But you would not need to install a device at every single communications center. So for example, if you install another device here, which monitors these cables here, and another device here, then this communications center right here does not need an additional device, because all the cables that are attached to it are already monitored by the other communications centers. Now, installing 1 of these devices is, of course, quite expensive. And that is why Alice has been asked by her employer, the telecommunications company, to figure out a way to monitor the whole network by installing as few devices as possible. And, as I said, the whole network is, of course, much more complex than this. So it contains about 500 communications centers, say, so she cannot do it manually. She definitely needs to write an algorithm to help her with this.

Now, before we go deeper into the algorithm, let's just make sure that you understand the problem that Alice has to work on. So let's take this very simple communications network here, and what I would like you to do is to figure out the minimum number of devices that would need to be installed in this network in order to monitor the whole network. And please enter your answer as a number in here.

There are a couple of different solutions for this, but all of these solutions will have in common that you need at least and I will show you one of these solutions. So you could install one here, which would monitor these cables here. You could install one here to monitor these cables, and then you need one here, or you could have one here. There are other possibilities, as I said, to monitor these 2 cables here. And then finally, you can install one here to monitor these 2. So this is one solution where you use 4 monitoring devices to monitor the whole network, and it's not possible with 3.

So how can Alice approach her problem if there are lots of these communication centers? Certainly, she can't just do a random approach and trust that she's somehow going to find the best possible solution. So she needs some sort of algorithm to solve her problem. And one algorithm that would be guaranteed to find the best possible solution, or the minimum number of devices that you need, would be to just try all possibilities. So, for example, if you have a very simple network, such as this one here-- Well, first of all, let's have a look at the best possible solution, and we're going to do this as a little quiz. So I want you to tell me where to install the monitors so that each cable in this network is monitored. And I want you to do this by checking off the communication centers where we need to install monitoring devices.

And the answer to that is that we only need to install 2 devices-- one up here and one down here. This one up here covers those 3 cables, and this one down here covers these 3 here, so this one is covered twice. But we need at least 2 devices to cover the whole network and actually, in this case, this is the only possible solution for this. But of course, a computer can't just see that 2 devices suffice. So Alice's algorithm 'trying all possibilities' would have to go through all of the possibilities that you could have of installing a device at a certain communication point or not installing one. So, in this case here, that would be 16 different possibilities if we give the communication points little letters here so we can better distinguish them. So Alice's algorithm 'trying all possibilities' would have to consider installing no device at all, which would of course not be a valid solution. It could try installing just a device at 'A' which, again, would not be a valid solution, and so on. And of course the algorithm would also find solutions that are valid but would use more than the minimum number of monitoring devices that are actually needed. But since the algorithm tries all possibilities, it will also find this solution here using just 2 devices.

So to give you a more clear understanding about the algorithm that Alice is using, I'm going to write it down in a sort of pseudo-code. That means I'm not going to write real Python code or any other programming language that you're used to but, basically, do a more formal description of this 'trying all possibilities' algorithm. So the solution that we're looking for is going to be written into a variable called 'minimum devices.' And initially to start off the algorithm, we're going to set that variable to the number of communication centers because that is the maximum number of monitoring devices that you are going to need in any case. The algorithm then goes through each assignment of the values 0 and 1 to the communication centers. And what I mean by that is a value of 0 means that communication center does not get a monitoring device, and a 1 means that we are going to install a monitoring device at that communication center. The algorithm then checks if the assignment is valid. And what I mean by valid is that the communication centers that have a 1 in the assignment are monitoring all the cables in the network. If we have a valid assignment, the algorithm then computes how many devices we used in that assignment, which is simply summing all the 1's that are in the current assignment that we're working on. The algorithm then checks if the current assignment is a better solution than the best one we have found so far. And it does that by taking the minimum of the currently known best solution, which is 'minimum devices'--here--and the number of devices in the current assignment. If you're familiar with algorithms, you might already see a few issues-- even in this pseudo-code--with this algorithm. But we're going to go into that more deeply in Unit 3, actually. Right now, we're just going to work with this very simple version here.

So once Alice has programmed this algorithm--here--she, of course, tests it. So she constructs small test instances that she can solve herself and runs them through this algorithm. Now, one thing I would like you to figure out-- now if she actually runs a small test instance through this algorithm-- is how many loops that algorithm goes through. And by 'loops' I mean how many times those lines--3 to 5, here--are executed for a certain network. So let's say that the network consists of 5 communication centers. So for a network with 5 communication centers, I want to know how often lines 3 to 5--this part here--are executed.

And the solution to that is 32 because we have 5 communication centers, and for each communication center we have to construct a separate solution-- one where the communication center does receive a monitoring device, and one where it doesn't. So we have 2 possibilities for the first one, then 2 for the second one, and so on. And this is 2^5 which is 32.

So let's see what happens if Alice is running her algorithm on a larger network. So, instead of 5 communication centers, she has 20 communication centers in her network. How often are the lines 3 to 5 executed in that case?

So the answer here is that the lines are executed 1,048,576 times or just about a million times. And the way you calculate this is very similar to here above. So instead of 2^5, you now have to take 2^20 because-- for the 20 communication centers--you're trying all separate possibilities of having them with a monitoring device or not.

So, you can see the general pattern here, and what you can see is that the number of times that lines 3 to 5 are executed grows very rapidly. So, for 5 communication centers it's just 32; for 20, it's already a million. Now, Alice's telecommunications company, of course, has lots more communication centers than that. So, let's assume they have about 500 communication centers. So, for 500 communication centers--if Alice runs her algorithm-- how often are the lines 3 to 5 executed in that case? More than a trillion times? More than a trillion trillion times? Or way more than that?

And the correct answer here is 'way more than that.' It's 2^500, which is approximately 10^150. So, that's not even a number we have a sensible name for. So, Alice's algorithm, while being correct, does not offer any way of finding the solution for the problem that she's working on. And now, of course, the question is if this is just because Alice wasn't able to think of a better algorithm than this, here, or because the problem that she's working on is actually a hard problem to solve.

Complexity theory deals a lot with problems and with algorithms, so we should say a little bit more about each one of the two. So, a problem normally consists of 3 parts. The first one is very simple. It's just a name that we give to the problem so that when we talk about it, we know how to reference it. In this case we're going to find a better name for that soon, but in this case, we'll just call the problem that Alice was working on 'Alice's problem.' For each problem, we also need to say something about the input that we're expecting for it. So in this case, here, it's a network of communication centers. And, of course, we also need to say something about the output that we are expecting. So in this case, here, it would be the minimum number of monitoring devices to cover all cables or all connections. Of course the most useful output would be to know not only the minimum number of monitoring devices, but where we should actually put them. But you're soon going to see that it doesn't really make much of a difference most of the time if we are just asking for the minimum number or if we are actually asking for the communication centers where we need to put those devices. Now, what Alice devised to solve this problem was a possible algorithm. Now, there's no really accepted definition of what an algorithm actually is. But, for us, it's enough to say that whenever we talk about an algorithm, we'll be talking about the description of a computer program that is able to solve the problem that we are given. Now the question that we want to answer for Alice's problem-- since the algorithm that she has found is not very good-- is if the problem that she's working on is a hard problem or an easy problem. And what we mean by that is if it's possible to find a more efficient algorithm for this problem. If that is the case, then we would call this problem an easy problem. Or, we will soon have a more precise definition of that, actually. And if it's not possible to find a better algorithm for the problem, then this would be considered a hard problem. Now, the hardness of a problem tells you how fast and with how many resources you can solve the problem. But, of course, that would require you to find the best possible algorithm for that problem. And 'best' is not a very scientific term, so we'll have to say a little bit more about the analysis of algorithms.