Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:charles:home [2011/01/26 04:59] – gouldc
+++ courses:cs211:winter2011:journals:charles:home [2011/04/05 05:20] (current) – gouldc
@@ Line 1: / Line 1: @@
 ====== Charles' Journal ======
-PREFACE
-Algorithms are pervasive both within and beyond computer science. Understanding algorithms gives a glimpse into the whole of computer science.
-Two fundamental components of algorithm analysis: determining its mathematical core, identifying an appropriate design.
-The book builds upon prior knowledge of data structures and programming. It is meant to be read by students who have taken introductory courses in the discipline.
-A good portion of the book will be dedicated to the notion of computational intractability. We will see that problems can be proved to be NP-complete, and we will learn what to do if that is the case.
-CHAPTER ONE -- INTRODUCTION: SOME REPRESENTATIVE PROBLEMS
-.1 A First Problem: Stable Matching
-The problem of stable matching is best explained using an example. In class we used bachelors and bachelorettes. Suppose some man m is engaged to some woman w, and another man m' is engaged to another woman w'. Now, suppose that m prefers w' to w, and w' prefers to m to m'. It would be preferable for m and w' to break their engagements, since each would be happier together than they are currently. This is an unstable situation. A solution to this problem would be a set of engagements in which no unstable pairings exist. If each person's preference list for the opposite sex is provided, is it possible to construct such a set?
-.2 Five Representative Problems
-(1) Interval scheduling
-And then ITS decreed, "Computer labs shall remain locked at all times and under any circumstances, except when a university professor schedules hours in them in advance." Professor Sprenkle has to register lab times with Steve now. She tells Steve, "I want to use the computer lab on M,W,F from 10:10 am  to 11:05 am." Then Professor Stough enters, asking if he can reserve the room for F, 10:45 to 12:45 to teach a C++ workshop to his CS340 students. How does Steve determine who gets to reserve the room on F morning (there is an overlap from 10:45 to 11:05)? The time overlap of these "requests" makes the requests incompatible, and so one of the requests must be rejected. We want "to select a compatible subset of requests of maximum possible size."
-(2) Weighted interval scheduling
-This is similar to the interval scheduling problem; the difference is that each request has an associated value (weight). We no longer want to accept the maximum number of compatible requests. We want to accept the subset of requests that yields the maximum sum value.
-(3) Bipartite matching
-Bipartite graphs can model assignments (likes jobs being assigned to machines). Each job should be matched to a machine, and each machine should be matched to a job. We represent bipartite graphs as two columns of nodes, with edges (assignments) from nodes in the first column to nodes in the second column. The stable matching problem is an example of bipartite matching. More formally, such a problem is defined in the following way: "Given an arbitrary bipartite graph G, find a matching of maximum size. If |X| = |Y| = n, then there is a perfect matching if and only if the maximum matching has size n."
-(4) Independent set
-A set of nodes is independent if no two nodes in S are joined by an edge. Example problem: you have n friends, some pairs don't get along. Find the maximum number of friends you can invite to say a birthday party and avoid any conflicts. Interval scheduling and bipartite matching can both be thought of (encoded) as special cases of the independent set problem. There is no efficient algorithm for the independent set problem currently. We will see later that "Independent Set" is one problem in the large class of NP-complete problems.
-(5) Competitive facility location
-Walmart vs K-Mart. Both companies want to build stores in convenient locations (to increase market share, etc.). But all around the country, local zoning regulations prevent the franchises from being located too near one another. Assume the geographic region over which they are vying for control is divided into n zones (1, 2, ..., n), and each zone has an associated value (the expected revenue for each company if it opens a store there). Who will win the game? Which company will open a store in location X, Y, Z?
-CHAPTER TWO -- BASICS OF ALGORITHM ANALYSIS
-.1 Computational Tractability
-"[Many of the problems we study] will involve an implicit search over a large set of combinatorial possibilities, and the goal will be to efficiently find a solution that satisfies certain clearly delineated conditions.") This section reads like a Socratic dialogue: it attempts to define something, refutes its own proposed definitions, and (unlike a Socratic dialogue) finally agrees on a definition. An algorithm is considered "efficient" if it has a polynomial running time.
-.2 Asymptotic Order of Growth
-As input size grows, the worst-case running time grows at a rate proportional to some function f(n). This function becomes a BOUND on the running time of the algorithm.
-There are three types of asymptotic bounds: upper bounds (big-O), lower bounds (omega), and tight bounds (theta). Asymptotic growth rates have the properties of additivity and transitivity. Some propositions/proofs are given about some common types of functions (polynomials, logarithms, and exponentials).
-Polynomials are O(n^2), logarithms are O(log n), and exponentials are O(r^n).
-.3 Implementing the Stable Matching Algorithm Using Lists and Arrays
-The Gale-Shapley Stable Matching algorithm terminates in at most n^2 iterations (we learned this earlier). It would be nice to construct an algorithm that is O(n^2). For this to work, every iteration has to be implemented in constant time. It is important for programmers to consider the data structures they will be using; they are chosen for efficiency and for ease of implementation. The G-S algorithm can be implemented using arrays and linked lists. A section is dedicated to an overview of these data structures (including their advantages and disadvantages) but we know about them by now.
-.4 A Survey of Common Running Times
-.5 A More Complex Data Structure: Priority Queues
+  * [[preface|Preface]]
+  * [[chapter1|Chapter 1: Introduction]]
+  * [[chapter2|Chapter 2: Algorithm Analysis]]
+  * [[chapter3|Chapter 3: Graphs]]
+  * [[chapter4|Chapter 4: Greedy Algorithms]]
+  * [[chapter5|Chapter 5: Divide and Conquer]]
+  * [[chapter6|Chapter 6: Dynamic Programming]]
+  * [[chapter7|Chapter 7: Network Flow]]