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

chapter1

Anonymous (anonymous@undisclosed.example.com) — 2014-01-16T15:59:40+00:00

Chapter 1 Gale and Shapely asked, “Given a set of preferences among employers and applicants, can we assign applicants to employers so that for every employer E and every applicant A who is not scheduled to work for E, at least one of the following two things is the case?

chapter2

Anonymous (anonymous@undisclosed.example.com) — 2014-01-22T04:03:04+00:00

Section 2.1 - Computational Tractability To begin with, we will focus on analyzing the worst-case running time: we will look for a bound on the largest possible running time the algorithm could have over all inputs of a given size N and see how this scales with

chapter3

Anonymous (anonymous@undisclosed.example.com) — 2014-02-12T04:40:56+00:00

Section 3.1 - Basic Definitions and Applications The reading wasn't as helpful as the past few weeks because I felt like I already knew a lot of it from class. Recall from Chapter 1 that a graph G is simply a way of encoding pariwise relationships among a set of objects: it consists of a collection

chapter4

Anonymous (anonymous@undisclosed.example.com) — 2014-03-05T04:55:51+00:00

An algorithm is greedy if it builds up a solution in small steps choosing a decision at each step myopically to optimize some underlying criterion. 4.1 - Interval Scheduling: The Greedy Algorithm Stays Ahead Designing a Greedy Algorithm (using the Interval Scheduling Problem) Use a simple rule to select a first request i1; once that is accepted, we reject all requests that are not compatible with i1. We then select the next request i2 to be accepted and again reject all requests that are not c…

chapter5

Anonymous (anonymous@undisclosed.example.com) — 2014-03-12T00:47:22+00:00

Divide and conquer refers to a class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively and then combines the solutions to these subproblems into an overall solution. 5.1 - A First Recurrence: The Mergesort Algorithm

chapter6

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

6.1 - Weighted Interval Scheduling: A Recursive Procedure The Weighted Interval Scheduling Problem is a strictly more general version of the Interval Scheduling Problem, in which each interval has a certain value ( or weight) and we want to accept a set of maximum value.

home

Anonymous (anonymous@undisclosed.example.com) — 2014-01-21T03:52:47+00:00

Deirdre's Journal

preface

Anonymous (anonymous@undisclosed.example.com) — 2014-01-16T16:00:18+00:00

Preface Algorithms can be found in almost any discipline from biology to economics to computer science and therefore have a huge range of applications. There are two components to the “algorithmic enterprise” 1) the task of getting to the mathematically clean core of a problem and 2) the task of identifying the appropriate algorithm design techniques, based on the structure of the problem. Interacting together, we can use algorithmic ideas to both ask questions and find answers in the world. I w…

sidebar

Anonymous (anonymous@undisclosed.example.com) — 2014-03-26T03:12:58+00:00

Deirdre's Sidebar * Preface * Chapter 1 * Chapter 2 * Chapter 3 * Chapter 4 * Chapter 5 * Chapter 6 ---------- <- CSCI 211: Algorithm Design and Analysis