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

chapter1.1

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T18:38:44+00:00

Chapter 1.1: The Stable Matching Problem The Stable Matching Problem arose from a situation in which two economists (Gale and Shapley) posed the question: Could one design a college admissions process, or a job recruiting process, that was self-enforcing? What they meant was, is it possible to match employers and applicants in such a way that neither the employer nor an applicant would benefit from trading with another employer/applicant. For example, If person 1 is working for job A but would …

chapter2.1

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T18:38:21+00:00

Chapter 2.1: Computational Tractability A simple definition of efficiency when it comes to algorithms is: An algorithm is efficient if, when implemented, it runs quickly on real input instances. However, this doesn’t really say much about how well the algorithm runs or what exactly an input instance is. So, it’s best to focus on the worst-case running time which will serve as a bound on the largest possible running time an algorithm can have for all inputs of a given size N. There are some case…

chapter2.2

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T18:37:59+00:00

Chapter 2.2: Asymptotic Order of Growth If we can express an algorithm’s worst-case running time on inputs of size n as growing at a rate that is proportional to some function f(n), then that function becomes a bound on the running time of the algorithm. Counting the number of steps an algorithm executes is essentially meaningless both because we will often be using pseudo-code and because we want to classify broad classes of algorithms so we need a more general way of determining running time.…

chapter_2.3

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T18:37:22+00:00

Chapter 2.3: The Stable Matching Problem w/Lists & Arrays In chapter 1.1, we created a basic algorithm for the Stable Matching Problem without having to do any programming. We didn't have to do any actual programming in order to find the bound on run-time for this algorithm, however it is important to think about how the information is presented in a programming situation. Two basic data structures that would work well with our particular algorithm are lists and arrays. These data structures ar…

chapter_2.4

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

Chapter 2.4: A Survey of Common Running Times Linear Time An algorithm running in O(n) time runs at at most a constant factor times the input size (n). In other words, the algorithm processes the input in a single pass. For example: * Computing the Maximum - given a list of n numbers, it is possible to find the maximum in linear time. We can process the numbers a_1, a_2,

chapter_2.5

Anonymous (anonymous@undisclosed.example.com) — 2014-01-27T17:11:26+00:00

Chapter 2.5: Priority Queues A priority queue is designed for applications in which elements have a priority value or key and each time we want to select an element from a set S, we want to take the one with the highest priority. Smaller keys represent higher priorities. Priority queues are good for managing real-time evens such as the scheduling of processes on a computer. Each process has a priority, but they do not arrive in order of their priorities. The running time of each operation of a …

chapter_3.1

Anonymous (anonymous@undisclosed.example.com) — 2014-01-27T17:32:42+00:00

Chapter 3.1: Graphs - Basic Definitions and Applications A graph G is a way of encoding pairwise relationships among a set of objects. It has a collection V of nodes and a collection E of edges, each of which joins 2 nodes together. We represent an edge

chapter_3.2

Anonymous (anonymous@undisclosed.example.com) — 2014-01-27T18:10:58+00:00

Chapter 3.2: Graph Connectivity and Traversal Given a graph G=(V,E) and two particular nodes s and t, how do we know if there is a path from s to t in G? If the graph is small, this problem can be solved naturally by inspection. However, for large graphs (with many nodes and edges), there are two natural algorithms for solving this problem.

chapter_3.3

Anonymous (anonymous@undisclosed.example.com) — 2014-01-27T18:36:13+00:00

Chapter 3.3: Implementing Graph Traversal w/Queues and Stacks The BFS and DFS algorithms differ essentially only in that one uses a queue in its implementation and the other uses a stack. There are two basic ways to represent a graph: using an adjacency matrix

chapter_3.4

Anonymous (anonymous@undisclosed.example.com) — 2014-02-09T20:55:05+00:00

Chapter 3.4: Testing Bipartiteness 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. Another way to think about it is that the nodes in the set

chapter_3.5

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

Chapter 3.5: Connectivity in Directed Graphs In order to represent a directed graph, it is best to use an adjacency lists. Each node can have 2 lists associated with it: a list of nodes it points to and a list of nodes that point to it. Graph search algorithms (BFS & DFS) are basically the same for a directed graph as they are for an undirected graph. BFS starts at a node

chapter_3.6

Anonymous (anonymous@undisclosed.example.com) — 2014-02-12T00:43:57+00:00

