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

chapter1

Anonymous (anonymous@undisclosed.example.com) — 2018-01-11T00:45:25+00:00

1.1 A First Problem: Stable Matching Problem Explanation The Stable Matching Problem originated from two mathematical economists, David Gale and Lloyd Shapley, who wanted to understand if it was possible to design a job recruiting process that was

chapter2

Anonymous (anonymous@undisclosed.example.com) — 2018-01-28T20:18:18+00:00

Chapter 2 2.1 Computational Tractability Algorithm Goals * Many algorithms are discrete: the goal is to efficiently find a solution that satisfies certain very clear conditions. * Running Time * Efficiency: amount of space (or memory) Defining Efficiency

chapter3

Anonymous (anonymous@undisclosed.example.com) — 2018-02-05T05:40:53+00:00

Chapter 3 3.1 Basic Definitions and Applications * Graph: encodes pairwise relationships among a set of objects; consists of a collection V of nodes and a collection E of edges * Directed Graph: consists of a set of nodes V and a set of directed edges E' (each e' is an ordered pair - u (tail) and v (head) are not interchangeable)

chapter4

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

Chapter 4 Greedy Algorithm: 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 * Interval Scheduling Problem: set of requests, where the ith request corresponds to an interval of time starting at s(i) and finishing at f(i)

chapter5

Anonymous (anonymous@undisclosed.example.com) — 2018-03-10T20:28:38+00:00

Chapter 5 * Divide and Conquer: 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 * Recurrence Relation: bounds the running time recursively in terms of the running time on smaller instances

chapter6

Anonymous (anonymous@undisclosed.example.com) — 2018-03-26T16:42:28+00:00

Chapter 6 * In general, most problems do not have a natural greedy algorithm solution that works * Divide and conquer is often not strong enough to reduce exponential brute-force search down to polynomial time * Dynamic Programming: one implicitly explores the space of all possible solutions, by decomposing things into a series of subproblems, and then building up correct solutions to larger and larger subproblems

chapter7

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

Chapter 7 * Matching in bipartite graphs can model situations in which objects are being assigned to other objects * Nodes in X represent jobs, and the nodes in Y represent machines, and an edge (xi,yj) indicates that machine yj is capable of processing job xi.

home

Anonymous (anonymous@undisclosed.example.com) — 2018-03-30T18:42:56+00:00

Karishma's Wiki * Preface * Chapter 1: Introduction * 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-10T02:43:41+00:00

Preface Algorithms have many applications and occur in all fields, from computer science to biology to economics. Looking specifically at computer science, algorithms form the core of the field of study. There are two fundamental components: * Getting to the mathematically clean core of a problem

sidebar

Anonymous (anonymous@undisclosed.example.com) — 2018-03-30T18:46:57+00:00

Karishma's Journal * Preface * Chapter 1 * Chapter 2 * Chapter 3 * Chapter 4 * Chapter 5 * Chapter 6 * Chapter 7 ---------- <- Karishma's Wiki <- CS211 Wiki