W&L Computer Science Wiki - courses:cs211:winter2018:journals:holmesr

ch._4_front_matter

Anonymous (anonymous@undisclosed.example.com) — 2018-02-27T02:05:39+00:00

Chapter 4 Front Matter Right off the bat, the authors state that defining a greedy algorithm is exceedingly difficult. A greedy algorithm is characterized by the way that it creates a solution to a problem, which is building up a solution in small steps which select a local maximum of a certain aspect of the inputs. Interestingly, this implies about the original problem that there is a rule that governs local decisions which helps make the optimal solution to the problem.

home

Anonymous (anonymous@undisclosed.example.com) — 2018-04-02T15:26:29+00:00

Bancks' Wiki * Preface * Section 1.1 * Section 2.1 * Section 2.2 * Section 2.3 * Section 2.4 * Section 2.5 * Section 3.1 * Section 3.2 * Section 3.3 * Section 3.4 * Section 3.5 * Section 3.6 * Ch. 4 Front Matter * Section 4.1 * Section 4.2 * Section 4.4 * Section 4.5 * Section 4.6 * Section 4.7 * Section 4.8 * Section 5.1 * Section 5.2 * Section 5.3 * Ch 6 Front Matter and 6.1 * Section 6.2 * Section 6.3 * Section 7.1 * Section 7.2 * S…

preface

Anonymous (anonymous@undisclosed.example.com) — 2018-01-19T13:55:44+00:00

First Two Pages of Preface This section is an introduction and explanation of why the study and analysis of algorithms is important. Algorithms can be used to model many situations and processes in the natural world, although it is often not immediately obvious in what way they are able to do this. The author suggests two

section_1.1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-21T17:37:10+00:00

Chapter 1 Section 1.1 Section 1.1 deals with the Stable Matching Problem. The algorithm that solves this problem can be used for a variety of different applications, including matching residents with hospitals, job candidates with jobs, or freshman girls with sororities. We will talk about it in terms of matching men and women in monogamous, heteronormative relationships.

section_2.1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-29T19:21:17+00:00

Chapter 2 Section 2.1 Computational Tractability The first attempt to describe efficiency is that “an algorithm is efficient if, when implemented, it runs quickly on real input instances.” This is good, but it fails to address on what type of machine the algorithm is being run, how well it runs, and the scalability it possesses.

section_2.2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-21T00:58:59+00:00

Section 2.2 Asymptotic Order of Growth An algorithm's worst-case running time can be tested quantitatively by computing its algorithmic upper and lower bounds. To prove that an algorithm has an asymptotic upper bound of n2 we can imagine one whose worst-case running time T(n) is f(n) = pn

section_2.3

Anonymous (anonymous@undisclosed.example.com) — 2018-01-21T17:31:33+00:00

Section 2.3 Implementing the G-S Algorithm Analytically, we have found that the Gale-Shapley stable matching algorithm can run in O(n2) time. This is the result of the loop that drives the progress of the algorithm running in O(n2) time, which means that each step within the loop must run in constant time. Our task, then, is to determine which data structures to implement in order to support this constant time execution of steps within the loop.

section_2.4

Anonymous (anonymous@undisclosed.example.com) — 2018-01-29T04:08:41+00:00

Section 2.4 A Survey or Common Running Times The first common running time treated in this section is O(n) running time. This is sometimes described as a “Linear” running time because the running increases linearly, or at the same rate as the input size. Common causes of a linear running time are loops that iterate through every item in an input or algorithms that apply a constant number of processes to each item in an input. Some examples of linear running times include finding the maximum val…

section_2.5

Anonymous (anonymous@undisclosed.example.com) — 2018-01-29T19:20:38+00:00

Section 2.5 Priority Queues Statement 2.11 from the book says that “a sequence of O(n) priority queue operations can be used to sort a set of n numbers”. This is because the set of numbers can be inserted into it with their value as their priority and then extracted in order of priority, resulting in their being in sorted order. I wondered when reading this, then, why we can not come up with a linear sort algorithm? I know I must be missing something but why is this not a linear sort?

section_3.1

Anonymous (anonymous@undisclosed.example.com) — 2018-02-06T04:53:07+00:00

Chapter 3 Section 3.1 Definitions and Applications for graphs A graph is a structure that represents relationships between two elements. They consists of nodes or vertices V and edges E which join the nodes to one another. An edge can be represented as a two-element subset of

section_3.2

Anonymous (anonymous@undisclosed.example.com) — 2018-02-05T19:30:17+00:00

Section 3.2 Graph Connectivity and Traversal Breadth-First Search is a method of search through a graph to assemble the connected component. It does this by adding a “layer,” or the set of nodes connected to the root node s, and then recursively calling itself on each node in the layer. A few interesting properties of the breadth-first search and its resultant tree are that for any nodes

section_3.3

Anonymous (anonymous@undisclosed.example.com) — 2018-02-06T03:41:21+00:00

Section 3.3 Implementing Graph Traversal Using Queues and Stacks Breadth-First Search and Depth-First search often produce quite different trees, but their mechanics are very similar and in fact their essential difference is one's using a queue versus the other's using a stack.

