http://servo.ad.wlu.edu/dokuwiki/ 2026-04-16T23:59:01+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-13T16:40:07+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/chapter_0?rev=1294936807&do=diff Preface My notes on Preface Brief Summary * The idea of algorithms are pervasive, its applications can be found in just about every discipline. * the subject of algorithms is a powerful lens through which to view the field of computer science in general. text/html 2011-01-19T04:46:09+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/chapter_1?rev=1295412369&do=diff Chapter 1 My notes on Chapter 1 readings 1.1: Stable Matching Problem Brief Summary This sections talks about the origination of the matching problem and the real-life implications such problem can have. A stable, self-enforcing matching system has to be established in order to have everyone’s self-interest prevent offers from being retracted or redirected. The section then shows an algorithm that produces stable matching and shows a proof of the effectiveness of the algorithm. text/html 2011-01-25T01:52:16+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/chapter_2?rev=1295920336&do=diff Chapter 2 2.1 Computational Tractability Summary The author talks about why worst-case approach the complexity is used rather than its seemingly attractive alternative---average performance. It is hard to define what random input should we generate to evaluate the complexity. text/html 2011-02-16T12:33:29+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/chapter_3?rev=1297859609&do=diff 3.1 Basic Definitions and Application The summary Motivation of a graph: easy in representing pair-wise relationships within a system. Definition of a graph (categories: undirected and directed) A graph consists of a number of nodes and edges. Edges in a graph indicate a symmetric relationship between their ends. Often we want to encode asymmetric relationships, and for this we use the closely related notion of a directed graph. Some example applications of the graph: • Transportation network… text/html 2011-03-02T03:13:35+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/chapter_4?rev=1299035615&do=diff Chapter 4 definition of Greedy agorithm: An algorithm is greedy if it builds up a solution in sma!l steps, choosing a decision at each step myopically to optimize some underlying criterion. OR Finding the best step locally. 4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead text/html 2011-03-14T04:13:09+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/chapter_5?rev=1300075989&do=diff Overview definition:P234 Divide and conquer refers to a class of algorithmic techniques in which one breaks the input into several parts, solves the problem ifi each part recursively, and then combines the solutions to these subproblems into an overall solution text/html 2011-04-06T16:41:26+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/chapter_6?rev=1302108086&do=diff Overview A good recap before moving on: Algorithmic Paradigms • Greedy. Build up a solution incrementally, myopically optimizing some local criterion • Divide-and-conquer. Break up a problem into sub-problems, solve each sub-problem independently text/html 2011-04-06T20:59:22+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/chapter_7?rev=1302123562&do=diff 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm The Problem Motivation: A few concepts: to model transportation networks--networks whose edges carry some sort of traffic and whose nodes act as “switches” passing traffic between different edges. Network models of this type have several ingredients: text/html 2011-04-06T16:43:46+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/chen/home?rev=1302108226&do=diff Chen's Journal * Preface * Chapter 1: Introduction * Chapter 2: Algorithm Analysis * Chapter 3: Graphs * Chapter 4: Greedy Algorithms * Chapter 5: Divide artd Cortquer * Chapter 6: Dynamic programming * Chapter 6: Network Flow