http://servo.ad.wlu.edu/dokuwiki/ 2026-04-22T11:23:08+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-31T02:47:05+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/chapter1?rev=1296442025&do=diff Chapter 1: Introduction Section 1: Stable Matching * Summary: This section discusses the stable matching problem. This problem was introduced in 1962 to solve/think about the matching process of students to schools in the college admissions process. It can also help solve other matching problems like patients to hospitals, and applicants to jobs or internships. According to our text book, an unstable matching means two people/groups (ex. a university and a student) could agree to make swit… text/html 2011-01-31T02:47:47+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/chapter2?rev=1296442067&do=diff Chapter 2: Basics Section 1: Computational Tractability * Summary: This section is about the importance of finding efficient algorithms and what it means for an algorithm to be efficient. This book focuses on time efficiency, but also notes that efficient use of space (memory) is also important. We want a definition of efficiency that is platform-independent, instance-independent, and able to predict how the running time changes with increasing input sizes. When we analyze the running time… text/html 2011-02-12T14:28:58+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/chapter3?rev=1297520938&do=diff Chapter 3: Graphs Section 1: Basic Definitions and Applications * Summary: Graphs are useful in discrete math, and they show up EVERYWHERE if you're looking at things that way! A graph (a.k.a. Undirected Graph) consists of a collection V of nodes (a.k.a. vertexes) and a collection E of edges (each edge joins two nodes and is represented by a two-element subset of V). Edges indicate a symmetric relationship. Directed graphs have asymmetric relationships (directed edges represented by ordere… text/html 2011-02-21T23:00:59+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/chapter4?rev=1298329259&do=diff Chapter 4: Greedy Algorithms Section 1: Interval Scheduling: The Greedy Algorithm Stays Ahead * Summary: Sometimes greed works. An algorithm is greed if it builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion. When algorithms work to give an optimal or almost optimal solution, it says something about the problem's underlying structure. Problem: how to find cases where greedy works and prove that it works. First way: greedy s… text/html 2011-03-13T22:18:02+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/chapter5?rev=1300054682&do=diff Chapter 5: Divide and Conquer Section 1: A First Recurrence: The Mergesort Algorithm * Summary: Divide and conquer - break the input into several parts, solve the problem in each part recursively, combine the solutions to the subproblems into an overall solution. Recurrence relations are necessary to discuss the running time of these algorithms. These algorithms might not improve running time as much as in the previous section (because they're reducing the degree of a polynomial running ti… text/html 2011-04-03T00:40:01+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/chapter6?rev=1301791201&do=diff Chapter 6: Dynamic Programming Intro * Summary: There isn't always a Greedy Algorithm or a Divide and Conquer Algorithm to solve a problem efficiently. Dynamic programming is a faster and more subtle technique. “...the basic idea is drawn from the intuition of divide and conquer and is essentially the opposite of the greedy strategy: one implicitly explores the space of all of the possible solutions, by carefully decomposing things into a series of subproblems, and then building up correct … text/html 2011-04-05T04:39:54+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/chapter7?rev=1301978394&do=diff Section 1: The Max-Flow Problem and the Ford-Fulkerson Algorithm * Summary: This chapter goes back to the bipartite matching problem from the beginning of the term. One problem is to determine the size of the largest matching in a bipartite graph, which needs new techniques to solve. They develop a new class of problems - network flow problems - that include bipartite matching as a special case. They develop a polynomial-time algorithm for the Maximum-Flow Problem and show how it works for … text/html 2011-04-08T03:23:17+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/home?rev=1302232997&do=diff Camille's Journal * Preface * Chapter 1: Introduction * Chapter 2: Basics * Chapter 3: Graphs * Chapter 4: Greedy Algorithms * Chapter 5: Divide and Conquer * Chapter 6: Dynamic Programming * Chapter 7: Network Flow * The P versus NP Problem text/html 2011-04-08T03:33:30+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/npproblem?rev=1302233610&do=diff The Status of the P versus NP Problem * Overview: The P versus NP problem is still open. It seems like there is not a polynomial time solution to these problems, but this hasn't been proven. Either way (whether there is a polynomial time solution or not), there would be major implications to our world. text/html 2011-01-18T15:49:29+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2011/journals/camille/preface?rev=1295365769&do=diff Preface * Summary: Algorithms are important because all kinds of problems (both in computer science and outside of computer science) can be modeled as algorith problems/solved using algorithms. Deeper than that, algorithms provide a language for expressing problems and a way to make the problems/solutions clean and precise. There are two steps/components to algorithms: getting to the