Chapter 3.6: Directed Acyclic Graphs & Topological Ordering A directed graph with no cycles is called (obviously) a directed acyclic graph (DAG). DAGs can be used to encode precedence relations or dependencies. For example, if there are a set of tasks {1,2,

chapter_4.1

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

Chapter 4.1: Interval Scheduling The Problem We have a set of requests {1,2,...,n} where the ith request corresponds to an interval of time starting at s(i) and finishing at f(i). A subset of the requests is compatible if no two of them overlap in time, and the goal is to choose the largest possible subset of requests. Compatible sets of maximum size are optimal.

chapter_4.2

Anonymous (anonymous@undisclosed.example.com) — 2014-02-26T02:48:45+00:00

Chapter 4.2: Minimizing Lateness For situations in which there is only a single resource and a set of n requests to use the resource for an interval of time. Each resource is available starting at time s and each request i has deadline d_i. Each request requires time

chapter_4.4

Anonymous (anonymous@undisclosed.example.com) — 2014-02-26T02:49:27+00:00

Chapter 4.4: Shortest Paths in Graphs It is possible to use a greedy algorithm to find the shortest path in a graph, whether the graph is directed or undirected, weighted or unweighted. Dijkstra's Algorithm This algorithm maintains a set S of vertices

chapter_4.5

Anonymous (anonymous@undisclosed.example.com) — 2014-02-26T03:04:40+00:00

Chapter 4.5: Minimum Spanning Trees Suppose we have a set of locations V={v_1, v_2,..., v_n} and we want to build a communication network on top of them. There should be a path between every pair of nodes, but other than this, we want to build as cheaply as possible. If

chapter_4.6

Anonymous (anonymous@undisclosed.example.com) — 2014-02-26T03:17:05+00:00

Chapter 4.6: Kruskal's Algorithm The Union-Find structure stores a representation of the components of a graph in a way that supports rapid searching and updating. We will use this to implement Kruskal's Algorithm. The Union-Find structure allows us to maintain disjoint sets (such as the components of a graph) in the following sense: given a node

chapter_4.7

Anonymous (anonymous@undisclosed.example.com) — 2014-03-02T19:57:18+00:00

Chapter 4.7: Clustering The problem of clustering arises whenever there is a collection of objects that you want to classify or organize into coherent groups. Naturally, the first thing you do is check how similar or dissimilar each pair of objects is. This is commonly known as a

chapter_4.8

Anonymous (anonymous@undisclosed.example.com) — 2014-03-02T20:37:01+00:00

Chapter 4.8: Huffman Codes The problem in this section has to do with bits. Bits are sequences of 0s and 1s that computers can understand. We need an encoding scheme that takes human language and converts it into bits. The easiest way to do this is to use a fixed number of bits for each symbol in the alphabet, and then just concatenate the bit strings for each symbol to form text. However, at the same time, we want to minimize the number of bits needed, check to make sure no bit is a prefix for…

chapter_4

Anonymous (anonymous@undisclosed.example.com) — 2014-02-12T00:48:41+00:00

Chapter 4: Introduction to Greedy Algorithms An algorithm is greedy if it builds up a solution is small steps, choosing a decision at each step myopically to optimize some underlying criterion. In other words, a greedy algorithm chooses the optimal solution locally, in hopes of achieving optimization globally. In many cases, a greedy algorithm does lead to an optimal solution, however there are times when this breaks down (i.e. the postage stamp problem from the lecture slides).

chapter_5.1

Anonymous (anonymous@undisclosed.example.com) — 2014-03-02T20:19:15+00:00

Chapter 5.1: Mergesort Mergesort works by dividing a list of numbers into 2 equal halves, sorting each half recursively, and then combining the results of the recursive calls. Common Divide and Conquer Algorithm Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.

chapter_5.2

Anonymous (anonymous@undisclosed.example.com) — 2014-03-11T21:53:52+00:00

Chapter 5.2: Recurrence Relations If T(n) denotes the running time of a divide-and-conquer algorithm, the it obeys the following recurrence relation: For some constant, c, T(n)=q*T(n/2)+cn when n>2 and T(2)< =c, which I will call (*). We can solve this relation by using unrolling, substitution, and partial substitution.

chapter_5.3

Anonymous (anonymous@undisclosed.example.com) — 2014-03-11T22:12:46+00:00

Chapter 5.3: Counting Inversions Consider a problem that arises in the analysis of rankings. For example, many sites use a technique known as collaborative filtering, in which they try to match your preferences with those of other people out on the internet. The main issue in these types of applications is that of comparing to rankings. If you rank a set of

chapter_5.4

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

Chapter 5.4: Finding the Closest Pair of Points Given n points on a plane, our goal is to find the pair that is closest together. Comparing every possible pairing would take O(n^2) time. However, it is possible to do this in O(nlogn) time. The Algorithm

chapter_6.1

Anonymous (anonymous@undisclosed.example.com) — 2014-03-25T20:49:31+00:00

Chapter 6.1:,Weighted Interval Scheduling The original interval scheduling problem is actually just the special case of weighted interval scheduling where all values are equal to 1. In that case, most greedy algorithms did not solve the problem. So, in the more general weighted interval scheduling problem, no natural greedy algorithm is known to solve this problem. Because of this, we switch to dynamic programming. We still have

chapter_6.2

Anonymous (anonymous@undisclosed.example.com) — 2014-03-24T21:28:06+00:00

Chapter 6.2: Memoization The key idea behind an efficient algorithm using dynamic programming is the memoized array M. It encodes the notion that we are using the value of optimal solutions to the subproblems on intervals {1, 2,…, j}for each j, and it uses the memoization algorithm to define the value of

chapter_6.3

Anonymous (anonymous@undisclosed.example.com) — 2014-03-25T23:51:43+00:00

Chapter 6.3: Segmented Least Squares In previous problems, we've developed recurrence relations based on a binary choice, either n belonged to the optimal solution or it didn't. This problem, however, involves multiway choices; i.e. at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution.

chapter_6.4

Anonymous (anonymous@undisclosed.example.com) — 2014-03-26T00:19:35+00:00

Chapter 6.4: Subset Sums and Knapsacks This problem is a little different from the previous dynamic programming problems we've seen before. Here, we are given n items, each with a nonnegative weight, w_i (for i=1,...,n). There is also a bound W. Our goal is to select a subset

chapter_7.1

Anonymous (anonymous@undisclosed.example.com) — 2014-04-02T00:35:45+00:00

Chapter 7.1: The Maximum Flow Problem and the Ford-Fulkerson Algorithm Graphs are often used to model transportation networks; networks whose edges carry some sort of traffic and whose nodes act as switches, passing traffic between edges. Network models of this type have

chapter_7.2

Anonymous (anonymous@undisclosed.example.com) — 2014-04-02T00:48:21+00:00

Chapter 7.2: Maximum Flows and Minimum Cuts in a Network Consider dividing the nodes of the graph into two sets A and B, so that s is in A and t is in B. We say that an s-t cut is a partition (A,B) of the vertex set V so that s is in A and t is in B. The capacity of a cut (A,B), denoted c(A,B), is the sum of the capacities of all edges out of A.

chapter_7.5

Anonymous (anonymous@undisclosed.example.com) — 2014-04-02T01:28:15+00:00

Chapter 7.5: The Bipartite Matching Problem A bipartite graph G=(V,E) is an undirected graph whose node set can be partitioned as V=X∪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⊆E such that each node appears in at most one edge in M. The Bipartite Matching Problem (BMP) is that of finding a matching in G of largest possible size.

chapter_7.7

Anonymous (anonymous@undisclosed.example.com) — 2014-04-02T02:09:02+00:00

Chapter 7.7: Extensions to the Maximum Flow Problem So far in our maximum flow problems, we've only had a single source s and a single sink t. Now suppose that there can be a set S of sources generating flow and a set T of sinks that can absorb flow. With multiple sources and sinks, it is unclear how to decide which source or sink to favor in a maximization problem. So instead of maximizing the flow value, we will consider a problem where sources have fixed supply values and sinks have fixed de…

home

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T18:07:36+00:00

Alyssa's Journal

preface

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T18:38:59+00:00

Preface Algorithmic ideas and notions are not just limited to long-standing, well-known problems. They span a wide range of topics and subject fields. Algorithms have many applications beyond computer science, but they do allow for a better view of computer science in general. Despite how essential they are to computer science, they do not always come in the form of a precise, mathematical question. Oftentimes, they are surrounded by complicated, problem-specific details that are sometimes supe…

sidebar

Anonymous (anonymous@undisclosed.example.com) — 2014-03-29T18:27:12+00:00

Algorithm Analysis Journal Alyssa's Journal * Preface * Stable Matching * Computational Tractability * Asymptotic Order of Growth * Stable Matching w/Lists and Arrays * A Survey of Common Running Times * Priority Queues * Graphs: Basic Definitions and Algorithms * Graph Connectivity and Traversal * Implementing Graph Traversal w/Queues and Stacks * Testing Bipartiteness * Connectivity in Directed Graphs * Directed Acyclic Graphs & Topological Ordering * Introduction…