Differences
This shows you the differences between two versions of the page.
Next revision | Previous revisionNext revisionBoth sides next revision | ||
courses:cs211:winter2012:journals:mike:home [2012/01/08 03:35] – created admin | courses:cs211:winter2012:journals:mike:home [2012/03/28 03:18] – [Chapter 6] whitem12 | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Mike's Journal ====== | ====== Mike's Journal ====== | ||
+ | ===== Preface: | ||
+ | Algorithms are used all over the place in tons of applications, | ||
+ | | ||
+ | |||
+ | ===== Chapter 1 ===== | ||
+ | ==== The Matching Problem ==== | ||
+ | |||
+ | The goal is to make an efficient algorithm for matching two groups together. | ||
+ | The simplest form of this problem, and thus the easiest example of it to explain, is where every one thing matches with only 1 thing, and there are an identical number of items on each side. | ||
+ | For this example the book uses men and women getting engaged. | ||
+ | The Book Presents the Gale and Shapely method for what a stable and unstable match is. An unstable match is one in which two sets of partners would rather be with the partner in the other group. | ||
+ | ==== Five Representative Problems ==== | ||
+ | Graphs are good for representing pair-wise relationships. | ||
+ | === Interval Scheduling === | ||
+ | Problem: How do you schedule individual use of a popular resource. | ||
+ | This problem is pretty simple to solve. | ||
+ | === Weighted Interval Scheduling === | ||
+ | Problem: How do you schedule a resource which is in demand, given that individuals have a priority associated with them, to maximize the return. | ||
+ | This is not as easy to solve as the non-weighted problem, but you can use dynamic programming. | ||
+ | === Bipartite Matching === | ||
+ | Problem: When doing the matching problem using Bipartite graphs, the problem gets more difficult. | ||
+ | === Independent Set === | ||
+ | Problem: given a graph, find the subgraph such that all nodes are independent. | ||
+ | === Competitive Facility Location === | ||
+ | Problem: you have two players competing for owning a certain sum of weighted nodes with rules as to which can be adjacent, each picks nodes after the other, what's the best possible way to play the game to getting the largest sum? | ||
+ | |||
+ | ===== Chapter 2 ===== | ||
+ | Basics of Algorithm Analysis | ||
+ | ==== Computational Tactability ==== | ||
+ | Defining efficiency is difficult. | ||
+ | ==== Asymptotic Order of Growth ==== | ||
+ | When discussing algorithm complexity it is most important to discuss how the algorithm handles number of instructions relative to the amount of data/ | ||
+ | |||
+ | ===== Chapter 4 ===== | ||
+ | ==== Section 7: Clustering ==== | ||
+ | === The Problem === | ||
+ | == Maximum Spacing == | ||
+ | ===Design of the Algorithm=== | ||
+ | === Analyzing the Algorithm === | ||
+ | ====Section 8: Huffman Codes and Data Compression ==== | ||
+ | ===The Problem=== | ||
+ | ==Variable-Length Encoding Schemes== | ||
+ | ==Prefix Codes== | ||
+ | ==Optimal Prefix Codes== | ||
+ | ===Design=== | ||
+ | ==Prefix Codes as Binary Trees== | ||
+ | ==Top-Down Approach== | ||
+ | ===Analyzing=== | ||
+ | |||
+ | ===== Chapter 5 ===== | ||
+ | Divide and Conquer | ||
+ | ====Section 1: Mergesort==== | ||
+ | Idea: Divide a list in half until you have sorted lists (all single entries) and then merge them back together as a sorted list such that the final list is a sorted version of the initial list. Takes n steps to break down and n*log(n) steps to merge them back together. | ||
+ | === Approaches === | ||
+ | Two basic ways: | ||
+ | ==Unrolling the Mergesort Recurrence== | ||
+ | Analyze the first few layers and generalize from there to unroll how the recursion takes place. | ||
+ | ==Substituting a Solution into the Mergesort Recurrence== | ||
+ | Guess what the solution is and then check it (this is good for merge sort since we know it takes n*log(n). | ||
+ | ==Partial Substitution== | ||
+ | So if you don't know the constant then you can assume it exists and then check to make sure that it turns out right in the end and then work it back up to find the actual constant involved. | ||
+ | |||
+ | ===== Chapter 6 ===== | ||
+ | Dynamic Programing - Break down into sub problems, then build the problems back up to solve the large problem. | ||
+ | ==== Weighted interval scheduling ==== | ||
+ | Recursive algorithm: this is the first step in creating a dynamic algorithm. | ||
+ | === How to do it === | ||
+ | - label the requests, and sort them in order of finishtime | ||
+ | - Think of the optimal solution, either the last item is in it or isn't in it | ||
+ | - Find the optimal solution involving the last one (so ignore all that don't finish before it starts) and the optimal solution that doesn' | ||
+ | |||
+ | This is a problem because the call stack grows at very very fast rate, we want to avoid this, so we introduce the dynamic part. | ||
+ | |||
+ | By memorizing the result of a previous calculation, | ||
+ | |||
+ | You can use the Array of calculation choices to work your way back to find the optimal solution. | ||
+ | |||
+ | ==== Memoization ==== | ||
+ | |||