http://servo.ad.wlu.edu/dokuwiki/ 2026-04-16T01:40:23+00:00 http://servo.ad.wlu.edu/dokuwiki/ http://servo.ad.wlu.edu/dokuwiki/lib/exe/fetch.php/wiki/dokuwiki-128.png text/html 2011-01-27T07:07:42+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/chapter1?rev=1296112062&do=diff Chapter 1: Introduction 1.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 sol… text/html 2011-01-27T08:20:12+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/chapter2?rev=1296116412&do=diff Chapter 2: Algorithm Analysis 2.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. text/html 2011-02-18T06:51:46+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/chapter3?rev=1298011906&do=diff Chapter 3: Graphs 3.1 Basic Definitions and Applications 3.2 Graph Connectivity and Graph Traversal 3.3 Implementing Graph Traversal Using Queues and Stacks 3.4 Testing Bipartiteness: An Application of Breadth-First Search 3.5 Connectivity in Directed Graphs text/html 2011-02-20T02:45:38+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/chapter4?rev=1298169938&do=diff Chapter 4: Greedy Algorithms Greedy algorithms build up solutions in small steps, “taking as much as they can” to reduce the size of the problem at hand. It may be easy to come up with greedy solutions for any kind of problem, but greedy solutions are not always optimal. In this chapter we will learn how to choose rules that make greedy solutions work and prove that they are optimal. text/html 2011-03-16T06:57:54+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/chapter5?rev=1300258674&do=diff Chapter 5: Divide and Conquer Large inputs can be computationally costly to work with. Smaller inputs are necessarily less so. We consider dividing large problems into smaller, easier ones and combining our findings later. Although combining results has an associated cost, the hope is that our solution will be more efficient than it was before. text/html 2011-04-05T05:52:23+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/chapter6?rev=1301982743&do=diff Chapter 6: Dynamic Programming Dynamic programming is a combination of divide and conquer and brute-force strategies: it (implicitly) looks at all possible solutions by decomposing problems into smaller ones, and it subtly takes advantage of things it knows to pick the best solution without explicitly looking at each one. The authors liken it to a balancing act that takes time to become comfortable with. Dynamic Programming is the antithesis of the greedy strategy because it doesn't attempt to … text/html 2011-04-06T08:16:13+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/chapter7?rev=1302077773&do=diff Chapter 7: Network Flow Essentially a return to bipartite matching, this chapter extends the special case of the Bipartite Matching Problem to other matching problems such as the mapping of customers to stores. We recall the definitions of matching and perfect matching, which are, respectively, text/html 2011-04-05T05:20:43+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/home?rev=1301980843&do=diff Charles' Journal * Preface * Chapter 1: Introduction * Chapter 2: Algorithm Analysis * Chapter 3: Graphs * Chapter 4: Greedy Algorithms * Chapter 5: Divide and Conquer * Chapter 6: Dynamic Programming * Chapter 7: Network Flow text/html 2011-01-27T07:08:14+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/preface?rev=1296112094&do=diff 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 com… text/html 2011-04-05T05:24:14+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/charles/sidebar?rev=1301981054&do=diff Home Preface Ch 1: Introduction Ch 2: Algorithm Analysis Ch 3: Graphs Ch 4: Greedy Algorithms Ch 5: Divide and Conquer Ch 6: Dynamic Programming Ch 7: Network Flow