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

chapter1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-09T22:13:22+00:00

Chapter 1: Introduction 1.1 A First Problem: Stable Matching The Stable Matching Problem is based on a question posed by David Gale and Lloyd Shapley which involved a self-enforcing admissions or recruiting process. In a more technical sense, this question is phrased as follows:

chapter2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-28T02:17:07+00:00

Chapter 2: Basics of Algorithm Analysis 2.1 Computational Tractability Several factors are key in the design of algorithms, including understanding the discrete nature of many problems as well as addressing the efficiency and space of an algorithm. The text gives one definition of efficiency:

chapter3

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

Chapter 3: Graphs 3.1 Basic Definitions and Applications A graph represents pairwise relationships between objects and consists of nodes and edges. In order to represent asymmetric relationships between ends of a graph, we would use a directed graph

chapter4

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

Chapter 4: Greedy Algorithms 4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead In the interval scheduling problem, we considered a set of requests {1, 2, ..., n} where the ith request corresponds to an interval of time beginning at s(i) and finishing at

chapter5

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

Chapter 5: Divide and Conquer 5.1 A First Recurrence: The Mergesort Algorithm Mergesort sorts a list by dividing it in half, sorting each half separately using recursion, and combining the two sorted lists. This is a template for many divide-and-conquer algorithms:

chapter6

Anonymous (anonymous@undisclosed.example.com) — 2018-03-25T15:22:59+00:00

Chapter 5: Dynamic Programming 6.1 Weighted Interval Scheduling: A Recursive Procedure A different version of the previously-discussed interval scheduling problem is one in which each interval has a certain value/weight and we want to find a maximum value. There is no natural greedy algorithm which we know to be able to solve this problem, so we must use dynamic programming with recursion. We would like to assume that the intervals are sorted by their finishing time. We then start by consideri…

chapter7

Anonymous (anonymous@undisclosed.example.com) — 2018-03-31T18:48:16+00:00

Chapter 7: Network Flow 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm Graphs can be used to model transportation networks, which are networks whose edges carry “traffic” and whose nodes pass the traffic between the edges. These graphs have the following:

home

Anonymous (anonymous@undisclosed.example.com) — 2018-03-31T17:56:53+00:00

Nora's Wiki * Preface * Chapter 1 * Chapter 2 * Chapter 3 * Chapter 4 * Chapter 5 * Chapter 6 * Chapter 7

preface

Anonymous (anonymous@undisclosed.example.com) — 2018-01-09T14:53:49+00:00

Preface From biology to economics, algorithmic principles are found in numerous fields and are used to solve a wide range of problems, both old and new. Most importantly, however, algorithms are essential in the field of computer science, with two primary tasks:

sidebar

Anonymous (anonymous@undisclosed.example.com) — 2018-03-31T17:57:29+00:00

Nora's Wiki Navigation: * Preface * Chapter 1: Introduction * Chapter 2: The Basics of Algorithm Analysis * Chapter 3: Graphs * Chapter 4: Greedy Algorithms * Chapter 5: Divide and Conquer * Chapter 6: Dynamic Programming * Chapter 7: Network Flow ---------- <- Nora's Wiki <- CSCI 211: Algorithm Design and Analysis