section_3.4

Anonymous (anonymous@undisclosed.example.com) — 2018-02-06T03:57:06+00:00

Section 3.4 Testing Bipartiteness: an Application of BFS A bipartite graph is one that can be separated into two sets such that every edge has one edge in X and the other in Y. This can be represented by a BFS tree by labelling all the odd layers as the layers which contain nodes in the X partition and the even layers contain nodes in the Y partition. Then it is easy to see that there can not be an edge that begins and ends in the same layer, and by the definition of a BFS, there can not be an …

section_3.5

Anonymous (anonymous@undisclosed.example.com) — 2018-02-06T04:37:01+00:00

Section 3.5 Connectivity in Directed Graphs First, directed graphs require two adjacency lists in order to be properly represented since an edge may go from node u to node v but not return from v to u. One lists represents the edges that leave a node and the nodes that those edges connect to, and the other list represents the edges which lead to a node and from which node they come. They are called the

section_3.6

Anonymous (anonymous@undisclosed.example.com) — 2018-02-06T04:52:52+00:00

Section 3.6 DAGS and Topological Orderings A Directed Acyclic Graph (DAG) is just what it sounds like, a directed graph containing no cycles. These are useful for representing precedence relations and dependencies because they don't contain cycles. A cycle in a dependency relation would mean that one process could not start until another had taken place, which would never happen because none could start first.

section_4.1

Anonymous (anonymous@undisclosed.example.com) — 2018-04-19T20:08:30+00:00

Chapter 4 Chapter 4 Front Matter Right off the bat, the authors state that defining a greedy algorithm is exceedingly difficult. A greedy algorithm is characterized by the way that it creates a solution to a problem, which is building up a solution in small steps which select a local maximum of a certain aspect of the inputs. Interestingly, this implies about the original problem that there is a rule that governs local decisions which helps make the optimal solution to the problem.

section_4.2

Anonymous (anonymous@undisclosed.example.com) — 2018-02-27T04:07:52+00:00

Section 4.2 Scheduling to Minimize Lateness: an Exchange Argument This problem gives a set of requests which all may begin at time s and must use the resource for a specific interval of time. The difference from the previous problem is that instead of a start and end time, these requests only come with a deadline before which they must be completed. These criteria allow us a few possible rules by which we may define the greedy algorithm.

section_4.5

Anonymous (anonymous@undisclosed.example.com) — 2018-03-05T03:55:49+00:00

Section 4.5 The Minimum Spanning Tree Problem A minimum spanning tree is a tree that includes the smallest subset of edges that connect all the edges in the original graph. Additionally, in order to determine the minimum spanning tree of a graph all the edges in the graph must be strictly greater than zero and of distinct lengths.

section_4.6

Anonymous (anonymous@undisclosed.example.com) — 2018-03-06T02:38:20+00:00

Section 4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure Kruskal's Algorithm requires a way to rapidly identify the connected components to which two nodes on either end of an edge belong. This requirement is met by a data structure called the Union-Find Data Structure. This data structure supports three operations: MakeUnionFind(S) which returns a Union-Find data structure on the set S where each element is in its own set, Find(u) which returns the name of the set containing…

section_4.7

Anonymous (anonymous@undisclosed.example.com) — 2018-03-06T03:58:11+00:00

Section 4.7 Clustering Clustering problems revolves around classifying objects into groups based on their distance from one another. For some collections of items, this distance can be physical but for many others, the distance is a measure of similarity for which a distance function must be defined. The idea of a clustering is that items more like each other will be in the same cluster, while items less like each other will be in disparate clusters. The trouble is finding an efficient way to p…

section_4.8

Anonymous (anonymous@undisclosed.example.com) — 2018-03-13T15:46:16+00:00

Section 4.8 Huffman Codes and Data Compression This section begins by discussing different ways which one may encode data. One example discussed is the scheme using 1's and 0's which allows one to encode 2b symbols using b bits. Another scheme is one such as Morse Code, which uses different lengths of strings to encode different characters, based on frequency. Letters that occur more frequently, such as e, t, and a, use one- or two-bit strings while less frequent letters use four or five bit st…

section_5.0

Anonymous (anonymous@undisclosed.example.com) — 2018-03-14T03:50:05+00:00

Chapter 5 Divide and Conquer algorithms Section 5.1 The Mergesort Algorithm The mergesort algorithm with which we are all familiar provides an excellent opportunity to study recurrence relations. As with many divide-and-conquer algorithms, the behvior of mergesort can be described with a template such as: divide the input into two equally-sized pieces, recursively solve those pieces and then recombine the results into an overall solution. For mergesort, as with many algorithms of this nature, …

section_5.1

Anonymous (anonymous@undisclosed.example.com) — 2018-03-14T02:06:54+00:00

