Counting Minimum Cuts (Algorithm)

there may be distinct cuts which are tied for the fewest number of crossing edges. For a concrete example

you could think about a tree. So, if you just look at a star graph, that is hubs and spokes, it's evident that if you isolate any leaf by itself, then you get a minimum cut with exactly one crossing edge. In fact, if you think about it for a little while, you'll see that in any tree you'll have N-1 different minimum cuts, each with exactly one crossing edge. The question concerns counting the number of minimum cuts. Namely, given that a graph may have more than one minimum cut, what is the largest number of minimum cuts that a graph with N vertices can have? We know the answer is at least N-1. We already discussed how trees have N-1 distinct minimum cuts. We know the answer at most something like 2^N, because a graph only has roughly 2^N cuts. In fact, the answer is both very nice and wedged in between. So the answer is exactly N choose 2, where N is the number of vertices. This is also known as N(N-1)/2. So it can be bigger than it is in trees, but not a lot bigger. In particular, graphs have only; undirected graphs have only polynomially many minimum cuts. And that's been a useful fact in a number of different applications. So, I'm going to prove this back to you. All I need is one short slide on the lower bound and then one slide for the upper bound, which follows from properties of the random contraction algorithm.

So for the lower  bound, we don't have to look much beyond our trees example. We're just gonna look at cycles. So for any value of N, consider the N cycle. So here, for example, is the N cycle with N = 8. That would be an octagon. And the key observation is that, just like in the tree, how moving each of the N-1 edges breaks the tree into two pieces and defines the cut. With a cycle, if you remove just one edge, you don't get a cut. The thing remains connected, but if you remove any pair of edges, then that induces a cut of the graph, corresponding to the two pieces that will remain. No matter which pair of edges you remove, you get a distinct pair of groups, distinct cuts. So ranging overall N choose 2 choices of pairs of edges, you generate N choose 2 different cuts. Each of these cuts has exactly two crossing edges, and it's easy to see that's the fewestnpossible. So that's the lower bound, which was simple enough. Let's now move on to the upper bound, which, a purely count-all fact will follow from an algorithm.

So consider any graph that has N vertices, and let's think about the different minimum cuts of that graph. What we're going to use is that the analysis of the contraction algorithm proceeded in a fairly curious way. So remember how we define the success probability of a contraction algorithm. We fixed up front, some min cut (A, B). And we defined the contraction algorithm, the basic contraction algorithm, before the repeated trials. We defined the contraction algorithm as successful, if and only if it output the minimum cut (A, B) that we designated upfront. If it output some other minimum cut, we didn't count it. We said nope, that's a failure. So we actually analyzed a stronger property than what we were trying to solve, which is outputting a given min cut (A, B) rather than just any/all min cut. So how is that useful? Well, let's apply it here. For each of these T minimum cuts of this graph, we can think about the probability that the contraction algorithm outputs that particular min cut. So we're gonna instantiate the analysis with a particular minimum cut (Ai, Bi). And what we proved in the analysis is that the probability that the algorithm outputs the cut (Ai, Bi), not just any all min cut. But, in fact, this exact cut (Ai, Bi) is bounded below by. We, in the end, we made a sloppy inequality. We said it's at least 1/(N^2). But if you go back to the analysis, you'll see that it was, in fact, 2/N(N-1), also known as 1/(N choose 2). So instantiating the contraction algorithm success probability analysis without all of the repeated trials business, we show that for each of these T cuts, for each fixed cut (Ai, Bi), the probability that this algorithm output that particular cut is at least 1/(N choose 2). Let's introduce a name for this event, the event that the contraction algorithm outputs the Ith min cut. Let's call this Si. The key observation is that the Sis are disjoint events. Remember an event is just a subset of stuff that could happen. So one thing that could happen is that the algorithm outputs the Ith main cuts, and by this joint, we just mean that there is no outcome that in a given pair of events. And that's because the contraction algorithm at N to the [inaudible], once it makes its conflicts, it outputs a single cut is a distinct cut. It can only output a dest one of them. Why is it important that these Sis are disjoint events? Well, with disjoint events, the probabilities  add  the probability of the union of a bunch of disjoint events is the sum of the probabilities of constituent events. If you want to think about this pictorially, and just draw a big box, denoting everything that could happen omega, and then these SIs just these  [inaudible] that don't overlap. So S1, S2, S3, and so on. Now the sum or probabilities of this joint events can sum to, at most, 1, right? The probability of all of omega is 1, and these SIs have not overlap and are packed into omega, so the sum of their probabilities is gonna be smaller. We're adding up formally. We have that the sum of the probabilities. Which we can lower bound by the number of different events. And remember there are T different min cuts for some parameter T. For each min cut (Ai, Bi), a lower bound of the probability that, that could spit out as output is 1/(N choose 2). So a lower bound on the sum of all of these probabilities is the number of them, T times the probability lower bound, 1/(N choose 2), and this has got to be at most 1. Rearranging, what do we find? T, the number of different mid-cuts, is bounded above by N choose 2. Exactly the lower bound provided by the N cycle. The N cycle has N choose 2 distinct minimum cuts. No other graph has more. Every graph has only a polynomial number indeed, at most a quadratic number of minimum cuts.

 

