Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:suraj:home [2012/01/23 00:32] – bajracharyas | courses:cs211:winter2012:journals:suraj:home [2012/01/31 17:59] (current) – bajracharyas | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | [[: | + | ====== |
| - | ====== | + | |
| - | __**PREFACE**__ | ||
| - | The preface talks about algorithms and its importance, goal of the book, target readers, what the book contains as a whole, problems and solutions in the book, a chapter-by-chapter synopsis of the book, a guidance on how the book is to be used, and acknowledgments. Algorithms are the basis of Computer Science because it helps us in simple matters as addition of numbers to the harder ones as loops, recursion or search with step-by-step methods of dealing with them. The goal of the book, according to the preface, is "to offer advice on how to identify clean algorithmic problem formulations in complex issues from different areas of computing and, from this, how to design efficient algorithms for the resulting problems" | ||
| - | |||
| - | **--------------------------------------------------------------------------------------------------------------------------------------** | ||
| - | **--------------------------------------------------------------------------------------------------------------------------------------** | ||
| - | |||
| - | __**CHAPTER 1: INTRODUCTION: | ||
| - | |||
| - | This chapter consists of 6 different problems, namely Stable Matching, Interval Scheduling, Weighted Interval Scheduling, Bipartite Matching, Independent Set and Competitive Facility Location. There is a detailed explanation about Stable Matching, with its history, examples, design of its algorithm, its analysis, extensions and proofs. For the rest, the chapter provides information on how these problems are to be dealt with. | ||
| - | |||
| - | __**Stable Matching**__ | ||
| - | |||
| - | David Gale and Lloyd Shapley, two mathematical economists designed the Stable Matching Problem in 1962, to design a self-enforcing matching algorithm to match elements of Set X with elements of Set Y depending on their preferences and limits. The book gives an example of one such Stable Matching Problem: a set of men to be matched with a set of equal number of women to get married to. | ||
| - | |||
| - | __Algorithm__ | ||
| - | |||
| - | * Set all Men(M) and Women(W) to be free | ||
| - | * While there exists a Man who is free and hasn't proposed all Women | ||
| - | * Choose such a man, m | ||
| - | * Let w be the highest preferred woman in m's list of preferred women to whom m hasn't proposed yet | ||
| - | * If w is free | ||
| - | * m and w are engaged | ||
| - | * Else if w is engaged to m' | ||
| - | * If w prefers m' to m | ||
| - | * m is still free | ||
| - | * Else if w prefers m to m' | ||
| - | * m and w are engaged | ||
| - | * m' becomes free | ||
| - | * End if | ||
| - | * End if | ||
| - | * Return the set of paired m and w | ||
| - | |||
| - | __Analysis__ | ||
| - | |||
| - | * w gets engaged from the moment she receives a proposal and her partner only keeps getting better, but not worse in terms of her preference | ||
| - | * It is reversed for m, i.e. his partner keeps getting worse in terms of his preference | ||
| - | * Since at most, each m proposes each w only once, the algorithm has an upper bound order of n^2 | ||
| - | * If m is free at any point, then there should be a w to whom he hasn't proposed yet. This is because there are the same number of w as m | ||
| - | * The set returned at the end is a perfect matching | ||
| - | * Every execution returns the same set (Need help) | ||
| - | * In Stable Matching S*, each w is paired with her worst valid m (Need help) | ||
| - | |||
| - | __**Interval Scheduling**__ | ||
| - | |||
| - | The goal of this problem is to maximize the number of requests for a resource which can be used by a single person at a time. For this, we say a set of requests are compatible if no two requested intervals do not overlap. Out of all these compatible sets, we choose the one with the maximum size. This is an example of " | ||
| - | |||
| - | __**Weighted Interval Scheduling**__ | ||
| - | |||
| - | This is almost the same as Interval Scheduling, except that each task has a weight, or a value assigned to it. For example, if task 1 has a higher weight over all other tasks, task 1 has to be included in the optimal solution. For this, we use a technique called " | ||
| - | |||
| - | __**Bipartite Matching**__ | ||
| - | |||
| - | In the Stable Matching problem, if any m does not want to marry at least one of w, Bipartite Matching problem occurs. This problem can be solved by a method known as " | ||
| - | |||
| - | __**Independent Set**__ | ||
| - | |||
| - | It is a more general way of defining a Stable Matching or a Bipartite Matching problems. For example, this problem helps you solve your problem of inviting a group of friends for a party such that there is no tension between any of them in the party because of any one of them not getting along with any of the rest. This problem has no known efficient algorithm and the only way to solve this problem is by brute force and trying out each subsets. This is an example of an " | ||
| - | |||
| - | __**Competitive Facility Location**__ | ||
| - | |||
| - | This problem is like a game played by two franchises trying to maximize their output by selecting different locations available, turn by turn, with rules that each of them cannot be too close to each other. This is an example of " | ||
| - | |||
| - | **--------------------------------------------------------------------------------------------------------------------------------------** | ||
| - | **--------------------------------------------------------------------------------------------------------------------------------------** | ||
| - | |||
| - | __**CHAPTER 2: BASICS OF ALGORITHM ANALYSIS**__ | ||
| - | |||
| - | This chapter talks about efficiency of algorithms. Not all algorithms are efficient in terms of their memory usage and speed. "Even bad algorithms can run quickly when applied to small test cases on extremely fast processors; even good algorithms can run slowly when they are coded sloppily." | ||
| - | |||
| - | __**Computer Tractability**__ | ||
| - | |||
| - | __Worst-Case Run Time Vs. Brute-Force Search__ | ||
| - | |||
| - | The worst-case run time for the Stable Matching example in the previous chapter is 2n^2 because there are two lists, M and W, each of size n and we go through each list once. However, there are n! possible perfect matchings and Brute-Force Search is much more bigger. | ||
| - | |||
| - | __NOTE__: In the book, there are some definitions on efficiency and a reason to why the particular definition is a good or a bad one. There is a also a table with run times of different algorithms on inputs of increasing size. | ||
| - | |||
| - | __**Asymptotic Order of Growth**__ | ||
| - | |||
| - | __Asymptotic Upper Bounds__ | ||
| - | |||
| - | Defined as T(n) = O(f(n)), meaning T(n) is O(f(n)) if there exist constants c > 0 and n0 >= 0 so that for all n >= n0, we have T(n) <= c.f(n). | ||
| - | |||
| - | __Asymptotic Lower Bounds__ | ||
| - | |||
| - | Defined as T(n) = Ω(f(n)), meaning T(n) is Ω(f(n)) if there exist constants ε > 0 and n0 >= 0 so that for all n >= n0, we have T(n) >= ε.f(n). | ||
| - | |||
| - | __Asymptotic Tight Bounds__ | ||
| - | |||
| - | Defined as T(n) = Θ(f(n)), if it is both the upper bound and the lower bound, meaning, it is just the right bound. | ||
| - | |||
| - | __Properties of Asymptotic Growth Rates__ | ||
| - | |||
| - | * They are transitive. If f = O(g) and g = O(h), then f = O(h) | ||
| - | * They are summable. If f = O(h) and g = O(h), f + g = O(h) | ||
| - | |||
| - | __Asymptotic Bounds for Some Common Functions__ | ||
| - | |||
| - | * Polynomial: f = O(n^d) | ||
| - | * Logarithms: f = log(b)n = O(n^x) | ||
| - | * Exponentials: | ||
| - | |||
| - | **--------------------------------------------------------------------------------------------------------------------------------------** | ||
| - | **--------------------------------------------------------------------------------------------------------------------------------------** | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
| + | * [[: | ||
