http://servo.ad.wlu.edu/dokuwiki/ 2026-04-16T17:34:20+00:00 http://servo.ad.wlu.edu/dokuwiki/ http://servo.ad.wlu.edu/dokuwiki/lib/exe/fetch.php/wiki/dokuwiki-128.png text/html 2014-01-21T04:45:22+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/1.1_the_stable-matching_process?rev=1390279522&do=diff 1.1 The stable-matching process. This problem arose in 1962 when Gale and Shapley, two mathematical economists, asked them selves if it was possible to design a self-enforcing college admissions process or job recruiting process. The motivation to this problem came from a story Gale and Shapley had recently read in the New Yorker about the intricacies of the college admissions process (Gale, 2001). Gale and Shapley suggested a mechanism to enforce the status quo to ensure the process does not c… text/html 2014-01-21T04:48:18+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/2.1_basics_of_algorithm_analysis?rev=1390279698&do=diff Analyzing algorithms involves thinking about how their resource requirements (amount of time and space they use) will scale with increasing input size. Computational tractability Finding efficient algorithms We shall concentrate on paradigmatic problems (models), and approaches with minimum irrelevant detail to design efficient algorithms. Most of these problems we are going to study are discrete, meaning they involve an implicit search over a large set of combinatorial possibilities. Our main c… text/html 2014-01-21T04:44:05+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/2.2_bounds?rev=1390279445&do=diff Instead of counting the steps (number of instructions)in an algorithm, we shall find a more meaningful and tireless way of finding the running time of an algorithm. We shall then use bounds to understand generally the working time range of an algorithm. Asymptotic Upper bounds. T(n) is our function, f(n) is another given function. T(n) can be expressed as f(n) i.e T(n) is order of f(n) if for sufficiently large input size N, T(n) is bounded above by c.f(n) where c>0. This means T(n)⇐=c.f(n) (T i… text/html 2014-01-21T22:06:59+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/2.3_implementing_the_stable_matching_algorithm_using_lists_and_arrays?rev=1390342019&do=diff We have to think about how the data will be represented and manipulated in an implementation of the algorithm in order to analyze the running time of an algorithm expressed in a high-level fashion. Keep in mind: G-S algorithm terminates in at most (n^2) iterations, and our implementation provides a corresponding worst-case running time of O(n^2), counting actual computational steps rather than simply the total number of iterations. text/html 2014-01-21T23:57:21+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/2.4_a_survey_of_common_running_times?rev=1390348641&do=diff When approaching a problem, it helps thinking about two kinds of bounds: one on the running time you hope to achieve, and the other on the size of the problem's natural search space (hence on the running time of a brute-force search algorithm for the problem). text/html 2014-01-22T02:58:37+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/2.5_priority_queues?rev=1390359517&do=diff We seek algorithms that improve qualitatively on brute-force search, and in general we use polynomial-time solvability. Priority queues will be useful when we are implementing the Stable Matching problem. The Problem We discussed ho we need to maintain a dynamically changing set S. In such cases, we want to be able to add, delete, and select elements from S when the algorithm calls it. A priority queue has a text/html 2014-01-29T04:50:03+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/3.1_basic_definitions_and_applications_graphs?rev=1390971003&do=diff A graph,G is simply a way of encoding pairwise relationships among a set of objects (Data structure). Consists of two sets, a set of nodes, and another for edges. An edge joins two nodes, it is denoted as e={u,v}, where u and v are nodes. There are two types of graphs: directed and undirected graphs. Directed graphs are those in which an ordered pair of nodes, lets say (u,v), the roles of u and v are interchangeable. text/html 2014-01-29T04:49:27+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/3.2_graph_connectivity_and_graph_traversal_graphs?rev=1390970967&do=diff Bold TextAfter understanding basic notion of graphs, we look forward to solving basic algorithm questions.Is there a path from s to t in a given graph, G? (s-t connectivity problem). This problem could also be called the Maze-solving problem. If we think of nodes as rooms, how can you get from one room to another if you start from room s? How efficient an algorithm can we design for this task? text/html 2014-01-29T04:47:56+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/3.3_implementing_graph_traversal_using_queues_and_stacks_graphs?rev=1390970876&do=diff DFS uses a stack while BFS uses a queue. We shall discuss how to use lists and arrays to represent graphs., and discuss the trade-offs between the two different representations. Representing Graphs. Using an adjacency list or adjacency matrix, are ways we can use to represent a graph. We shall focus on using an adjacency list. n = number of nodes, m = number of edges We shall use these two as parameters of our running times form now on. How do we know if O(n^2) is faster than O(m^3)? Is it imp… text/html 2014-02-11T07:03:01+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/3.4_testing_bipartiteness_bfs_algorithm?rev=1392102181&do=diff BIpartite graph: One where th enode set V can be partitioned into sets X and Y in a such a way that every edge has one end in X and the other in Y(Every edge joins one red node to a blue node). Examples of non-bipartite graphs are: A triangle (3 nodes), generally if a graph G has an odd cycle, then it cannot be partite. text/html 2014-02-11T07:01:58+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/3.5_connectivity_in_bipartite_graphs?rev=1392102118&do=diff In a directed graph, every edge(u,v) has a direction from u to v. This relationship is asymmetric, and this affects the structure of the resulting graph. An example would be the World Wide Web(the act of browsing from one webpage to another)-- where it is hard to browse backwards. text/html 2014-02-12T00:26:14+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/3.6_directed_acyclic_graphs_and_topological_ordering?rev=1392164774&do=diff If an undirected graph has no edges, then it has an extremely simple structure: each of its connected components is a tree. It is akso possible for a directed graph to have no (directed) cycles and still have a very rich structure. If a directed graph has no cycles, we call it a text/html 2014-02-12T01:42:30+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.0_greedy_algorithms?rev=1392169350&do=diff What is a greedy algorithm? It is difficult to describe what it is, but we generally say an algorithm is greedy if it builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion. One can design different greedy algorithms for the same problem, but all optimizing locally to reach an optimal solution. When a greedy algorithm succeeds in solving a nontrivial problem optimally, it implies something interesting and useful about the structure … text/html 2014-02-12T01:45:12+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.0_greedy_algorithms_front_matter?rev=1392169512&do=diff What is a greedy algorithm? It is difficult to describe what it is, but we generally say an algorithm is greedy if it builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion. One can design different greedy algorithms for the same problem, but all optimizing locally to reach an optimal solution. When a greedy algorithm succeeds in solving a nontrivial problem optimally, it implies something interesting and useful about the structure … text/html 2014-02-12T04:47:52+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.1_interval_scheduling_the_greedy_algorithm_stays_ahead?rev=1392180472&do=diff We shall say that a subset of requests is compatible if no two of them overlap in time, and the goal is to accept as large a compatible set subset as possible. Compatible sets of maximum size will be called optimal. Designing a Greedy Algorithm. We shall use a text/html 2014-02-24T06:13:37+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.2_scheduling_to_maximize_lateness_an_exchange_argument?rev=1393222417&do=diff Exchange Argument is a different kind of analysis that we are going to use to prove that our greedy algorithm is optimal. The Problem. Consider one resource that has to accomplish a set of n tasks within an interval of time for each resource. In this case we are going to look at deadlines that require a contiguous time interval for every task/request. All these requests must be assigned nonoverlapping intervals as part of the solution. Despite last problem in section 4.1, the algorithm has to cr… text/html 2014-02-26T04:41:01+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.4_shortest_paths_in_a_graph?rev=1393389661&do=diff Here we apply a greedy algorithm to finding the shortest paths. The Problem. Graphs are often used to model networks in which one travels from one point to another. Thus, a basic algorithmic problem is to determine the shortest path between nodes in a graph. That is to say, given nodes u and v, what is the shortest u-v path? Or given a start node s, what is the shortest path from s to each other node? text/html 2014-02-26T04:41:32+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.5_the_minimum_spanning_tree_problem?rev=1393389692&do=diff We now can apply an exchange argument in the context of a second fundamental problem on graphs: the Minimum Spanning Tree Problem. The Problem. Our goal is to build a communication network with the least cost on top of a set of locations.We assume that the full graph G is connected, otherwise no solution is possible. The goal of our network design problem can be rephrased as that of finding the cheapest spanning tree of the graph ; for this reason it is called the Minimum Spanning Tree Problem. text/html 2014-02-26T04:39:06+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.6_implementing_kruskal_s_algorithm_the_union-find_data_structure?rev=1393389546&do=diff In this case, the graph evolves through the addition of edges. Our goal is to maintain the set of connected components of such a graph throughout this evolution process. We will develop a data structure called the Union-Find structure which will store a representation of the components in a way that supports rapid updating and searching. For every edge e(v,w), if the connected components containing v and w are different, then there is no path between v and w, and hence edge e should be added and… text/html 2014-03-04T23:20:56+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.7_clustering?rev=1393975256&do=diff Minimum Spanning Trees also play a role in the area of clustering. The Problem. Clustering happens when one has a collection of objects such as a set of documents that one is trying to organize into a coherent group. It is important to find the similarityies between each pair of objects. One way to define similarities is by using a text/html 2014-03-05T04:24:03+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/4.8_huffman_codes_and_data_compression?rev=1393993443&do=diff We have seen how greedy algorithms use a greedy rule to shrink the size of a problem instance, in order to solve a smaller problem by recursion. The smaller instance leads to an optimal solution for the original instance , but the global consequences do not become fully apparent until the full recursion is complete. text/html 2014-03-05T04:48:05+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/5.1_the_mergesort_algorithm?rev=1393994885&do=diff Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half recursively, and then combining the two results. Basically, divide the list of numbers, solve and merge(conquer) both of them after sorting. We need a base case for the solution, which is in this case, when the length of the list is 2, compare the two elements , and sort them. Suppose n is even and T(n) is the time spent on such an instance, the algorithm spends O(n) time to divide the input i… text/html 2014-03-11T05:04:34+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/5.2_further_recurrence_relations?rev=1394514274&do=diff We just worked out a solution to a recurrence relation. We shall now consider a class of recurrence relations that generalizes a recurrence relation and shows how to solve it. The more general class of algorithms is obtained by considering divide-and-conquer algorithms that create recursive calls on q sub problems of size n/2 each, and then combine these solutions in O(n) time. A general recurrence relation used to figure out an algorithm's run time is: text/html 2014-03-12T02:11:05+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/5.3_counting_inversions?rev=1394590265&do=diff We have spent some time discussing approaches to solving a number of common recurrences. We shall illustrate the application of divide-and-conquer to problems form a number of different domains. The Problem. We will consider a problem that arises in the text/html 2014-03-12T03:41:44+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/5.4_finding_the_closest_pair_of_points?rev=1394595704&do=diff We now describe another problem that can be solved by an algorithm in the style we have been discussing; but finding the right way to “merge” the solutions to the two sub problems it generates requires a bit of ingenuity. The Problem. Given n points in a plane, find the pair that is closest together. This problem was considered by M.I Shamos and D.Hoey in the early 70s to work out efficient algorithms for basic computational geometry. It is hard to find an efficient algorithm for this problem. … text/html 2014-03-24T11:13:29+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/6.1_weighted_interval_scheduling_a_recursive_procedure?rev=1395659609&do=diff This problem is a strictly more general version, in which each interval has a certain value(or weight), and we want to accept a set of maximum value. Designing a Recursive Algorithm. No natural greedy algorithm is known for this problem, which is what text/html 2014-03-25T11:54:18+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/6.2_principles_of_dynamic_programming_memoization_or_iteration_over_subproblems?rev=1395748458&do=diff We now use the algorithm for the previous problem to summarize the basic principles of dynamic programming. We developed a polynomial-time solution in the previous section by memoization of our initial exponential-time solution. It is helpful to formulate essentially an equivalent version of the algorithm. text/html 2014-03-26T02:45:40+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/6.3_segmented_least_squares_multi-way_choices?rev=1395801940&do=diff We previously developed a recurrence based on a fundamentally binary choice: either an interval n belonged to the solution or not. The recurrence in this problem will involve what might be called “multi-way choices”. At each step we have a polynomial number of possibilities to consider for the structure of the optimal solution. text/html 2014-03-26T02:45:25+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/6.4_subset_sums_and_knapsacks_adding_a_variable?rev=1395801925&do=diff Here, we consider a version of problems with durations and deadlines, which is difficult to solve directly using the techniques we have seen so far. The Problem. We have a single machine that can process jobs, and a set of requests. We are only able to use this resource for the period between time 0 and time W, for some number W. Each request corresponds to a job that requires time wi to process. Which jobs should we choose if we want to keep the machine as busy as possible before the cut-off … text/html 2014-04-01T00:25:21+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/7.1_the_maximum-flow_problem_and_the_ford-fulkerson_algorithm?rev=1396311921&do=diff One often uses graphs to model transport systems or networks. Network models of this type have several ingredients: capacities on the edges, indicating how much traffic they carry, source nodes that generate traffic and sink nodes which absorb the traffic, and the traffic itself. text/html 2014-04-01T01:33:09+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/7.2_maximum_flows_and_minimum_cuts_in_a_network?rev=1396315989&do=diff Analyzing the Algorithm. Flows and Cuts. Our next goal is to show that the flow that is returned by the Ford-Fulkerson Algorithm, has the maximum possible value of any flow in G. To make progress toward this goal, we look at the way in which the structure of the flow network places upper bounds on the maximum value of an s-t flow. We use the notion of a text/html 2014-04-02T03:38:05+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/7.5_a_first_application_the_bipartite_matching_problem?rev=1396409885&do=diff We will begin with two basic applications: first, the Bipartite Matching Problem and the Disjoint Paths Problem in the next section. The Problem. A bipartite graph is an undirected graph whose node set can be partitioned as V=XUY, with every edge in the graph joining a node from X and one from Y. text/html 2014-04-02T03:35:20+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/7.7_extensions_to_the_maximum-flow_problem?rev=1396409720&do=diff Much power of the Maximum-Flow Problem lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or minimum cut in a directed graph. text/html 2014-01-21T04:43:37+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/fred_s_journal?rev=1390279417&do=diff 2.2 Bounds. Instead of counting the steps (number of instructions)in an algorithm, we shall find a more meaningful and tireless way of finding the running time of an algorithm. We shall then use bounds to understand generally the working time range of an algorithm. Asymptotic Upper bounds. T(n) is our function, f(n) is another given function. T(n) can be expressed as f(n) i.e T(n) is order of f(n) if for sufficiently large input size N, T(n) is bounded above by c.f(n) where c>0. This means T(n) text/html 2014-04-02T01:40:50+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/home?rev=1396402850&do=diff ----Fred's Journal---- Preface summary. 1.1 The stable-matching process. 2.1 Basics of Algorithm Analysis 2.2 Bounds 2.3 Implementing the Stable Matching Algorithm using Lists and Arrays 2.4 A Survey of Common Running Times 2.5 Priority Queues 3.1 Basic Definitions and Applications(Graphs) 3.2 Graph Connectivity and Graph Traversal(Graphs) 3.3 Implementing Graph Traversal Using Queues and Stacks(Graphs) 3.4 Testing Bipartiteness BFS Algorithm 3.5 Connectivity in bipartite graphs 3.6… text/html 2014-01-21T04:45:53+00:00 Anonymous (anonymous@undisclosed.example.com) http://servo.ad.wlu.edu/dokuwiki/doku.php/courses/cs211/winter2014/journals/fred/preface_summary?rev=1390279553&do=diff The subject of Algorithms is a powerful lens through which to view the field of computer science in general. Although we are more interested in understanding this subject in the field of computer science, other fields such as economics, biology, and other studies have used algorithms to solve problems respectively. Algorithmic projects include two fundamental components: understanding the mathematical clean core of a problem, and identifying the best techniques of solving the problem. Kleinberg …