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

ch1.1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-19T03:57:41+00:00

Chapter 1 This section focuses on the algorithm developed by David Gale and Lloyd Shapley in 1962. The algorithm, called the Stable matching problem, is meant to answer the question: “Could one design a college admissions process, or a job recruiting process, that was self-enforcing?” This algorithm can also be illustrated by matching groups of people into “couples” so that they all are matched with the best possible individual to lead to a stable relationship environment. The remainder of the …

ch1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-17T00:18:52+00:00

This section focuses on the algorithm developed by David Gale and Lloyd Shapley in 1962. The algorithm, called the Stable matching problem, is meant to answer the question: “Could one design a college admissions process, or a job recruiting process, that was self-enforcing?

ch2.1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-23T01:23:34+00:00

Chapter 2 2.1: Computational Tractability The section begins by coming up with a working definition of an efficient algorithm. It begins with saying an algorithm is efficient if it runs quickly on real-life inputs. Next, after discussing brute force, it amends this to saying an algorithm is efficient if it performs better than brute force search. Lastly, the text discusses the concept of polynomial time and amends the definition of efficiency to if an algorithm runs in polynomial time. Lastly,…

ch2.2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-17T00:46:13+00:00

This section goes into how to specifically talk about run-times. For instance, it discusses disregarding constant factors and terms not of the highest order coefficient. In building up this description, the concepts of Asymptotic upper and lower bounds are introduced to help fully categorize running times. O(*) deals with upper bounds as opposed to specific growth rates. Capital omega is used similar to O(*) to discuss the lower bound. Lastly, asymptotic tight bounds are introduced and are repre…

ch2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-29T23:52:48+00:00

ch3

Anonymous (anonymous@undisclosed.example.com) — 2018-02-07T03:19:18+00:00

Chapter 3 3.1: Basic Definitions and Applications Chapter 3 delves into the world of graphs, and this section lays down the framework for more advanced discussion and uses. As defined previously, a graph is a means of encoding relationships between pairs of elements. It does this by tracking vertices, elements, and edges, connections between pairs of elements. Edges typically denote a symmetric relationship, but directed graphs denote one way relationships. Transportation networks, communicati…

ch4

Anonymous (anonymous@undisclosed.example.com) — 2018-03-12T18:08:51+00:00

Chapter 4 4.1: Interval Scheduling: The Greedy Algorithm Stays Ahead This section discusses the Greedy Stays Ahead algorithm. It focuses on maximizing the number of compatible intervals that can be scheduled. It refers to the maximal compatible set as optimal. In designing possible algorithms, it discusses the natural ways we could go about picking a first interval. One not optimal solution is to simply pick the earliest interval, but this does not work. The next idea is picking the shortest i…

ch5

Anonymous (anonymous@undisclosed.example.com) — 2018-03-12T20:23:59+00:00

Chapter 5 5.1: A First Recurrence: The Mergesort Algorithm This section begins the chapter meant to break down and discuss several divide and conquer algorithms. We begin with the familiar Mergesort. This algorithm involves breaking up the input into smaller groups, organizing each group, and putting them back together. To use the book's words. The underlying concept is

ch6

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

Chapter 6 6.1: Weighted Interval Scheduling: A Recursive Procedure We have previously discussed Interval Scheduling with all weights equal to 1, but this section delves into a more general case of the problem where values can vary. Unfortunately, the greedy algorithm we previously discussed in the unweighted case will no longer be optimal for what we are doing. Thus, we need a new algorithm. In fact, we must move away from greedy algorithms all together, as one may have guessed, we now must us…

ch7

Anonymous (anonymous@undisclosed.example.com) — 2018-04-02T21:14:44+00:00

Chapter 7 7.1: The Maximum-Flow Problem and the Ford-Fulkerson Algorithm Often times, graphs are used to model transportation networks where the edges represent connections between objects or places. In real life, these routes typically have some amount of maximum capacity. Additionally, some nodes will generate this traffic, which are called sources, and others will be the destination of traffic, AKA sinks. The traffic in a graph of this nature is called flow, and the graph itself is called a…

home

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

Max's Wiki * Preface: first two pages * Chapter 1: Section 1 * Chapter 2 * Chapter 3 * Chapter 4 * Chapter 5 * Chapter 6 * Chapter 7

preface

Anonymous (anonymous@undisclosed.example.com) — 2018-01-16T23:35:35+00:00

The first two pages of the preface focus not necessarily on the power of algorithms, but on the issues surrounding the problems they solve. It is not as simple as “prove that 4 is composite.” Instead, the problems posed to developers often include weird fringe cases and require prioritizing different parts of the user experience. As a result, often times there is not simply one end all be all algorithm to handle the problem. Instead, depending on the specifics of the situation, other algorithms …

sidebar

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

Max's Wiki * Preface: first two pages * Chapter 1: Section 1 * Chapter 2 * Chapter 3 * Chapter 4 * Chapter 5 * Chapter 6 * Chapter 7 ---------- <- Max's Wiki <- CSCI 211: Algorithm Design and Analysis