Read More

Data Structure

Do you know when and how to use basic data structures is an essential skill for the serious programmer. Data structures are used in pretty much every major piece of software. So let me remind you of what's the point, the raison d??tre of the data structure? Its job is to organize data in a way that you can access it quickly and usefully. There's many, many examples of data structures and hopefully you've seen a few of them and perhaps even used a few of them in your own programs. And they range from very simple examples like lists, stacks and queues to more intricate but still very useful ones like heaps , search trees, hash tables.

Relatives thereof like balloon filters. Union find structures and so on. So why do we have such a laundry list of data structures? Why is there such a bewildering assortment? It's because different data structures support different sets of operations and are therefore well suited for different types of tasks. Let me remind you of a concrete example that we saw back when we were discussing graph search. In particular, breadth first search and depth first search. So we discussed how implementing breadth first search the right data structure to use was a Q. This is something that supports fast, meaning constant time insertion to the back, And constant time deletion from the front. Depth first search by contrast is a different algorithm with different needs. And because of its recursive nature, a stack is much more appropriate for depth first search. That's because it supports constant time deletion from the front, But constant time insertion to the front. So the last in first out support of a stack is good for depth first search. The first in first out operations of a queue work for breadth first search, Now because different data structures are suitable for different types of tasks you should learn the pros and cons of the basic ones. Generally speaking the fewer operations that a data structure supports the faster the operations will be. And the smaller the space overhead require by the data structure. Thus, as programmers, it's important that you think carefully about the needs of your application. What are the operations that you need a data structure to export? And then you should choose the right data structure, meaning the one that supports all of the operations you need. But ideally no superfluous ones.

Let me suggest four levels of data structure knowledge that someone might have, So level zero is the level of ignorance, for someone who has never heard of a data structure, And is unaware of the fact that organizing your data can produce fundamentally better software. For example, fundamentally faster algorithms, Level one I think of as being cocktail party level awareness. Now obviously, here I'm talking only about the nerdiest of cocktail parties. But nonetheless, this would be someone who could at least hold a conversation about basic data structures. They've heard of things like heaps and binary search trees, they're perhaps aware of some of the basic operations, but this person would be shaky using them in their own program or say in a technical interview context. Now, with level two, we're starting to get somewhere. So here I would put someone who has solid literacy about data structures. They're comfortable using them as a client in their own programs, and they have a good sense of which data structures are appropriate for which types of tasks. Now level three, the final level, is the hardcore programmers and computer scientists. And these are people who are not content to just be a client of data structures, and use them in their own programs, but they actually have an understanding of the guts of these data structures. How they are coded up, how they're implemented, not merely how they are used. Now my guess is that, really a large number of you will wind up using data structures in your own programs, and therefore, learning about what are the operations of different data structures and what are they good for, will be a quite empowering skill for you as a programmer. On the other hand, I'll bet that very few of you will wind up having to implement your own data structures from scratch, as opposed to just using as a client the data structures that already come with the various standard programming libraries. So with this in mind I'm going to focus my teaching on taking up to level two. My discussion gonna focus on the operations reported by various data structures and some of canonical applications. So through this I hope I'll develop your intuition for what kinds of data structures are suitable for what kinds of tasks. Time permitting, however, I also want to include some optional material for those of you wanting to take it to the next level and learn some about the guts of these data structure, the canonical limitations of how you code them up.