Section 5.1 The Mergesort Algorithm The mergesort algorithm with which we are all familiar provides an excellent opportunity to study recurrence relations. As with many divide-and-conquer algorithms, the behvior of mergesort can be described with a template such as: divide the input into two equally-sized pieces, recursively solve those pieces and then recombine the results into an overall solution. For mergesort, as with many algorithms of this nature, it will

section_5.2

Anonymous (anonymous@undisclosed.example.com) — 2018-03-14T03:07:40+00:00

Section 5.2 Further Recurrence Relations This section explores a more general version of recurrence problem than the previous one did. This type of recurrence creates recursive calls on q subproblems of size n/2. Mergesort uses q = 2, but can in fact be 1 or >2. Generalizing the inequality from the previous section gives us: T(n)

section_5.3

Anonymous (anonymous@undisclosed.example.com) — 2018-03-14T03:48:44+00:00

Section 5.3 Counting Inversions The motivation for this type of problem is based in the analysis of a set of rankings compared to a different set of rankings of the same items. A way to compare these sets of ordered items is to look at how many pairs are

section_6.0

Anonymous (anonymous@undisclosed.example.com) — 2018-03-27T16:02:32+00:00

Chapter 6: Dynamic Programming Chapter 6 Front Matter and Section 6.1: Weighted Interval Scheduling, a Recursive Approach The basic idea behind dynamic programming is similar to that of divide and conquer and opposite to that of greedy: dynamic programming divides the problem into subproblems and then takes the solutions to those to create the solution to the larger problem. This leads us to think that the dynamic programming approach may reach up to the brute force search time, however we wil…

section_6.1

Anonymous (anonymous@undisclosed.example.com) — 2018-03-27T03:34:20+00:00

Chapter 6 Front Matter and Section 6.1: Weighted Interval Scheduling, a Recursive Approach The basic idea behind dynamic programming is similar to that of divide and conquer and opposite to that of greedy: dynamic programming divides the problem into subproblems and then takes the solutions to those to create the solution to the larger problem. This leads us to think that the dynamic programming approach may reach up to the brute force search time, however we will never actually need to examine…

section_6.2

Anonymous (anonymous@undisclosed.example.com) — 2018-03-27T04:23:33+00:00

6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems The iterative version of the algorithm works by directly computing the entries in M rather than relying on the memoized recursion present in the recursive version. This algorithm works by iterating though the n items and computing each ones value, which is then stored directly in the array. It is easy to see that the algorithm then has linear running time since it will execute a constant time operation on each of i…

section_6.3

Anonymous (anonymous@undisclosed.example.com) — 2018-03-27T16:00:26+00:00

6.3 Segmented Least Squares: Multi-way Choices What we will call the error of a line of best fit is the sum of each point's distance from the line. It is relatively easy to place such a line and calculate its error when all the points seem to fit around one line, but sometimes the points in a data set can look like they fit on a sequence of two or more lines. This makes us want to find a way to allow the algorithm to fit a set of lines to the data points. We cannot allow it to fit an arbitraril…

section_7.1

Anonymous (anonymous@undisclosed.example.com) — 2018-04-03T03:37:51+00:00

Section 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm To begin our discussion of the Maximum-Flow problem and the Ford-Fulkerson algorithm (FF), we must first lay down some terminology. The network on which we will be measuring flow can be represented as a graph with nodes and edges. Each edge e has a non-negative capacity, which will be referred to as c

section_7.2

Anonymous (anonymous@undisclosed.example.com) — 2018-04-04T01:07:43+00:00

Section 7.2 Maximum Flows and Minimum Cuts in a Network The next objective is to prove that the FF algorithm returns the best possible flow in G. One of the important concepts that will help us towards this goal is considering a cut and how it can place upper-bounds on the maximum-value flow. We can start off by noticing that the amount of flow leaving the cut minus the flow that comes back into the cut is the total volume of flow from the cut. In the case that the cut contains s, then this wil…

section_7.5

Anonymous (anonymous@undisclosed.example.com) — 2018-04-04T03:22:57+00:00

Section 7.5 a First Application: the Bipartite Matching Problem We can compute a maximum matching in a set of nodes G by adding an s and a t node, then computing the maximum s-t flow in our new graph G'. This means that not only can we find the size of this matching but actually use the flow to find the matching itself.

section_7.7

Anonymous (anonymous@undisclosed.example.com) — 2018-04-04T14:37:45+00:00

Section 7.7 Extensions to the Maximum Flow Problem Circulations with demands This problem changes what we have been talking about by adding multiple sources and sinks. Instead of maximizing the flow value, we will have sources with fixed supply values and sources with fixed demand values. Here we want to satisfy all demand with all our supply instead of maximizing some value. The demand of a node can be greater than, equal to, or less than zero. If demand is greater than supply, the node is a …

sidebar

Anonymous (anonymous@undisclosed.example.com) — 2018-04-02T15:25:07+00:00

Bancks' Wiki * Preface * Chapter 1 * Chapter 2 * Chapter 3 * Chapter 4 * Chapter 5 * Chapter 6 * Chapter 7 ---- <- Bancks' Wiki <- CSCI 211: Algorithm Design and Analysis