http://servo.ad.wlu.edu/dokuwiki/ 2026-04-17T11:53:10+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-19T15:36:50+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter1?rev=1295451410&do=diff Chapter 1 Chpater 1 - Intro: Some Representative Problems First the chapter provides an example of the problem and highlights the crucial issues of the problem that would need to be specifically solved in an algorithm. Next it goes into the engagement problem, explaining each element of the problem, such as the initial state, defining stability and perfect matching, and analysing the algorithm once finished. Next the chapter goes over five basic representative problems that often appear in algo… text/html 2011-01-26T14:07:03+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter2.2?rev=1296050823&do=diff Section 2.3: In this section of the chapter the book explains arrays and lists and how they can be used to manipulate data. It also discusses the differences in run times for functions. For example, a list has constant time to “find” and element, has linear time to check if an element belongs in the list or logn time if the list is already sorted. However, an array has a pointer to the first element (and possibly the last) therefore it is constant to insert or remove an element but it takes line… text/html 2011-01-19T15:36:08+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter2?rev=1295451368&do=diff Chapter Two Chapter 2.1 and 2.2 In section 2.1 the chapter defines and discusses the importance of efficiency. It goes through three different definitions of an efficient algorithm, highlighting its strengths and flaws. It also goes over worst-case running time and brute force searches, and how worst-case running time gives an accurate capturing of the efficiency of a problem. In section 2.2, the chapter directly goes deeper into defining the running-time of a problem, such as the asymptotic up… text/html 2011-03-02T20:16:14+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter4?rev=1299096974&do=diff Section 4.5 Section 4.5 discusses Minimum Spanning Tree and the efficiencies of their algorithms. A mimimum spanning tree by definition is a tree that connects all the nodes with an edge, without creating any cycles, and has the least cost of building this tree. To produce a mim spanning tree with use greedy algorithm, and the three simple ones the book discusses, which all of them create a MST, are Kruskal's Algorithm, Prim's Algorithm, and the last is Reverse-Delete Algorithm. Both Kruskal's a… text/html 2011-03-30T16:11:10+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter6?rev=1301501470&do=diff Section 6.4 - Subset Sums and Knapsacks: Adding a Variable In this section we look at the Knapsack problem where there are n items and each is given a weight wi, and each request i has a value vi and weight wi. Thus the problem is to make the knapsack as full as possible (with max capcity of W). This problem is similar to the Weighted-Interval Problem because as in W-I-P, the key to the problem is that the item is either included in the sack or not. For this problem, we don't include item n whe… text/html 2011-02-02T07:01:20+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter_3?rev=1296630080&do=diff Chapter 3 covers one of the most fundamental combinational structures, graphs. 3.1 - In this section, the books defines a graph as a collection of nodes (V) and a collection of edges (E) such that an edge joins two nodes. In order to construct an asymmetrical graph we construct a directed graph such that G' consists of a set of nodes V and set of directed edges E', where an edge (u,v) would be an edge that goes from node u to node v (but not necessarily the reverse). But by default, a graph is… text/html 2011-02-16T06:39:57+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter_4?rev=1297838397&do=diff Section 3.6 - Directred Acyclic Graphs and Topological Ordering. In the last section of Chapter 3, the book discusses DAGs and Topological Ordering. By definition, a directed graph that does not have any cycles in a directed acyclic graph. DAGs are used to solve problems of precedence relations or dependencies. By having a set of tasks labeled 1 through n that include dependencies such as a pair of i and j shows that i must be performed before j. We represent this graph by setting each task to … text/html 2011-03-09T17:05:34+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter_5?rev=1299690334&do=diff Section 5.4 Section 5.4 looks at the closest pair problem, where the user is trying to find the pair of closest points within a graph. There is an obvious O(n-squared) solution of computing all the distances between neighboring point and finding the max. But there are other algorithms to solve this problem that do not use O(n-squared time). The section proposes a divide and conquer algorithm. Where we find the middle of the graph, draw a line so that half the points lie on one side and half on t… text/html 2011-03-16T16:21:19+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter_6?rev=1300292479&do=diff Section 5.5 Section 5.5 looks at integer multiplication, and how divide and conquer can be used to solve it. The algorithm students learn in elementary school (a.k.a. adding up the partial solutions) has a run time of O(n-aquared) becuase it takes O(n) to compute the partial product and there are n partial products. A better solution is found in this section by breaking down the product into further partail sums. One option is to recursively compute the results for four n/2 bit instances, and t… text/html 2011-04-06T06:20:03+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/chapter_7?rev=1302070803&do=diff Section 6.9 Shortest Paths and Distance Vector Protocols The Shortest Paths Problem looks at a routers in a network and wants to find the most efficient path to a destination. We use the cost of a delay (Cvw) on link (v,w) to determine the minimum delay from a source node s to a destination node t. However, in this problem we cannot simply use Dijkstra's Algotithm because we don't have global knowledge of the network. It is actually better to use local knowledge. To solve we use the Bellman Fo… text/html 2011-04-06T04:36:48+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/home?rev=1302064608&do=diff Ashley's Journal Preface Chapter 1 Chapter 2 Chapter 2.3-2.5 Chapter 3.1-3.5 Section 3.6 and Chapter 4 (4, 4.1, 4.2, 4.4) Chapter 4 (4.5, 4.6, 4.7, 4.8) Chapter 5 (5.4 5.5) Chapter 6 (5.5, 6, 6.1-6.4) Chapter 6 (6.4, 6.5, 6.6, 6.7, 6.8) Chapter 6.9-7.3 text/html 2011-01-19T15:37:22+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/ashley/preface?rev=1295451442&do=diff Preface Preface - The Preface of the book initially looks at why algorithm analysis is important and that tactics people use to solve these problems. It labels two fundamental components of algorithms, first eh task of getting to the mathematical core of a problem, and second the task of identifying the appropriate algorithm design techniques. The rest of the chapter outlines that content of the book starting with the explaining the importance of the exercises in the back. The rest of the prefa…