http://servo.ad.wlu.edu/dokuwiki/ 2026-04-16T22:56:43+00:00 http://servo.ad.wlu.edu/dokuwiki/ http://servo.ad.wlu.edu/dokuwiki/lib/exe/fetch.php/wiki/dokuwiki-128.png text/html 2012-01-18T02:46:24+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter2section1?rev=1326854784&do=diff 2.1 Computational Tractability Efficiency of algorithms is defined in the terms of the running time and the algorithms must be efficient in their use of other resources as well, especially the amount of space(or memory) they use. To analyze algorithms, we focus on the text/html 2012-03-01T04:12:31+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_section0?rev=1330575151&do=diff 4.0 Greedy Algorithms An algorithm is greedy if it builds up a solution in small steps, choosing the best solution at step to optimize some underlying criterion. It often is possible to find many greedy solutions for the same problem. The biggest challenge when dealing with greedy algorithms is to find the cases in which the found greedy algorithms work well and prove that they indeed work well. The main approaches used are: text/html 2012-02-24T20:55:05+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectioni?rev=1330116905&do=diff 4.1. Interval Scheduling: The Greedy Algorithm Stays Ahead The Greedy Algorithm stays ahead means that if we measure the greedy algorithm's progress in a step-by-step fashion, we see that it does better than any other algorithm. Thus it produces an optimal solution. For the Interval Scheduling Problem, we have a set of requests {1,2,3, text/html 2012-02-26T22:13:10+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectionii?rev=1330294390&do=diff 4.2. Scheduling to Minimize Lateness: An Exchange Argument The Problem * We have a single resource and a set of n requests to use the resource * The resource has a deadline d i and requires a contiguous interval of time t i * Each request is flexible: It can be scheduled at any time before its deadline. text/html 2012-02-27T03:25:38+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectioniii?rev=1330313138&do=diff 4.3. Optimal Caching: A More Complex Exchange Argument The Problem * caching: The process of storing a small amount of data in a fast memory to reduce the time spent interacting with a slow memory. * cache maintenance algorithms determine what to keep in the cache and what to delete from it when new data is brought in. text/html 2012-02-29T07:28:02+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectioniv?rev=1330500482&do=diff 4.4. Shortest paths in a graph The Problem * We are given a directed graph G = (V,E) with a starting node S.We assume that s has a path to every other node in G. * Each edge e has a length le≥ 0, which it the cost of traversing e. * For each path P, the length of P( text/html 2012-03-01T02:15:49+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectionv?rev=1330568149&do=diff 4.5. The Minimum Spanning Tree Problem * A Spanning Tree is a tree that spans all the nodes in a graph * Given a connected graph G = (V, E) with positive edge weights ce, a Minimum Spanning Tree is a subset of the edges T ⊆ E such that T is a spanning tree whose sum of edge weights is minimized. text/html 2012-03-01T03:54:14+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectionvi?rev=1330574054&do=diff 4.6. Implementing Kruskal's Algorithm: The Union-Find Data Structure * The basic idea behind the algorithm is that the graph in question has a fixed population of nodes * And the graphs grows over time by inserting edges between certain pairs of nodes. text/html 2012-03-06T03:38:56+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectionvii?rev=1331005136&do=diff 4.7 Clustering The Problem Clustering arises when one is trying to classify a collection of objects into coherent groups.The first question that comes into mind is whether there exist some measure under which each pair of objects is similar or dissimilar to another. A common approach used is to define a text/html 2012-03-06T05:27:09+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterfour_sectionviii?rev=1331011629&do=diff 4.8 Huffman Codes and Data Compression The Problem * Encoding Symbols Using Bits: * We need schemes to encode text written in richer alphabets and converts this text into long strings of bits. * The first thought would be to represent all of the symbol by the same number of bits text/html 2012-04-02T11:03:38+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptersevensectioni?rev=1333364618&do=diff 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm The Problem Graphs are often used to model transportation networks: edges carry some sort of traffic and nodes pass traffic between edges. In this model: * capacities on the edges: indicate how much traffic the edges can carry text/html 2012-04-02T11:25:08+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptersevensectionii?rev=1333365908&do=diff 7.2 Maximum Flows and Minimum Cuts in a Network Analyzing the Algorithm: Flows and Cuts * Cuts: An s-t cut is a partition (A, B) of V with s ∈ A and t ∈ B * The Capacity of a cut(A,B) is: The sum of all the capacities of all edges out of A: c(A,B) = ∑ text/html 2012-04-02T12:10:44+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptersevensectionv?rev=1333368644&do=diff 7.5 A First Application: The Bipartite Matching Problem The Problem * A Bipartite graph G =(V,E) is an undirected graph whose node set can be partitioned as V = X U Y, where every edge e ∈ E has one end in X and the other in Y. * A Matching M in G is a subset of the edges M ⊆ E such that each node appears in at most one edge in M. text/html 2012-04-02T16:56:14+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptersevensectionvii?rev=1333385774&do=diff 7.7 Extensions to the Maximum-Flow Problem The Problem: Circulations with Demands * Directed graph G = (V, E) * Edge capacities c(e), e ∈ E * Node supply and demands d(v), v ∈ V: * If d(v) > 0: node v has demand of d(v) flow--> The node is a sink and wishes to receive d(v) units more flow than it sends out text/html 2012-03-28T01:13:25+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptersixsectioni?rev=1332897205&do=diff 6.1. Weighted Interval Scheduling: A Recursive Procedure Chapter Six is concerned about ways of solving problems using Dynamic Programming techniques. When solving problems with Dynamic Programming, one implicitly explores the space of all possible solutions, by carefully decomposing them into several subproblems, and then building up correct solutions to larger and larger subproblems. With the Weighted interval scheduling problem, is a generalization of the Interval scheduling problem in whi… text/html 2012-03-28T01:37:48+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptersixsectionii?rev=1332898668&do=diff 6.2. Principles of Dynamic Programming: Memoization or iteration over Subproblems Designing the Algorithm The key to the efficient solution found by Memoization is the array M that keeps track of the previously computed solutions. Once we have the array M, the problem is solved: M[n] contains the value of the optimal solution on the full instance and Find-Solution can be used to trace back through M efficiently and return an optimal solution. text/html 2012-03-28T02:39:29+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptersixsectioniii?rev=1332902369&do=diff 6.3. Segmented Least Squares: Multi-way Choices With this problem, at each step we have a polynomial number of possibilities to consider the structure of the optimal solution. The Problem " " " " " " " " " " " " " " " " " " Suppose our data consists of a set P of n points in the plane,: text/html 2012-03-28T03:13:51+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptersixsectioniv?rev=1332904431&do=diff 6.4 Subset Sums and Knapsacks: Adding a Variable The Problem " " " " " " " " " " " " " " " " " " " Given n objects and a “knapsack” Item i weighs wi > 0 kilograms and has value vi > 0 Alternative: jobs require w i time text/html 2012-01-30T23:46:09+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterthreesectioni?rev=1327967169&do=diff 3.1 Basic Definitions and Applications A graph consists of a collection V of nodes and a collection E of edges, each of which joins two of the nodes. Edges indicate a symmetric relationship between their ends. Directed graphs express asymmetric relationships, and consist of a set of nodes V and a set of directed edges E'. With an ordered pair e'= (u,v) in E', u is called the tail of the edge, and v is head. Graphs serve as important models in several contexts. In transportation networks for ins… text/html 2012-01-31T01:40:23+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterthreesectionii?rev=1327974023&do=diff 3.2 Graph Connectivity and Graph Traversal This section aims at answering the question of if there is a path from a node s to another node t, where s and t are node in a graph G=(V,E). The problem is called “determining s-t connectivity”. Although it can be pretty easy to answer this problem for small graphs, it become more painful for reasonably sized graph. That's why we need a more elegant and efficient way to solve the problem in case we have a fairly big graph. Breadth-First Search and Dep… text/html 2012-01-31T02:48:33+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterthreesectioniii?rev=1327978113&do=diff 3.3Implementing Graph Traversal Using Queues and Stacks A graph can be represented as either an adjacency matrix or an adjacency list. with a graph G = (V,E), the number of nodes |V| is denoted as n and the number of edges |E| is denoted as m. When discussing the representations of graphs, our aim is to get a representation that allows us to implement the graph in a polynomial running time. The number of edges text/html 2012-01-31T03:20:20+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterthreesectioniv?rev=1327980020&do=diff 3.4 Testing Bipartiteness: An Application of Breadth-First Search A bipartite graph is a graph where one node V can be partitioned into sets X and Y in such a way that every edge has an end in X and another end in Y. If we suppose the nodes of X are colored red and the nodes in Y are colored blue, we can say that a graph is bipartite if it is possible to color its nodes red and blue such that every edge has one red end and one blue end. If a graph is bipartite, then it can not contain an odd cy… text/html 2012-01-31T03:49:34+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterthreesectionv?rev=1327981774&do=diff 3.5 Connectivity in Directed Graphs In a directed graph, an edge (u,v) has a direction: from u to v or from v to u. The nodes in these kinds of edges are in asymmetric relations. A World Wide Web is an easy example of a directed graph as one cannot follow the links in reverse order or even the fact that some websites links to other websites which don't necessarily link back to the first websites.In representing directed graphs, each node has two lists associated with it: one list consists of no… text/html 2012-02-21T01:34:37+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapterthreesectionvi?rev=1329788077&do=diff 3.6 Directed Acyclic Graphs and topological Ordering If a directed graph has no cycles, it's called a Directed Acyclic Graph(DAG). DAGS can be used to implement dependencies or precedence relations and are widely used in Computer Science.For instance, we can have a set of tasks {1, 2, 3,…, n} to be performed, the condition being that for certain tasks text/html 2012-01-09T04:25:05+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_eight?rev=1326083105&do=diff Chapter Eight * Section I * Section II * Section III * Section IV text/html 2012-03-13T01:59:43+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_five?rev=1331603983&do=diff Chapter Five * 5.1 A First Recurrence: The Mergesort Algorithm * 5.2 Further Recurrence Relations * 5.3 Counting Inversions * 5.4 Finding the Closest Pair of Points * 5.5. Integer Multiplication text/html 2012-03-06T22:23:45+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_fivesection_i?rev=1331072625&do=diff 5.1 A First Recurrence: The Mergesort Algorithm Divide and conquer algorithms are 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. Analyzing these problems usually involves solving recurrence relation that bounds the running time recursively in terms of the running time on smaller instances. Mergesort uses the same template as other divide… text/html 2012-03-11T23:21:47+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_fivesection_ii?rev=1331508107&do=diff 5.2 Further Recurrence Relations In this section, we are concerned with the generalization of the recurrence relation we saw in the previous section. Indeed, we need to study the cases where we have an algorithm that makes recursive calls on q subproblems of size n/2 and combine the results in O(n) time. text/html 2012-03-12T22:25:37+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_fivesection_iii?rev=1331591137&do=diff 5.3 Counting Inversions Counting inversions is a problem that we face when analyzing rankings in several applications. The main challenge in this category of problems is to find a way to efficiently compare the rankings. Let's suppose we have a sequence of n numbers a text/html 2012-03-13T01:58:40+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_fivesection_iv?rev=1331603920&do=diff 5.4 Finding the Closest Pair of Points The Problem Given n points in the plane,find the pair that is closest together. The brute-force attempt at solving this problem would cost us O(n²) time. Our goal is to find an efficient algorithm that runs in O(nlogn) time. text/html 2012-03-13T02:22:38+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_fivesection_v?rev=1331605358&do=diff 5.5. Integer Multiplication The Problem We need an efficient way to multiply two integers. The widely used algorithm costs O(n²) time. Our goal: improve on this quadratic running time. Designing the Algorithm The basic idea is to break up the product into partial sums. text/html 2012-03-06T03:40:04+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_four?rev=1331005204&do=diff Chapter Four: Greedy Algorithms * 4.0 Greedy Algorithms * 4.1. Interval Scheduling: The Greedy Algorithm Stays Ahead * 4.2. Scheduling to Minimize Lateness: An Exchange Argument * 4.3. Optimal Caching: A More Complex Exchange Argument * 4.4. Shortest paths in a graph * 4.5. The Minimum Spanning Tree Problem * 4.6. Implementing Kruskal's Algorithm: The Union-Find Data Structure * 4.7. Clustering * 4.8 Huffman Codes and Data Compression text/html 2012-01-14T22:08:08+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_one?rev=1326578888&do=diff Chapter One * 1.1 A First Problem: Stable Matching * 1.2 Five Representative Problems text/html 2012-04-02T12:12:10+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_seven?rev=1333368730&do=diff Chapter Seven * 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm * 7.2 Maximum Flows and Minimum Cuts in a Network * 7.5 A First Application: The Bipartite Matching Problem * 7.7 Extensions to the Maximum-Flow Problem text/html 2012-03-28T02:40:45+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_six?rev=1332902445&do=diff Chapter Six * 6.1. Weighted Interval Scheduling: A Recursive Procedure * 6.2. Principles of Dynamic Programming: Memoization or iteration over Subproblems * 6.3. Segmented Least Squares: Multi-way Choices * 6.4 Subset Sums and Knapsacks: Adding a Variable text/html 2012-01-31T03:21:24+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_three?rev=1327980084&do=diff Chapter Three * 3.1 Basic Definitions and Applications * 3.2 Graph Connectivity and Graph Traversal * 3.3Implementing Graph Traversal Using Queues and Stacks * 3.4 Testing Bipartiteness: An Application of Breadth-First Search * 3.5 Connectivity in Directed Graphs * 3.6 Directed Acyclic Graphs and topological Ordering text/html 2012-01-24T03:21:40+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chapter_two?rev=1327375300&do=diff Chapter two * 2.1 Computational Tractability * 2.2 Asymptotic Order of Growth * 2.3 Implementing The Stable Matching Algorithm using Lists and Arrays * 2.4 A survey of Common Running Times * 2.5 A More Complex Data Structure: Priority Queues text/html 2012-01-18T02:47:39+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptter2section2?rev=1326854859&do=diff 2.2 Asymptotic Order of Growth Asymptotic Upper Bounds * Let T(n) be a function(let's assume it is the worst-case running time of a certain algorithm on an input of size n). * Given another function f(n), we say that T(n) is O( f(n)) (T(n) is order text/html 2012-01-23T23:56:53+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptter2section3?rev=1327363013&do=diff 2.3 Implementing The Stable Matching Algorithm using Lists and Arrays To asymptotically analyze the running time of an algorithm, we don't need to implement and run it, but we definitely have to think about how the data will be represented and manipulated in an implementation of the algorithm so we could bound the number of computational steps it takes. This section looks at how to implement the Gale-Shapley algorithm using lists and arrays. In the Stable Matching Problems that the algorithm so… text/html 2012-01-24T23:11:13+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptter2section4?rev=1327446673&do=diff 2.4 A survey of Common Running Times When analyzing algorithms,we need to have an approximate sense of the “landscape” of different running times. Most problems have a natural “search space”,which is the set of all possible solutions.When we say we are looking for an efficient algorithm, our goal is actually that of finding algorithms that are faster than the brute-force enumeration of the search space. Thus we always need to think about two bounds when analyzing algorithms: the one on the natu… text/html 2012-01-26T17:59:14+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/chaptter2section5?rev=1327600754&do=diff A More Complex Data Structure: Priority Queues To qualitatively improve the brute-force algorithms so we can have efficient algorithms, we always need to overcome higher-level obstacles. However, the running time of polynomial-time algorithms can often be further improved through the implementation details and use of more complex data structures. Some of those complex data structures are usually specialized for solving some kind of problems, while we can also find others that are more general i… text/html 2012-01-18T00:50:27+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/home?rev=1326847827&do=diff Jean Paul's Journal * Preface * Chapter One * Chapter Two * Chapter Three * Chapter Four * Chapter Five * Chapter Six * Chapter Seven * Chapter Eight text/html 2012-01-14T21:31:19+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/pagename?rev=1326576679&do=diff 1.1 A First Problem: Stable Matching The Stable matching problem originated in 1962 when two mathematical economists David Gale and Lloyd Shapley asked if one could design a college admissions process,or job recruiting process that was self-enforcing. The goal would be to get a stable outcome where both applicants and recruiters would be happy.To solve the problem, Gale and Shapley simplified it to the problem of devising a system by which each n men and n women can end up getting married. In t… text/html 2012-01-18T01:42:52+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/preface?rev=1326850972&do=diff Preface Algorithms are an important part of the Computer Science field. Not only does the topic of algorithms have many applications,but it also forms the heart of the Computer Science field and provides the means through which to view the Computer Science field as whole.Logarithmic problems are not always mathematically precise, but they rather tend to come in messy forms. Thus when analyzing those algorithmic problems, one has to get to the mathematically clean core of a problem and then iden… text/html 2012-01-14T22:29:06+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/section1?rev=1326580146&do=diff 1.1 A First Problem: Stable Matching The Stable matching problem originated in 1962 when two mathematical economists David Gale and Lloyd Shapley asked if one could design a college admissions process,or job recruiting process that was self-enforcing. The goal would be to get a stable outcome where both applicants and recruiters would be happy.To solve the problem, Gale and Shapley simplified it to the problem of devising a system by which each n men and n women can end up getting married. In t… text/html 2012-01-17T05:02:53+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/section2?rev=1326776573&do=diff 1.2 Five Representative Problems The five representative problems are cleanly formulated problems encountered very often in the study of algorithms,all resembling one another at a general level but differing greatly in their difficulty and in the kinds of approaches taken to solve them. They are all motivated by computing applications. To talk about these problems,the terminology of graphs is used. A graph G consists of a pair of sets (V,E)-a collection of V nodes and a collection of E edges, e… text/html 2012-01-14T21:34:34+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/jeanpaul/sectioni?rev=1326576874&do=diff 1.1 A First Problem: Stable Matching The Stable matching problem originated in 1962 when two mathematical economists David Gale and Lloyd Shapley asked if one could design a college admissions process,or job recruiting process that was self-enforcing. The goal would be to get a stable outcome where both applicants and recruiters would be happy.To solve the problem, Gale and Shapley simplified it to the problem of devising a system by which each n men and n women can end up getting married. In t…