http://servo.ad.wlu.edu/dokuwiki/ 2026-04-19T19:06:42+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-23T21:38:08+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/chapter1?rev=1327354688&do=diff Chapter 1 Section 1: Stable Matching In this section, our goal is to find an algorithm that generates a perfect, stable matching between n men and n women. The Gale-Shapley algorithm accomplishes this. Algorithm outline (p 6): Pick a random man and have him propose to his top choice who he has not yet proposed to. This woman will accept if single or if this man is preferred to her current mate. Otherwise he remains single. Repeat this until every man is engaged or has proposed to every wo… text/html 2012-01-25T01:53:48+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/chapter2?rev=1327456428&do=diff Chapter 2 This chapter explains how to analyze algorithms by measuring how their resource requirements scale with increasing input size. Section 1: Computational Tractability We want to find efficient algorithms, but what does efficient mean? We need to be more specific than just saying it runs fast or its better than brute-force search so we will consider an algorithm efficient if it has a polynomial worst-case running time. This means that for an input of size N, the worst-case running ti… text/html 2012-02-16T03:06:50+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/chapter3?rev=1329361610&do=diff Chapter 3 This chapter introduces basic graph definitions and algorithms. Section 1: Basic Definitions and Applications A graph consists of a collection of nodes (V) and edges (E). Directed graphs have “one-way” edges to indicate asymmetric relationships while text/html 2012-03-06T16:01:39+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/chapter4?rev=1331049699&do=diff Chapter 4 A greedy algorithm is one that builds up a solution in small steps to optimize something. We will use greedy algorithms for many problems including the shortest path problem, the Minimum Spanning Tree problem and others. There are two main proof techniques for showing a greedy algorithm works: the greedy stays ahead proof and the exchange argument. text/html 2012-03-14T03:28:17+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/chapter5?rev=1331695697&do=diff Chapter 5 Divide and conquer algorithms are algorithms that break the input into parts, solve the parts recursively, and then combine the solutions. When analyzing them, we will often look at recurrence relations, recursive functions that bound the running time of the algorithm. text/html 2012-03-26T04:53:00+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/chapter6?rev=1332737580&do=diff Chapter 6 In dynamic programming, we solve problems by finding a way to decompose them into subproblems that we can then use to build a solution. Section 1: Weighted Interval Scheduling: A Recursive Procedure In this section, we look to solve the weighted interval scheduling problem using dynamic programming. In this problem, our goal is to maximize the value of the intervals we schedule. The key to this problem is recognizing that each interval is either in the optimal solution, or it … text/html 2012-04-04T02:59:13+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/chapter7?rev=1333508353&do=diff Chapter 7: Network Flow In this chapter, we discuss network flow algorithms. Section 1: The Maximum Flow Problem and the Ford-Fulkerson Algorithm We can use graphs to model flow networks. In these networks, edges have certain capacities that indicate the maximum flow allowed over that edge and nodes represent interchanges that direct the flow to some edge. A source node (s) generates flow, a sink node (t) absorbs it, and all other nodes redirect the flow so that the amount of flow into it i… text/html 2012-04-03T23:14:03+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/home?rev=1333494843&do=diff Virginia'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 text/html 2012-01-16T03:44:23+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/preface?rev=1326685463&do=diff Preface Algorithms have applications in many fields. In computer science, studying algorithms can give us a different way to view and solve problems by encouraging us to think about the underlying structure and identify an appropriate algorithm design for each problem. text/html 2012-04-04T02:59:38+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2012/journals/virginia/sidebar?rev=1333508378&do=diff Virginia's Journal Home * 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 <-Course Wiki Page