Read More

Merge Sort (overview)

so for example, three other sorting algorithms that you may know about, Let's start with three sorting algorithms which are perhaps simpler, first of all is "Selection Sort". So this is where you do a number of passes through the way repeatedly, identifying the minimum of the elements that you haven't looked at yet, so you're basically a linear number of passes each time doing a minimum computation. There's "Insertion Sort", which is still useful in certain cases in practice as we will discuss, but again it's generally not as good as Merge Sort, where you will repeatedly maintain the invariant that prefix view of array, which is sorted version of those elements. So after ten loops of Insertion Sort, you'll have the invariant that whatever the first ten elements of the array are going to be in sorted order, and then when Insertion Sort completes, you'll have an entire sorted array. Finally, some of you may know about "Bubble Sort", which is where you identify adjacent pairs of elements which are out of order, ... and then you do repeated swaps until in the end the array is completely sorted. Again I just say this to jog your memory, these are simpler sorts than Merge Sort, but all of them are worse in the sense that they're lack in performance in general, which scales with N^2, and the input array has N elements, so they all have, in some sense, quadratic running time. But if we use this non-trivial Divide-and-Conquer approach, or non-obvious approach, we'll get a, as we'll see, a much better running time than this quadratic dependence on the input. Okay? So we'll get a win, first sorting in Divide-and-Conquer, and Merge Sort is the algorithm that realizes that benefit. So the second reason that I wanna start out by talking about the Merge Sort algorithm, is to help you calibrate your preparation. I think the discussion we're about to have will give you a good signal for whether you're background's at about the right level, of the audience that I'm thinking about for this course. So in particular, when I describe the Merge Sort algorithm, you'll notice that I'm not going to describe in a level of detail that you can just translate it line by line into a working program in some programming language. My assumption again is that you're a sort of the programmer, and you can take the high-level idea of the algorithm, how it works, and you're perfectly capable of turning that into a working program in whatever language you see fit. So hopefully, I don't know, it may not be easy the analysis of Merge Sort discussion. But I hope that you find it at least relatively straight forward, because as the course moves on, we're going to be discussing algorithms and analysis which are a bit more complicated than the one we're about to do with Merge Sort. So in other words, I think that this would be a good warm-up for what's to come. Now another reason I want to discuss Merge Sort is that our analysis of it will naturally segment discussion of how we analyze the algorithms in this course and in general. So we're going to expose a couple of assumptions in our analysis, we're focus on worst case behavior, or we'll look for guarantees on performance on running time that hold for every possible input on a given size, and then we'll also expose our focus on so called "Asymptotic Analysis", which meaning will be much more concerned with the rate of growth on an algorithms performance than on things like low-order terms or on small changes in the constant factors. Finally, we'll do the analysis of Merge Sort using what's called as "Recursion-Tree" method. So this is a way of tying up the total number of operations that are executed by an algorithm. And as we'll see a little bit later, this Recursion-Tree method generalizes greatly. And it will allow us to analyze lots of different recursive algorithms, lots of different Divide-and-Conquer algorithms, including the integer multiplication algorithm that we discussed in an earlier segment. So those are the reasons to start out with Merge Sort.

So what is the computational problem that Merge Sort is meant to solve? Well, presumably, you all know about the sorting problem. But let me tell you a little bit about it anyways, just so that we're all on the same page. So, we're given as input. An array of N numbers in arbitrary order, and the goal of course is to produce output array where the numbers are in sorted order, let's say, from smallest to largest. Okay so, for example, we could consider the following input array, and then the goal would be to produce the following output array. Now one quick comment. You'll notice that here in input array, it had eight elements, all of them were distinct, it was the different integers, between 1 and 8. Now the sorting problem really isn't any harder if you have duplicates, in fact it can even be easier but to keep the discussion as simple as possible let's just, among friends, go ahead and assume that they're distinct, for the purpose of this lecture. And I'll leave it as an exercise which I encourage you to do, which is to think about how the Merge Sort algorithm implementation and analysis would be different, if at all, if there were ties, okay? Go ahead and make the distinct assumption for simplicity from here on out. Okay, so before I write down any pseudo code for Merge Sort, let me just show you how the algorithm works using a picture, and I think it'll be pretty clear what the code would be, even just given a single example.

