http://cswiki.wlu.edu/dokuwiki/ 2026-04-13T12:11:55+00:00 http://cswiki.wlu.edu/dokuwiki/ http://cswiki.wlu.edu/dokuwiki/lib/exe/fetch.php/wiki/dokuwiki-128.png text/html 2014-01-20T21:47:45+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/chapter1?rev=1390254465&do=diff Chapter 1: Introduction Section 1.1 : A First Problem: Stable Matching Stable matching is an algorithm that solves the classic problem of creating pairs from two parties, both with their own preferences, in such a way that no pair would leave their current partners for each other. This problem can apply to applicants applying for positions with a set of companies, the college application process, or groups of men and women. The Gale-Shapely algorithm was developed by David Gale and Lloyd Shape… text/html 2014-01-20T22:35:11+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/chapter2?rev=1390257311&do=diff Chapter 2: Basics of Algorithm Analysis Section 2.1: Computational Tractability This section tries to formulate a definition for efficiency. It outlines that we cannot simply define efficiency as speed, because even bad algorithms run quickly on fast computers or when they are run with only small test cases. When looking at efficiency we look at the worst-case scenario as best-case is not particularly realistic and average-case analysis does not really help us look at how the algorithm works a… text/html 2014-02-10T18:50:40+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/chapter3?rev=1392058240&do=diff Chapter 3: Graphs 3.1: Basic Definitions and Applications A graph is a data structure used to represent relationship pairs in a group of objects. Graphs can be used to represent transportation networks, like where flights go to/come from in regards to an airport, communication networks, like data sharing between computers, information networks, like how the links on a particular website work, social networks, such as Facebook, and finally, graphs can represent dependency networks, which can re… text/html 2014-03-03T21:10:58+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/chapter4?rev=1393881058&do=diff Chapter 4: Greedy Algorithms A greedy algorithm creates a solution by making the optimal choice at a local level in the hopes of creating a solution that is globally optimal. The easiest example of this is giving change in the way that uses the least amount of coins. There are several ways to prove that the greedy solution is the optimal solution. The two this chapter discusses are greedy stays ahead and exchange (swappy). The motivation by the greedy algorithm is to solve a non-trivial problem… text/html 2014-03-12T01:47:43+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/chapter5?rev=1394588863&do=diff Chapter 5: Divide and Conquer Divide and conquer algorithms break the problem into smaller sections, solve those sections, and then put the sections back together. This is done in the hopes that we will be able to reduce the run time of the algorithm. text/html 2014-03-25T04:59:24+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/chapter6?rev=1395723564&do=diff Chapter 6: Dynamic Programming Section 6.1: Weighted Interval Scheduling: A Recursive Procedure The weighted interval scheduling problem is a generalized version of the interval scheduling problem where each of the intervals has a certain value and we are trying to maximize the value of the set. To create this set of intervals with maximum value we first design a recursive solution. First, we sort the intervals in order of nondecreasing finish time and define p(j) to be the largest index i< j … text/html 2014-04-02T04:43:08+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/chapter7?rev=1396413788&do=diff Chapter 7: Network Flow Section 7.1: The Maximum-Flow Problem and the Ford-Fulkerson Algorithm Graphs are used to model transportation networks, which are networks whose edges carry traffic and whose nodes act as “switches” to pass the traffic. Each edge has a capacity, a specified amount that they can carry, and there are source and sink nodes which direct the flow of traffic. A flow network is a graph with non-negative edges, that has a single source node s and a single sink node t. Furtherm… text/html 2014-03-30T22:36:13+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/home?rev=1396218973&do=diff Shannon's Journal Preface Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 text/html 2014-01-15T01:07:17+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/preface?rev=1389748037&do=diff Preface The first two pages of the preface provided a quick overview of what algorithms are and how the book would be approaching the discussion of algorithms. It discussed how algorithms are more than sets of steps to solve problems and are instead a way to view computer science. It mentioned how algorithms are not always neat and straightforward but rather require a lot of complex thinking. Finally the preface outlined the books goal: viewing algorithms as a design process during which we ide… text/html 2014-01-15T01:16:27+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/section1?rev=1389748587&do=diff Section 1.1 : A First Problem: Stable Matching Stable matching is an algorithm that solves the classic problem of creating pairs from two parties, both with their own preferences, in such a way that no pair would leave their current partners for each other. This problem can apply to applicants applying for positions with a set of companies, the college application process, or groups of men and women. The Gale-Shapely algorithm was developed by David Gale and Lloyd Shapely to solve this problem.… text/html 2014-01-15T02:29:41+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/section21?rev=1389752981&do=diff Section 2.1: Computational Tractability This section tries to formulate a definition for efficiency. It outlines that we cannot simply define efficiency as speed, because even bad algorithms run quickly on fast computers or when they are run with only small test cases. When looking at efficiency we look at the worst-case scenario as best-case is not particularly realistic and average-case analysis does not really help us look at how the algorithm works and instead looks at how the input is gene… text/html 2014-01-15T03:06:34+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/section22?rev=1389755194&do=diff Section 2.2: Asymptotic Order of Growth Bounds of runtime functions are the “worst-case” scenarios that an algorithms runtime is bounded by. A bound can be an upper bound, which is denoted O(f(n)), a lower bound, which is denoted Ω(F(n)), or a tight bound, which is denoted Θ(f(n)). An upper bound occurs when the algorithm’s function is bounded above by a multiple of f(n). A lower bound occurs when the algorithm’s function is less greater than f(n) times some constant. Finally a tight bound occu… text/html 2014-03-30T23:27:23+00:00 Anonymous (anonymous@undisclosed.example.com) http://cswiki.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/shannon/sidebar?rev=1396222043&do=diff Shannon's Sidebar Shannon's Journal * Preface * Chapter 1: Introduction * 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 ---- <- CSCI 211: Algorithm Design and Analysis