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

chapter1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-22T21:56:24+00:00

Chapter 1 Section 1.1 : A First Problem: Stable Matching The stable matching problem/algorithm attempts to find a stable matching (pairing) between individuals of two sets of the same size given a ranking of preferences for each individual within the set. A matching is a mapping from the elements of one set to the elements of the other set.

chapter2

Anonymous (anonymous@undisclosed.example.com) — 2018-02-05T20:31:59+00:00

Chapter 2 Section 2.1 : Computational Tractability This section is all about defining efficiency and deciding which algorithms actually are efficient and how efficient they are. An algorithm is not necessarily efficient if it runs quickly, and not necessarily inefficient if it runs slowly. Efficiency has to do with the best case and worst case for each individual algorithm independent of platform or instance. We start by comparing the worst case performance with the performance of the brute-fo…

chapter3

Anonymous (anonymous@undisclosed.example.com) — 2018-02-07T00:51:00+00:00

Chapter 3 Section 3.1: Basic Definitions and Applications A graph G is simply a way of encoding pairwise relationships among a set of objects: it consists of a collection V of nodes and a collection E of edges, each of which “joins” two of the nodes. We thus represent an edge e ∈ E as a two-element subset of V: e = {u, v} for some u, v ∈ V, where we call u and v the ends of e.

chapter4

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

Introduction: Greedy Algorithms An algorithm is said to be greedy is 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 in solving a nontrivial problem optimally, it typically implies something interesting and useful about the structure of the problem itself. There are two basic methods for proving that a greedy algorithm produces an optimal solution to a problem:

chapter5

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

Section 5.1: A First Recurrence: The Mergesort Algorithm Divide and Conquer Algorithms * Process * Break up problem into several parts * Solve each part recursively * Combine solutions to sub-problems into overall solution * Use recurrences to analyze the runtime of divide and conquer algorithms

chapter6

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

Section 6.1: Weighted Interval Scheduling: A Recursive Procedure Weighted Interval Scheduling * Job j starts at sj, finishes at fj, and has weight or value vj * Two jobs are compatible if they don't overlap * Goal: find maximum weight subset of mutually compatible jobs

home

Anonymous (anonymous@undisclosed.example.com) — 2018-03-27T20:43:04+00:00

Emily Boyes' Wiki * Preface * Chapter 1: Introduction: Some Representative Problems * Chapter 2: Basics of Algorithm Analysis * Chapter 3: Graphs * Chapter 4: Greedy Algorithms * Chapter 5: Divide and Conquer * Chapter 6: Dynamic Programming

preface

Anonymous (anonymous@undisclosed.example.com) — 2018-01-18T22:16:29+00:00

Preface Not only do algorithms have many broad applications, but they also provide a “lens through which to view the field of computer science in general.” There are two important components to the study of algorithms: getting to the basic core of the problem and then deciding which algorithm design techniques to use depending on the structure of the problem. Algorithms are not only just the means to the solutions of problems; understanding how to solve different problems with the best algorith…

sidebar

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

Emily Boyes' Wiki * Preface * Chapter 1: Introduction: Some Representative Problems * Chapter 2: Basics of Algorithm Analysis * Chapter 3: Graphs * Chapter 4: Greedy Algorithms ---------- Emily Boyes' Wiki <- CSCI 211: Algorithm Design and Analysis