So let's go ahead and consider the same unsorted input array that we had on the previous slide. So the Merge Sort algorithm is a recursive algorithm, and again, that means that a program which calls itself and it calls itself on smaller sub problems of the same form, okay? So the Merge Sort is its purpose in life is to sort the given input array. So it's going to spawn, or call itself on smaller arrays. And this is gonna be a canonical Divide-and-Conquer application, where we simply take the input array, we split it in half, we solve the left half recursively, we solve the right half recursively, and then we combine the results. So let's look at that in the picture. So the first recursive call gets the first four elements, the left half of the array, namely 5, 4, 1, 8. And, of course, the other recursive call is gonna get the rest of the elements, 7, 2, 6, 3. You can imagine these has been copied into new arrays before they're given to the recursive calls. Now, by the magic of recursion, or by induction if you like, the recursive calls will do their task. They will correctly sort each of these arrays of four elements, and we'll get back sorted versions of them. So from our first recursive call, we receive the output, 1, 4, 5, 8, and from the second recursive call, we received the sorted output, 2, 3, 6, 7. So now, all the remains to complete the Merge Sort is to take the two results of our recursive calls, these two sorted elements of length-4, and combine them to produce the final output, namely the sorted array of all eight of the input numbers. And this is the step which is called "Merge". And hopefully you are already are thinking about how you might actually implement this merge in a computationally efficient way. But I do owe you some more details. And I will tell you exactly how the merge is done. In effect, you just walk pointers down each of the two sort of sub-arrays, copying over, populating the output array in the sorted order. But I will give you some more details in just a slide or two. So that's Merge Sort in a picture. Split it in half, solve recursively, and then have some slick merging procedure to combine the two results into a sorted output.

Read More

Algorithm for Counting Inversion

We're gonna start by extending the merge sort algorithm to solve a problem involving counting the number of inversions of an array. Before we tackle the specific problem of counting the number of inversions in an array, let me say a few words about the divide and conquer paradigm in general. So again, you've already seen the totally canonical example of divide and conquer, namely merge sort. So the following three conceptual steps will be familiar to you. The first step, no prizes for guessing is you divide. The problem. Into smaller sub-problems. Sometimes this division happens only in your mind. It's really more of a conceptual step than part of your code. Sometimes you really do copy over parts of the input into say new arrays to pass on to your recursive calls. The second step, again no prizes here, is you conquer the sub-problems just using recursion. So for example, in Merge Sort, you conceptually divide the array into two different pieces. And then you [inaudible] with the conquer or sort to the first half of the array. And you, you do the same thing with the second half of the array. Now of the array. And you, you do the same thing with the second half of the array. problem, and then solving the sub problems recursively. Usually, you have some extra cleanup work after the recursive calls, and to stitch together the solutions to the sub problems into one for the big problem, the problem that you actually care about. Recall, for example, in Merge Sort, after our recursive calls, the left half of the array was sorted, the right half of the array was sorted. But we still had to stitch those together. Merge into a sorted version of the entire array. So the [inaudible] step is to combine. The solutions to the subproblem into one problem. Generally the largest amount of ingenuity happens in the third step. How do you actually quickly combine solutions to subproblems into one to the original problem? Sometimes you also get some cleverness in the first step with division. Sometimes it's as simple as just spliting a ray in two. But there are cases where the division step also has some ingenuity. Now let's move on to the specific problem of counting inversions and see how to apply this divide and conquer paradygm. So let begin by defining the problem formally now. We're given as input an array A with a length N. And you can define the problem so that the array a contains any ole distinct numbers. But, let's just keep thing simple and assume that it contains the numbers one through n. The integers in that range in some order. That captures the essence of the problem. And the goal is to compute the number of inversions of this array so what's an inversion you may ask well an inversion is just a pair of array [inaudible] I and J with I smaller than J so that earlier array entry the I entry is bigger than the latter one the Jake one so one thing that should be evident is that if the array contains these numbers in sorted order if the array is simply one two three four all the way up to N then the number of inversions is zero. The converse you might also want to think through if the array has any other ordering of the numbers between one and N other than the assorted one, then it's going to have a non. Of zero number of inversions.

