W&L Computer Science Wiki - courses:cs211:winter2014:journals:stephen:home

chapter-1.1

Anonymous (anonymous@undisclosed.example.com) — 2014-01-14T01:28:24+00:00

In 1962, David Gale and Lloyd Shapley asked the question: Could one design a college admissions process, or a job recruiting process, that was self-enforcing? Self-enforcing, in this case, means that a system based on self interest prevents offers from being retracted or rejected and thus causes a stable system. The question ended up being:

chapter-2.1

Anonymous (anonymous@undisclosed.example.com) — 2014-01-14T23:41:21+00:00

This section discusses computational tractability, what efficiency is, and why we have the current methods that we do in order to measure it. The worst-case analysis of an algorithm has been found to do a reasonable job of capturing its efficiency in practice; that is, how long will the algorithm take to run in the worst possible case. This chapter defines an efficient algorithm as one that has a polynomial running time.

chapter-2.2

Anonymous (anonymous@undisclosed.example.com) — 2014-01-15T01:07:08+00:00

This section of chapter two looks to classify running times at a coarser level of granularity than say, the algorithm runs for at most 1.62n^2 + 3.5n + 8 steps. We don't classify efficiency at that level of specificity so that similarities among different algorithms and among different problems show up more clearly.

chapter-2.3

Anonymous (anonymous@undisclosed.example.com) — 2014-01-22T03:10:03+00:00

2.3: Implementing the Stable Matching Algorithm Using Lists and Arrays The runtime of the outside while loop will be at most n^2, but we need to find a way to make all of the other operations within the loop to be O(1) so that the entire algorithm runs at O(n^2) as was shown in chapter 1. In order to do this some cases may involve preprocessing the input to convert it from its given input representation into a data structure that is more appropriate for the problem being resolved.

chapter-2.4

Anonymous (anonymous@undisclosed.example.com) — 2014-01-22T03:43:27+00:00

2.4: A Survey of Common Running Times This chapter looks at different running times of algorithms and cases in which they would be used. It is suggested to look at a new problem by thinking about two kinds of bounds: one on the running time you hope to achieve, and the other on the size of the problem's natural search space - the set of all possible solutions.

chapter-2.5

Anonymous (anonymous@undisclosed.example.com) — 2014-01-22T04:24:55+00:00

2.5: A More Complex Data Structure: Priority Queues One of the book's key focuses is to seek algorithms that improve qualitatively on brute-force search, and the priority queue can help a lot with this. A priority queue is a first in first out collection that allows ordering by priority. This can be useful in real-time events such as the scheduling of processes on a computer. Each process has a priority, but process do not arrive in order of their priorities.

chapter-3.1

Anonymous (anonymous@undisclosed.example.com) — 2014-01-27T23:59:15+00:00

Chapter 3.1: Graphs - Basic Definitions and Applications A graph G is simply a way of encoding pairwise relationships among a set of objects. A directed graph G consists of a set of nodes V and a set of directed edges E. Each e that is an element of E is an ordered pair (u, v); in other words, the roles of u and v are not interchangeable, and we call u the tail of the edge and v the head.

chapter-3.2

Anonymous (anonymous@undisclosed.example.com) — 2014-01-28T23:49:26+00:00

3.2: Graph Connectivity and Graph Traversal Breadth-First Search Breadth-first search adds nodes one “layer” at a time. For each j >= 1, layer L(j) produced by BFS consists of all nodes at distance exactly j from s. There is a path from s to t if and only if t appears in some layer.

chapter-3.3

Anonymous (anonymous@undisclosed.example.com) — 2014-01-29T00:11:22+00:00

3.3: Implementing Graph Traversal Using Queues and Stacks Two basic ways to represent graphs: adjacency matrix and adjacency list. The adjacency matrix representation of a graph requires O(n^2) space, while the adjacency list representation requires only O(m+n).

chapter-3.4

Anonymous (anonymous@undisclosed.example.com) — 2014-02-11T01:37:20+00:00

3.4: Testing Bipartiteness: An Application of Breadth-first Search A bipartite graph is one where the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y. If a graph G is bipartite, then it cannot contain an odd cycle. Note a triangle - 3 nodes all connected. The odd length cycle is 3 and therefore the graph is not bipartite.

chapter-3.5

Anonymous (anonymous@undisclosed.example.com) — 2014-02-11T05:05:13+00:00

3.5: Connectivity in Directed Graphs An example of a directed graph is the world wide web, nodes are pages and edges are hyperlinks. Representing Directed Graphs A directed graph has each node with two lists associated with it: one list consists of nodes to which it has edges, and a second list consists of nodes from which it has edges.

chapter-3.6

Anonymous (anonymous@undisclosed.example.com) — 2014-02-11T05:25:02+00:00

3.6: Directed Acyclic Graphs and Topological Ordering If an undirected graph has no cycles, then it has an extremely simple structure: each of its connected components is a tree. But it is possible for a directed graph to have no directed cycles and still have a very rich structure. If a directed graph has no cycles, it is a

chapter-4.1

Anonymous (anonymous@undisclosed.example.com) — 2014-02-11T16:18:42+00:00

