https://cswiki.wlu.edu/dokuwiki/ 2026-05-31T22:42:11+00:00 https://cswiki.wlu.edu/dokuwiki/ https://cswiki.wlu.edu/dokuwiki/lib/exe/fetch.php/wiki/dokuwiki-128.png text/html 2018-01-19T03:48:55+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/chapter1?rev=1516333735&do=diff Chapter 1 Section 1.1 A First Problem: Stable Matching Section 1.1 begins with an introduction of the Stable Matching Problem. The motivation behind this problem is to create a self-enforcing matching process, where the self interests of two given parties prevent matched pairs from being retracted and redirected. The authors explain this problem through the context of applicants seeking summer internships with certain employers. Given E employers and A applicants, as well as a list of preferen… text/html 2018-01-30T00:00:00+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/chapter2?rev=1517270400&do=diff Chapter 2 Section 2.1 Computational Tractability The authors begin by stating the importance of efficient and discrete algorithms. The authors then attempt to define the term efficiency, concluding that a concrete definition of efficiency is “platform-independent, instance-independent, and of predictive value with respect to increasing size. text/html 2018-02-07T02:17:31+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/chapter3?rev=1517969851&do=diff Chapter 3 3.1 Basic Definitions and Applications A graph is a collection of V nodes and E edges where an edge e is represented as a two-element subset {u, v}. Directed graphs represent an edge e in ordered pairs (u, v), which are not interchangeable. An undirected graph is essentially a default graph. Examples of graphs include transportation, communication, information(e.g. world wide web), social, and dependency networks. An important operation in graphs is traversing a sequence of nodes con… text/html 2018-03-11T21:59:40+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/chapter4?rev=1520805580&do=diff Chapter 4 4.1 Interval Scheduling The motivation for interval scheduling is to schedule as many jobs as possible with no overlap between the intervals of time for each job. When designing a greedy algorithm for this problem, we base the algorithm on one simple rule; e.g. selecting jobs that start the earliest, or jobs with smallest interval times. In this problem, the simple rule that produces an optimal solution is selecting jobs that finish the earliest. The greedy algorithm looks like such: text/html 2018-03-12T21:39:07+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/chapter5?rev=1520890747&do=diff Chapter 5 5.1 Mergesort Mergesort's behavior can be described as dividing the input into two halves, solving each half separately by recursion, and then combining the two results into an overall solution. So, it takes O(n) time dividing the input in half, T(n/2) time to solve each half, then O(n) time to combine the two solutions back together. Thus, the recurrence relation is 2T(n/2) + O(n). This itself is not a run time, however. In order to determine the run time of an algorithm from a recu… text/html 2018-03-27T01:05:24+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/chapter6?rev=1522112724&do=diff Chapter 6 6.1 Weighted Interval Scheduling The problem is similar to our previous Interval Scheduling problem with the added case that jobs now have different weights; thus, no greedy algorithm can be used to solve this problem, so we must switch to dynamic programming. More specifically, we use a recursive algorithm. The algorithm relies on a simple observation: for any job j, we wither pick j or we do not pick j. This observation helps formulate the recursive case: text/html 2018-04-03T03:13:32+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/chapter7?rev=1522725212&do=diff Chapter 7 7.1 Ford-Fulkerson Algorithm For our purposes, we define a flow network as a graph G with a source node s and a sink node t with each edge e having a non-negative capacity ce. There are also two important conditions: the capacity condition and the conservation condition. The capacity condition restricts a flow of an edge to be less than or equal to its capacity. The conservation condition assures that, with the exception of the source and sink nodes, the flow into a node v equals the… text/html 2018-04-02T13:56:28+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/home?rev=1522677388&do=diff Mark's Wiki * Preface: First two pages * Chapter 1: Section 1.1 * Chapter 2: Sections 2.1-2.5 * Chapter 3: Sections 3.1-3.6 * Chapter 4: Sections 4.1, 4.2, 4.4-4.8 * Chapter 5: Sections 5.1-5.3 * Chapter 6: Sections 6.1-6.3 * Chapter 7: Sections 7.1-7.2, 7.5, 7.7 text/html 2018-01-16T19:06:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/preface?rev=1516129613&do=diff Preface: First two pages The authors begin by stating the prevalence of algorithms and algorithmic ideas across a variety of fields, including biology, economics, and, most importantly, computer science. Although not exclusive to computer science, algorithmic problems form the heart of this field of study. Additionally, the authors explain that this core of computer science can be divided into two fundamental components: understanding the pure mathematics of a problem, and then, based on the pr… text/html 2018-04-19T02:42:43+00:00 Anonymous (anonymous@undisclosed.example.com) https://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2018/journals/donohuem/sidebar?rev=1524105763&do=diff Mark's Wiki * Preface: First two pages * Chapter 1: Section 1.1 * Chapter 2: Sections 2.1-2.5 * Chapter 3: Sections 3.1-3.6 * Chapter 4: Sections 4.1, 4.2, 4.4-4.8 * Chapter 5: Sections 5.1-5.3 * Chapter 6: Sections 6.1-6.3 * Chapter 7: Sections 7.1-7.2, 7.5, 7.7 ---------- <- Mark's Wiki <- CSCI 211: Algorithm Design and Analysis