Read More

Why Study Algorithm

algorithm is a well defined set of rules, a recipe, in effect, for solving some kind of computational problem. So for example, maybe you're given a bunch of numbers and you want to rearrange them into sorted order. Maybe you're given a road network with an origin and a destination, and you want to compute the shortest path from point A to point B. Maybe you're given a bunch of tasks with deadlines, and you want to know whether or not it's feasible to accomplish all of those tasks by the respective deadlines. So, why study algorithms? Well first of all, understanding the field of algorithms and also the related field of data structures, is crucial for doing serious work in pretty much any other branch of computer science. examples here, and let me just state one super obvious one, which is that search engines use a tapestry of algorithms to efficiently compute the relevance of various webpages. The most famous such algorithm which you may have heard of is the PageRank algorithm, in use by Google, indeed. In a December 2010 report to the United States White House, the President Council of Advisors on Science and Technology argued that, "in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed", as you'd be familiar with in the form of Moore's Law. Third, although this is getting significantly outside the scope of this course, algorithms are increasingly being used to provide a novel lens on processes outside of computer science and technology. For example, the study of quantum computation has provided a new and computational view point on quantum mechanics. Price fluctuations in economic markets can be fruitfully viewed as an algorithmic process. And even evolution can be usefully thought of as a surprisingly effective search algorithm. to both of them. Now, I don't know about you, but back when I was a student, my avorite classes were always challenging classes. But, after I struggled through them I somehow felt like I had a few more IQ points than when I started. So, I hope his course provides a similar experience for many of you: that, on the one hand, it's a bit of a struggle -- you find the concepts challenging, but perhaps you feel just a, a tinge smarter after we're done. it is addictive. So let's now descend from these lofty generalities and get much more concrete. And also, let's remember that we've all been learning and using algorithms since we were little kids. So once upon a time, in roughly 3rd grade or so, you learned how to multiple two numbers The last two reasons I'm gonna give you might sound a little flippant, but, I think there's more than a grain of truth now you probably weren't thinking in these terms at the time, but multiplying two numbers is certainly a well defined computational problem, and that procedure you learned back in 3rd grade or so is indeed an algorithm. So let's just make that a little bit more precise. In this computational problem we're given as input two numbers, let's say, with N digits. And to make things interesting, why don't you think about n as being really quite large, say, in the thousands. Maybe we're implementing an algorithm that's going to be used in a cryptography application, where you need to keep track of really quite large numbers. So if we call the two infinite numbers X and Y, the problem is simply to compute their products X times Y. So a quick digression, I'll certainly be the first to admit that my handwriting is not the greatest. I got a C in penmanship back in elementary school, and I think the teacher was being, a little generous. But, you know, it's an acquired taste but trust me, integer multiplication. Now, when we talk about procedures for multiplying two numbers, we're gonna be interested in ounting how many steps are required in order to execute, the multiplication. So how do we count a step? We'll talk more about this later, but for multiplying two numbers, let's just call a step the addition or multiplication of two single-digit numbers. So let's review the integer multiplication algorithm that we learned back in grade school just by working through a concrete example. Specifically,let's think of n = 4, so let's look at two 4-digit numbers. Let's say 5,6, 7, 8. And 1, 2, 3, 4. [sound of door closing] Now as you'll recall, the procedure we learned way back when was just to take each digit at the bottom number, and multiply it by each of the top numbers. And then to take each of those, N partial products, and add them up. So, for example, you start with the 4, you multiple it by 8, you get 32, carry the 3. 4 times 7 is 28, add the 3, you get 1. Carry the 3, and so on. So that gives you this first partial product, 22712. Then you do a shift, so you effectively put a 0 in this final digit, and you repeat that procedure using the next digit, the 3. So again, 3 times 8 is 4, carry the 2, and so on. And you can compute the final two partial products using the 2 and the 1. And having computed all of the partial products, you just add them up to get the final product. Now, the question I'm interested in, is: how much work, how many primitive operations did we do to multiply these two numbers and, more generally, how many does it require to multiply to N-digit numbers as a function of N? Well, just to get sort of a ballpark viewpoint for what's going on, we started with two N-digit numbers. And at the end of the day, we basically filled out a grid of size roughly N by N, give-and-take a little bit. So just in ballpark terms, it seems that multiplying two N-digit numbers require essentially a quadratic number of operations, a small number of operations to fill each entry in this grid. The grid is N by N roughly. So that's roughly N^2 operations. And a little more detail, we can look at each of the partial product separately. So, to compute say this first partial product,what did we do? We took the four, we multiplied it by each of the N digits on top. We also did some carries, so that affects things a little bit. But in the end, we did somewhere between say N and 2N, primitive operations to compute this first partial product. And that's true, of course, for each of the N partial products.So that's roughly N operations for each of the N partial products. So that's roughly N^2 operations to compute all of the partial products. Then we have to add it all up at the end, but that takes just an extra number of constant times n primitive operations to do all of those additions. So summarizing, overall, the number of primitive operations required to multiply two N-digit numbers using this procedure grows quadratically with the length N. So, for example, if you double the length of two numbers, you expect to do roughly four times as many primitive operations,if you use this iterative algorithm for multiplying two numbers. Now, depending on what type of 3rd grader you were, you might well have accepted this procedure as being the unique, or at least the optimal way of multiplying to N-digit numbers together. And if you wanna be an exponent algorithm designer, that kind of obedient attitude is something you're gonna have to learn to discard. Here's a favorite quote of mine. It's from a quite early textbook in the field, The Design and Analysis of Computer Algorithms by Aho, Hopcroft and Ullman. And after highlighting a number of algorithmic design techniques, they conclude by saying, "perhaps the most important principle for the good algorithm designer is to refuse to be content". So that's a beautifully accurate quote. I might rephrase it more succinctly by just saying, "if you want to be a good algorithm designer, you should adopt the following mantra: You should always be asking "can we do better?"". This is a particularly appropriate question to ask when you're faced with some kind of naive or obvious algorithm for solving a problem, like the 3rd grade algorithm for integer multiplication. This will come up over and over again. We'll see an algorithm, there will be an obvious solution but, with some extra algorithmic ingenuity, by detecting subtle structure in the problem, we'll be able to do significantly qualitatively better than the naive or obvious solution to the problem. So let's apply this cocky attitude to the problem of multiplying two integers. Let's just suppose, as a working hypothesis, that there is some procedure which is better than what we learned back in elementary school. What could it possibly look like? Well, as someone with some programming experience, you know that there are not only iterative algorithms, iterative programs, like the one we just outlined for integer multiplication. But there are also recursive programs. These are programs that call themselves typically, on an input of a similar form but with smaller size.So as a working hypothesis, let's imagine that there's some interesting recursive approach to multiplying two integers. What must such an algorithm look like? Well it must somehow fundamentally involve calling itself on smaller problems, that is, on smaller numbers, numbers with fewer digits. So what kind of decomposition on numbers could be used to enable this kind of recursive approach. Well, if you think about it, there's a pretty natural way to break a number with a bunch of digits into a couple numbers with fewer digits. Namely, just take the first half of the digits, the first N/2 digits, regard that as a number in its own array. And the second half of the digits, regard that as a number in its own array. So perhaps this decomposition will have some use in enabling a recursive attack on how to multiply two integers. ok sometimes you have interesting algorithmic ideas for which it's totally not obvious what kinds of properties, or what kind of performance guarantees those algorithms enjoy. So in particular, confronted with these three different integer multiplication algorithms, how can we NOT wonder which of the three is the best? Which of these requires the fewest number recursive operations to multiply two integers? In particular, does one of these novel recursive approaches do better than the algorithm we learned back in elementary school? The answer to that question is totally non-obvious and it requires non-trivial mathematical analysis to answer. In the upcoming lectures I'll provide you with the tools to not only precisely understand and answer this question but more generally to predict the running times of an entire genre of divide-and-conquer algorithms. ok for this time maybe its enough see you next time :)))

Read More