http://servo.ad.wlu.edu/dokuwiki/ 2026-05-15T12:58:54+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-19T00:59:36+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/chapter1?rev=1295398776&do=diff Chapter 1 - Introduction: Some Representative Problems 1.1 - A First Problem: Stable Matching The stable matching problem deals with creating a self-reinforcing selection process. There are two groups, and all the members of each group has a preference profile that lists ranks all members of the other group in order of who that member would like to be matched with. The solution should be self-reinforcing, meaning that members not paired together have no desire to change their matching after th… text/html 2011-01-25T20:53:00+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/chapter2?rev=1295988780&do=diff Chapter 2 - Basics of Algorithm Analysis We have to think about how much time and how much space an algorithm will use as the size of its input(s) increases. 2.1 - Computational Tractability Many problems involve searching through a large number of possibilities, and the algorithm is supposed to find a solution more quickly than just searching through all theoretical possibilities. A basic definition of efficiency is as follows: text/html 2011-02-15T01:12:33+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/chapter3?rev=1297732353&do=diff Chapter 3 - Graphs 3.1 - Basic Definitions and Applications A graph allows us to encode pairwise relationships among a set of nodes. Each graph has both a set of nodes and a set of edges. Each edge connects two nodes. For a directed graph, it is important to note the direction of the edge in a ordered pair with the first node listed being the node that points to the second node listed. There are many examples of graphs. We can use graphs to model a transportation network, with nodes representi… text/html 2011-02-16T06:31:00+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/chapter4?rev=1297837860&do=diff Chapter 4 - Greedy Algorithms A greedy algorithm uses small steps to formulate its solution. In each step, a decision is made to optimize the solution at that step. A greedy algorithm tells use that there is some rule we can use to make small decisions that will ultimately lead us to an optimal solution. Sometimes, greedy algorithms produce solutions that are close to optimal, but not quite optimal. A greedy algorithm works by staying ahead of the optimal solution at each step. There is also th… text/html 2011-03-09T04:18:37+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/chapter5?rev=1299644317&do=diff Chapter 5 - Divide and Conquer For a divide and conquer algorithm, we break the input into several parts and solve each part recursively. We then combine all solutions into an overall solution. To figure out the running time of a divide and conquer algorithm, we look at the recurrence relation, which is based on the number of times we recursively call the algorithm. Generally for a divide and conquer algorithm, the brute force method will run in some polynomial time, and the divide and conquer … text/html 2011-04-06T03:26:24+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/chapter6?rev=1302060384&do=diff Chapter 6 - Dynamic Programming While we have seen cases where greedy algorithms can work, there are cases such that no greedy algorithm will work for a problem. Divide and conquer is another approach that we can use, but it is difficult to get from a problem with an exponential brute force solution to one with polynomial time. Dynamic programming involves dividing a problem into smaller and smaller subproblems, and then text/html 2011-04-06T04:51:48+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/chapter7?rev=1302065508&do=diff Chapter 7 - Network Flow Network flow stems from our original Bipartite Matching problem. This problem can model situations where objects need to be matched and when we need collections of pairs. We could also look for the largest matching set. 7.1 - The Maximum-Flow Problem and the Ford-Fulkerson Algorithm text/html 2011-04-06T03:28:30+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/home?rev=1302060510&do=diff David's Journal * Preface * Chapter 1 - Introduction: Some Representative Problems * 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 text/html 2011-01-18T02:11:28+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/david/preface?rev=1295316688&do=diff Preface Algorithms are used in Internet routing standards, biology, and economics. Algorithms are the crux of Computer Science, but they often get mixed in with the code. The purely mathematical algorithm is important for our study. We must look out how problems are formulated, and how we can use algorithms to solve them. It is necessary to find the actual question for which our algorithm must answer.