Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:thetfordt:chapter4 [2018/02/20 17:43] – created thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter4 [2018/03/12 00:17] (current) – thetfordt
@@ Line 2: / Line 2: @@
 ===== Section 4.1 - Interval Scheduling: The Greedy Algorithm Stays Ahead =====
+The section begins by bringing back a problem from earlier in the text: the Interval Scheduling Problem. In this problem, we are given a set of requests with start and finish times, and we are asked to find the largest subset of requests such that none of the times overlap. We want to devise a greedy algorithm to solve this problem.
+The book walks through the different strategies we could use: ordering by start times, total time intervals, basing intervals on other intervals, and finally, finish times. It turns out that by ordering the requests by finish times, we have a greedy algorithm that matches the optimal solution.
+The algorithm begins with a while loop on the set of all requests R. It says that while that set is nonempty, we choose the request with the smallest finishing time, we add that request to our set A (which will contain the solution), and then delete all requests from R that are not compatible with the request we just added to A. This algorithm is intuitive, and the book walks through the proof behind it well. Finally, the text diagnoses the runtime of the algorithm which is O(nlogn). Note that the runtime here is caused by ordering the finish times in sorted order, which we know takes O(nlogn) time.
+Next, the book moves on to a similar problem. Here, we are given another set of requests, and we wish to schedule all of these requests using as few resources as possible. The book provides a good example to contextualize this using the idea that if we are given a set of class times, how many classrooms will we need to accommodate these class times. The text proves the intuitive fact that the number of resources needed is at least the depth of the set of intervals.
+The algorithm follows similarly from the algorithm produced earlier in the section. First, we sort the intervals by their start times. As we progress through these sorted intervals j = 1,2,...,n, for any two intervals that are overlapping, we exclude the label from the preceding (earlier) interval I_i from consideration with the later interval I_j (in the same resource). And then if there is a label that has not been excluded during this call of the for loop, we assign a nonexcluded label to I_j. If there does not exist such a label, we leave I_j unlabeled.
+The book does not diagnose the runtime of this algorithm. However, it does analyze the algorithm, ultimately concluding that the algorithm will schedule every interval on a resource, using a number of resources **equal to** to the depth, which was not as clear before reading the section carefully.
+This section was long, and hard to follow at times. I would rate the readability at 5/10.
+===== Section 4.2 - Scheduling to Minimize Lateness: An Exchange Argument =====
+This section begins by slightly manipulating the interval scheduling problem such that each request is given a time t and a deadline d. Our goal is to minimize the maximum lateness of the requests. The text walks through a few different strategies for solving this problem. It spends some time attacking the strategy of ordering by the amount of time each request takes and the strategy of ordering by slack time (d - t). It then concludes that the clear choice to produce an optimal solution is ordering by increasing deadlines. The text then walks through an algorithm will it claims will accomplish this.
+The algorithm first orders the jobs in order of their deadlines. It then considers each job in this sequence, creates a start and finish time for each job by using the information given, and returns the set of scheduled intervals after conducting this loop.
+It then walks through the long and dwindling proof that this solution is indeed optimal. It does this by using an exchange argument. The exchange argument is used by defining something called an inversion. An inversion is a pair of jobs i and j such that j is scheduled immediately after i and has d(j)<d(i). The text takes an optimal schedule, supposes it has inversions, and then shows by eliminating these inversions, we still have an optimal schedule (minimizing maximum lateness) which is identical to the schedule which is created by the algorithm. We know this because the algorithm produces a schedule with no inversions.
+I would rate the readability of this section at 8/10. It was interesting and a helpful supplement to what we learned in class.
+===== Section 4.4 - Shortest Paths in a Graph =====
+This section begins by laying out its purpose: to apply a greedy algorithm to the problem of trying to find the shortest path in a graph. The problem is then further defined: given a start node s, what is the shortest path from s to each other node?
+It turns out that Edsger Dijkstra created a greedy algorithm to solve this exact problem in 1959. The algorithm keeps track of a set S of vertices u. For each one of these nodes, the set also maintains the shortest distance from s to each one of these other vertices u as d(u). Initially, we let S={s} and d(s) = 0. And for each node v in V-S, where V is the set of vertices in the graph, we find the shortest path that can be created by traveling through the vertices in S to the new node v before adding it to S. For some node u in S, there will be a path (u,v) such that d(v) = d(u) + length(u,v) where d(v) is the shortest path to v from s.
+I found this algorithm confusing in class, but the text helped to clear things up in Figure 4.7, laying out a very simple example of the next choice Dijkstra's algorithm would take.
+The text goes on to prove that Dijkstra's algorithm will indeed drive the shortest path from s to any other node u in the graph. I found this proof straightforward. The text also notes two key facts about the algorithm: (1) that it does not work if paths have negative distances and (2) that is is truly a continuous version of the breadth-first search. (2) helps clear up the intuition behind the algorithm because, intuitively, I would think that the way to find the shortest path from one node to another would be to simply run a BFS on that node.
+The book then walks through the implementation of the algorithm. It ultimately concludes that by using a priority to queue to hold the nodes V with the distances as the keys for each node, we can reduce the running time of Dijkstra's algorithm to O(m), rather than O(nm) with sloppy implementation.
+I would rate the readability of this section at 8/10. Although I found it difficult to follow at times, I think it is just because Dijkstra's algorithm is slightly more complex than what we have covered in the past. Although, once it became clear to me the exact intuition behind it, I began to read much more fluidly with more comprehension and interest.
+===== Section 4.5 - The Minimum Spanning Tree Problem =====
+This section begins by illustrating the problem: we have a set of locations and we want to build a communication network between them with the least cost possible. This then leads us to the idea of the minimum spanning tree because, in reality, we are searching for the cheapest spanning tree of a given graph.
+The section then walks through three different approaches to solving this problem (which are all efficient and correct): Kruskal's Algorithm, Prim's Algorithm, and the Reverse-Delete Algorithm. Before going into detail as to what each of these does, I want to lay out the properties essential for proving these algorithms work. First, the book lays out and proves the cut property: this says that if we have two subsets of nodes, and there is an edge e with the minimum-cost with one end in one set and the other end in the other set, then every minimum spanning tree on that graph must contain that edge e. I found the book's proof of the cut property very helpful and intuitive. Now, with this property, the text makes it clear that we are able to prove the optimality of Kruskal's and Prim's algorithms.
+Krukal's algorithm works by taking the graph, disconnecting the edges, and then adding the edges back in ascending order until we arrive at a minimum spanning tree. This, intuitively, makes sense and I found the proof of its optimality clear, with the usage of the cut property.
+Prim's algorithm works very similarly to Dijkstra's algorithm. It starts with a root node s and greedily grows a tree outward from s. However, at each step, we just add in the node to the tree which yields the least cost. The book uses the cut property to prove the optimality of this, as well.
+Then, the book walks through the cycle property, which I felt I had a solid grip on from class. The cycle property says that if a graph has a cycle C, then the most expensive edge in that cycle cannot possibly belong to the minimum spanning tree of that graph.
+The book uses this property to explain the optimality of the Reverse-Delete Algorithm: this algorithm starts with the fully connected graph, and progressively deletes the largest edge in the graph until reaching a minimum spanning tree (obviously not deleting an edge which would disconnect the graph).
+The book ends the section with, first, discussing the implementation of Prim's algorithm, which follows fairly intuitively from Dijkstra's algorithm. It uses a priority queue to contain the nodes with attachment costs of those nodes as the keys. This was a nice reminder from what we covered in class, as implementation details can sometimes be difficult to grasp.
+The book concludes the section discussing extensions of the minimum spanning tree problem. One suggestion that jumped out at me, in particular, was the idea of making resilience an explicit goal when designing a tree. What would an algorithm for designing a tree which stayed connected through any particular edge deletion look like? If we were designing a power grid for a neighborhood, this is what kind of structure we would want, as power lines are bound to come down at some point. We would want houses to maintain power even if something like this happened.
+I would rate the readability of this section at 9/10. It was interesting material and the proofs were straight-forward.
+===== Section 4.6 - Implementing Kruskal's Algorithm: The Union-Find Data Structure =====
+This section through the background of the Union-Find data structure in order to reach an implementation of Kruskal's Algorithm, which I discussed in the previous section.
+In order to implement the algorithm, the book lays out what operations we would like our data structure to be able to accomplish. The first operation is MakeUnionFind, which returns all elements in sets, which we want to run in O(n) time. The second is, for some u in S, Find(u), which returns the name of the set containing u. And we want this to run in O(log n) time. And finally, for two sets A and B, we want to be able to join them using an operation called Union(A,B) and run in O(log n) time.
+The book walks through two approaches for implementation of this structure. The first approach is an array implementation. I like the strategy the text uses for proving that the union operation runs the time it does. Rather than focusing on worst-case run time for every call, it focuses on the total running time a for a sequence of operation, which turns out to be O(k log k). But I preferred the book's second implementation option, which uses pointers to nodes to maintain sets. When two sets are joined in a union, the pointer of the smaller set then points to the location of the pointer of the larger set, which implements union in O(1) time. But this increases the runtime of finding a node to O(log n) time as one must cycle through at most log(n) pointers in order to reach the node being sought.
+The book walks through the implementation of Kruskal's algorithm using this data structure, but also notes that the current version we have of the union-find data structure could be improved, but is not necessary for the implementation of the algorithm. This is because the bulk of the running time of the algorithm comes from sorting the edges in ascending order (which we need to use the algorithm) which runs in O(m log m) time. The book also notes that O(m log m) is the same as O(m log n) since m <= n^2.
+I would rate the readability of this section at 8/10.
+===== Section 4.7 - Clustering =====
+This section addresses the issue of clustering. Given a distance function on objects, we are seeking to divide them into different groups such that objects within the same group are close together, and objects in different groups have their distance maximized. So, if we want k clusters, we are seeking a k-clustering with the maximum possible spacing between each cluster.
+The book walks through the process of designing such an algorithm that will do this but ultimately concludes that this is incredibly similar to Kruskal's algorithm. If we want k clusters on a graph G, we would just obtain the minimum spanning tree on this graph from Kruskal's algorithm, but without performing the last (k-1) edge-additions. Alternatively, the book defines a formal claim that if we have a minimum spanning tree T and delete the (k-1) most expensive edges, we have k components with maximum spacing. The proof for this was fairly straight-forward.
+I would rate the readability of this section at 9/10.
+===== Section 4.8 - Huffman Codes and Data Compression =====
+In this section, we consider another slightly different approach to a new idea of a greedy algorithm. We shrink the size of a problem such that a smaller problem of the same structure can be solved by recursion. An excellent example of this is the problem of encoding symbols using bits. (Note that this is also an area of data compression as this is a core issue in that field.) The problem is that we want to figure out the smallest number of average bits per symbol (or letter, in our case) such that we optimize the data compression, we can represent those symbols using as little space as possible.
+The text dives into the first true widespread usage of encoding, which was through morse code. But Morse code has one critical problem which we must address in data compression. It requires a sort-of 'space' between each letter. But we need to be able to represent symbols as a continuous string of bits such that we are only working with two bits - 1's and 0's.
+This introduces the idea of prefix codes. This is exactly what it sounds like. In using prefix codes, we map a set of symbols to bits such that no symbol is a prefix of any other. In doing that, we can represent any string of symbols using only 0's and 1's.
+The text walks through how prefix codes can be represented using binary trees. We can do this by having leaf nodes represent letters and left tree branches to represent zeros and right tree branches represent ones. In doing this, this actually establishes a prefix code for this set of letters. The book walks through a straightforward proof of this. I should note that this binary tree is also full.
+The book then walks through a few different approaches to the construction of the tree, because that is at the core of the problem. It first walks through the top-down approach. This approach takes the set of letters, splits it into two halves, and then forms the tree by using these two halves. However, the book note that there is no such version of the top-down solution such that it always produces an optimal prefix code.
+This leads us to the bottom-up approach, AKA Huffman codes. Huffman developed and proved the optimality of his algorithm by constructing the prefix tree from the bottom up. Suppose we are given an alphabet S with given frequencies. If S has two letters then we encode one letter using 0 and the other letter using 1 (base case). Otherwise, we let y* and z* be the two lowest-frequency letters. We form a new alphabet S' by deleting y* and z* and replace them with a new letter w of frequency f(y*)+f(z*). We then recursively construct a prefix code m' for S', with tree T' and define a prefix code for S as follows: Start with T', take the leaf labeled w and add two children below it labeled y* and z*. We can see that this algorithm addresses exactly the kind of recursive problem the chapter began by describing. The book follows the logic of the algorithm by proving the optimality of it. It does this by proving the Huffman code for a given alphabet achieves the minimum average number of bits per letter of any prefix code.
+The book then walks through implementation, first stating that it appears this would run in O(k^2) time. However, if we use an implementation of priority queues via heaps, we can actually reduce the running time down to O(k log k).
+In the section mentioning some extensions of Huffman codes, the idea of arithmetic encoding really jumped out to me. I would think that a series of black and white pixels would have to be represented by 0's and 1's for black and white. However, I did not think of the fact that you could represent certain common patterns of whites and blacks using prefix codes.
+I would rate the readability of this section at 7/10. Although very interesting, it was hard to stay focused over such a long section.