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

ch1

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

Chapter 1: Intro 1.1: Stable Matching The Stable Matching Problem is presented in a variety of motivational contexts, ranging from summer internships to medical school residencies. In 1962, mathematical economists Gale and Shapley approached it in the hopes of a

ch2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-30T04:48:07+00:00

Chapter 2: Basics of Algorithm Analysis 2.1: Computational Tractability When considering computational algorithms, two crucial aspects are the algorithm's usage of physical memory space, and its run-time. In many situations we will find that a balance must be struck between the two.

ch3

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

Chapter 3: Graphs 3.1: Basic Definitions and Applications We define a graph as a collection V of vertices, or nodes, and a collection of edges between those vertices, represented as two-element subsets: {u, v}, where u and v are nodes. For a directed graph

ch4

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

Greedy Algorithms Greedy algorithms essentially use a localized decision making process to yield a globally optimal solution. Fortunately, the ability of a greedy algorithm to solve a nontrivial usually reveals a great deal about the structure and nature of the problem itself. In the first two sections of the chapter we will work through two example problems to illustrate two typical methods of proving the greedy algorithm indeed yields an optimal solution:

ch5

Anonymous (anonymous@undisclosed.example.com) — 2018-03-12T22:14:39+00:00

Divide and Conquer This group of algorithmic techniques hinges upon breaking apart the input, and then solving each piece recursively. Analyzing run times then involves solving a recurrence relation that bounds the time recursively in terms of the run time of smaller instances.

ch6

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

Dynamic Programming As has already become prevalent in our brief class discussions, dynamic programming feels very much like we are tiptoeing around brute force exploration. The technique consists of breaking the search space into smaller subproblems, and then growing progressively larger until we have a global solution. An important key to note is that these techniques are crucial to problems for which greedy algorithms do not exist, especially because our thus far studied divide and conquer a…

ch7

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

Chapter 7: Network Flow En route to develop a polynomial time algorithm for finding the largest matching in a bipartite graph, we will formulate a generate class of problems--network flow problems--from which we can narrow down to bipartite matching.

home

Anonymous (anonymous@undisclosed.example.com) — 2018-04-03T01:19:58+00:00

Gillen's Wiki * Preface (first two pages) * Chapter 1: Intro * Chapter 2: Basics of Algorithm Analysis * Chapter 3: Graphs * Chapter 4: Greedy Algorithms * Chapter 5: Divide and Conquer * Chapter 6: Dynamic Programming * Chapter 7: Network Flow

preface

Anonymous (anonymous@undisclosed.example.com) — 2018-01-15T01:04:32+00:00

Preface (first two pages) This section sets the stage for the coming semester. After a brief bit of motivation (i.e. “algorithms are everywhere”), we are given the breakdown of how, when given a problem, to approach it. That approach is two-fold: breaking the problem down into it's true mathematical skeleton, and then proceeding to find algorithm design techniques that may be applied. Becoming comfortable with both of these parts will come through practice, experience, and time

sidebar

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

Gillen's Wiki * Preface (first two pages) * Chapter 1: Intro * Chapter 2: Basics of Algorithm Analysis ---------- <- Gillen's Wiki <- CSCI 211: Algorithm Design and Analysis