http://servo.ad.wlu.edu/dokuwiki/ 2026-04-25T09:56:38+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-02-04T16:50:54+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/chapter_1?rev=1296838254&do=diff Chapter 1: Introduction: Some Representative Problems 1.1 Stable Matching The Stable Matching Problem is based on the question: Could one design a process(college application or job recruiting, for example) that is self-enforcing? A simplified version of this problem is a situation trying to match n men with n women, taking into account their preferences. A perfect matching is is a matching in which each man and woman appears in exactly one pairing. An instability in a matching is when a ma… text/html 2011-02-04T16:54:04+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/chapter_2?rev=1296838444&do=diff Chapter 2: Basics of Algorithm Analysis 2.1 Computational Tractability This book puts a lot of emphasis on explaining their approaches to problems. I definitely think this is beneficial because it helps me see the overall goals and processes. This section starts with a basic definition of efficiency, simply that an algorithm is efficient if it runs quickly on real input instances. This definition lacks specifics and a way to quantify how to determine how fast is fast enough. Our final defi… text/html 2011-02-15T23:02:32+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/chapter_3?rev=1297810952&do=diff Chapter 3: Graphs 3.1 Basic Definitions and Applications This section simply introduces graphs and some basic terminology that is related to them. This section is pretty much review from CS112, but there are definitely a few important concepts that it is helpful to review and remember. Graphs are incredibly useful data structures, especially for modeling a variety of networks, such as social or communication networks. text/html 2011-03-02T03:48:58+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/chapter_4?rev=1299037738&do=diff Chapter 4: Greedy Algorithms An greedy algorithm is accurate to its name. It builds up a solution greedily, by choosing a decision at each step that optimizes the solution at that point. While greedy algorithms can be designed for many problems, the ones we want to concern ourselves with are the ones that have optimal greedy solutions. Thus, most of this chapter will be concerned with constructing a greedy algorithm and then proving it is optimal, using either the text/html 2011-03-15T14:22:53+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/chapter_5?rev=1300198973&do=diff Chapter 5: Divide and Conquer This chapter covers divide and conquer algorithms, which aim to break up a problem into several parts, solve them recursively, and then combine the solutions to the subproblems. The idea is to reduce a brute-force algorithm, with is often polynomial time, to a divide and conquer algorithm that is has a lower polynomial running time. Analysing this running time depends on the recurrence relationship, we which will learn about in this chapter. Divide and conquer a… text/html 2011-04-02T21:52:32+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/chapter_6?rev=1301781152&do=diff Chapter 6: Dynamic Programming This chapter is about dynamic programming, which is a more powerful approach than greedy or divide and conquer methods. The basic idea is kind of the opposite of greedy approach. You explore all possible solutions to a problem but breaking a problem up into subproblems, the building up the correct solution into larger subproblems. This may seem to be close to brute-force, but it is not because of the way it explores the possible solutions. It never explicitly … text/html 2011-04-02T22:22:29+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/chapter_7?rev=1301782949&do=diff Chapter 7: Network Flow This chapter is about a set of problems that grow from the Bipartite Matching Problem we talked about earlier. We can use this algorithm/idea to develop a general set of problems about traffic flow on networks. 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm text/html 2011-04-02T21:53:02+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/home?rev=1301781182&do=diff Anna's Journal Preface Chapter 1: Introduction - Some Representative Problems 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 2011-02-04T16:50:08+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/preface?rev=1296838208&do=diff Preface The preface of Algorithm Design by Kleinburg and Tardos gives a very clear introduction to the importance of algorithms, the goals of the book, and the layout and useful parts of the book. Algorithms are the basis for all computer science, but they are often complicated and messy. Thus, there are two important components to this book. The authors strive to teach us(students) how to get to the center of a confusing or complicated problem and then to identify the algorithm design techn… text/html 2011-02-08T02:07:14+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/anna/sidebar?rev=1297130834&do=diff Anna's Journal * Chapter 1: Introduction: Some Representative Problems CSCI 211: Algorithm Design and Analysis