4.1: Interval Scheduling: The Greedy Algorithm Stays Ahead For this problem, we'll say that a subset of the requests is compatible if no two of them overlap in time. Our goal is to accept as large a compatible subset as possible. Compatible sets of maximum size will be called

chapter-4.7

Anonymous (anonymous@undisclosed.example.com) — 2014-03-05T00:58:18+00:00

Chapter 4.7: Clustering Clustering arises whenever one has a collection of objects- say, a set of photographs, documents, or microorganisms - that one is trying to classify or organize into coherent groups. The clustering problem seeks to divide objects into groups so that, intuitively, objects within the same group are

chapter-4.8

Anonymous (anonymous@undisclosed.example.com) — 2014-03-05T01:15:01+00:00

Chapter 4.8: Huffman Codes and Data Compression Data compression has a fundamental problem in the issue of reducing the average number of bits per letter. When large files need to be shipped across communication networks, or stored on hard disks, it;'s important to represent them as compactly as possible.

chapter-4_intro

Anonymous (anonymous@undisclosed.example.com) — 2014-02-11T05:34:39+00:00

Chapter 4: Greedy Algorithms “Greed...is good. Greed is right. Greed works.” - Michael Douglas. An algorithm is greedy if it builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion. When a greedy algorithm succeeds there is a local decision rule that one can use to construct optimal solutions. There are two basic methods that we will follow for proving that a greedy algorithm produces an optimal solution to a problem. One can…

chapter-5.1

Anonymous (anonymous@undisclosed.example.com) — 2014-03-05T01:22:53+00:00

Chapter 5.1: A First Recurrence: The Mergesort Algorithm Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls - using the linear time algorithm for merging sorted lists that we saw in chapter 2.

chapter-5.2

Anonymous (anonymous@undisclosed.example.com) — 2014-03-11T00:31:14+00:00

Chapter 5.2: Further Recurrence Relations There is a more general class of algorithms obtained by considering divide and conquer algorithms that create recursive calls on q subproblems of size n/2 each and then combine the results in O(n) time. We treat the cases q > 2, q = 1, and q = 2 all separately.

chapter-5.3

Anonymous (anonymous@undisclosed.example.com) — 2014-03-11T17:43:30+00:00

Chapter 5.3: Counting Inversions Consider comparing two rankings of the same set of n movies. A natural way to quantify this notion is by counting the number of inversions. We say that two indices i < j form an inversion if a(i) > a(j), that is, if the two elements a(i) and a(j) are

chapter-5.4

Anonymous (anonymous@undisclosed.example.com) — 2014-03-11T17:58:45+00:00

Chapter 5.4: Finding the Closest Pair of Points The problem: Given n points in a plane, find the pair that is closest together. Designing the Algorithm Let us denote the set of points by P = {p1, ... , pn}, where pi has coordinates (x(i), y(i); and for two points we use d(pi, pj) to denote the distance. Our goal is to find a pair of points that minimizes this distance. We will apply the style of divide and conquer similar to what we used in Mergesort: we find the closest pair among the poin…

chapter-6.1

Anonymous (anonymous@undisclosed.example.com) — 2014-03-26T04:30:28+00:00

Chapter 6.1: Weighted Interval Scheduling: A Recursive Procedure The Weighted INterval Scheduling Problem is a problem in which each interval has a certain value (or weight), and we want to accept a set of maximum value. Two intervals are compatible

chapter-7.1

Anonymous (anonymous@undisclosed.example.com) — 2014-04-01T23:05:59+00:00

Chapter 7.1: The Maximum-flow Problem and the Ford-Fulkerson Algorithm We will be looking at transportation networks - networks whose edges carry some sort of traffic and whose nodes act as “switches” passing traffic between different edges. Network models of this type have

chapter-7.2

Anonymous (anonymous@undisclosed.example.com) — 2014-04-01T23:19:21+00:00

Chapter 7.2: Maximum Flows and Minimum Cuts in a Network Sometimes, C, the sum of the capacities out of the source node s, is a useful upper bound, but often times it is not. We will now use the notion of a cut to develop a much more general means of placing upper bounds on a maximum-flow value. The capacity of a cut (A,B), is the sum of the capacity of all edges out of A.

chapter-7.5

Anonymous (anonymous@undisclosed.example.com) — 2014-04-01T23:49:24+00:00

Chapter 7.5: A First Application: The Bipartite Matching Problem A bipartite graph is an undirected graph whose node set can be partitioned as V = X U Y, with the property that every edge e in E has one end in X and the other end in Y. A matching M in G is a subset of the edges M including E such that each node appears in at most one edge in M. The Bipartite Matching Problem is that of finding a matching in G of largest possible size.

chapter-7.7

Anonymous (anonymous@undisclosed.example.com) — 2014-04-02T04:44:10+00:00

Chapter 7.7: Extensions to the Maximum-Flow Problem Many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph.

preface

Anonymous (anonymous@undisclosed.example.com) — 2014-01-14T00:25:17+00:00

This textbook's main goal is “to show that the subject of algorithms is a powerful lens through which to view the field of computer science in general.” Algorithms are not typically neatly packaged problems and as a result consist of two fundamental components: the task of getting to the mathematically clean core of a problem, and then the task of identifying the appropriate algorithm design techniques. We will begin to approach algorithms as a design process that builds on an understanding o…