Chapter 4

Greedy Algorithms

“Greed… is good. Greed is right. Greed works” - Wall Street.

Greed algorithm definition:

• Hard to define
• builds up a solution in small steps.
• need to prove the greedy algorithm is optimal.

Two methods of proof

• greedy algorithm stays ahead (4.1)
• Exchanage argument

All this leads up to minimum spanning tree!

Greedy rule that works

• accept the request that finishes first
• algorithm on page 118

Show that this algorithm is optimal

• need to show that this algorithm produces the same size interval as the optimal solution
• To prove this algorithm is optimal need lemma.
  • Lemma 1: for all indices r⇐ k we have f(ir) ⇐ f(jr). proof on p. 120
• now can prove greedy algorithm is optimal. see page 121

Scheduling all Intervals

• This is similar to the classroom multi resource problem we did in class
• 4.4: in any instance of interval partitioning the number of resources needed is at least the depth of the set of intervals.
• algorithm on p. 124
• not sure how to code the “exclusion” idea in python.
• 4.5: if we use the greedy algoirthm above every interval will be assigned a label, and no two overlapping intervals will receive the same label.
• 4.6: the greedy algoithm above schedules every interval on a resource, using a number of resources equal to the depth of the set of interals. This is the optimal number of resources needed.

• We did a lot with this in class - talks about maximum lateness
• optimal greedy rule - earliest deadline firt
• algorithm pgs. 127 - 128
  • 4.7 there is an optimal sched with no idle time
  • 4.8 all schedules with no inversions and no idle time have the same maximum lateness
  • 4.9 there is an optimal schedule that has no inversions and no idle time.
  • swapping argument page 129 and page 130
  • 4.10 the schedule A produced by the greedy algorithm has optimal maximum lateness L.

• A problem that focuses on a sequence of requests of a different form.
• I don't think we covered this in class and its not listed on the schedule so I'm not going to write on it. If you want me to just let me know!

Problem = how to find the shortest paths either from one point to another or to all the points.

• Dijkstra algorithm
  • on page 138
  • 4.14 consider the set S at any point in the algorithm's execution. For each u element of S, the path Pu is a shortest s-u path.
    • proof on page 139
    • used dijkstra's for a project in highschool before.
  • 4.15 using a priority queue, Dijkstra's algorithm can be implemented on a graph with n nodes and m edges to run in O(m) time, plus the time for extractMin and Changekey operations.

• problem: looks for way to hit all the verticies the cheapest way possible.
• 4.16: Let T be a minimum-cost solution to the network design problem defined above. Then (V,T) is a tree.
• Three algorithms that work:
  • Kruskals: orders edges from low cost to high cost and keeps adding in the min cost that does not cause a cycle
  • Prim's - pick a source node and add the node that can be added most cheaply to the tree. Continue to do this.
  • Reverse - delete algorithm - delete highest cost edges as long as it does not disconnect the tree.
• 4.17: assume that all edges costs are distinct. Let s be any subset of nodes that is neither empty nor equal to all of V, and let edge e = (v,w) be the minimum cost edge with one end in S and the other in V - S. Then every minimum spanning tree contains the edge e.
• from pgs 146 - 148 the book discusses the why the three algoithms above are optimal.
  • we went over these in class. the book also discusses the cycle and cut properties we talked about
• pgs 149 - 150 talk about the implementation of prims algorithm
  • important take away for prim use a priority queue

• union-find data -
  • given a node u, the operation Find(u) will return the name of the set containing U.
  • Can be used to test if two nodes are in the same set.
  • Can merge two sets. Use the union-find to maintain connected components of graph G(V,E)
  • more info on p 152.
  • 4.23 consider the array implementation of the union-find data structure for some S of size n, where unions keep the name of the larger set. The Find operation takes O(1) time, MakeUninionFind(S) takes O(n) time, and any sequence of k Union operations takes at most O(klogk) time.
    • pf on page 153
  • another implmentation of Union-Find possible.
    • 4.24 Consider the above pointer-based implementation of the Union-Find data structure for some set S of size n, where unions keep the name of the larger set. A union operation takes O(1) time. MakeUnionFind(S) takes O(n) time. and a find operation takes O(logn) time.
    • Definitely still have some questions of the Union-find data structure, but I am going to go review the slides I missed.
• implementing Kruskal's Algorithm
  • sort the edges by cost, then use union-find to maintain the connected components of (V,T) more details on p. 157
  • 4.25 Kruskal's algoirthm can be implemented on a graph with n nodes and m edges to run in O(mlogntime)

The problem

• clustering arises when you have a group of objects and want to stratify them into different groups.
• common approach is to define a distance function on the objects where the larger the distance the less “related” the objects are to each other. In a physicial world this function could be taken as literal distance.
• Given a distance function the clustering approach seeks to divide them into groups so that objects in the same group are close and objects in the other group are far apart.

clustering of maximum spacing

• further def of distance function: d(i,i) = 0, d(i,j) > 0, d(i,j)=d(j,i)
• if we want k groups you need k clusterings.
• we also want clustering with maximum possible spacing, which means we want the clusters to be as far as possible from each other.

Designing the algorithm:

• we grow a graph from the set of vertices
  • add edges in increasing order of distances, don't add an edge if the two vertices are already in the same cluster.
  • if we add an edge that spans two distinct components we will be merging the two clusters. (call this single link clustering)
  • we are using hierachial agglomerative clustering to make this work.
  • we are using Kruskal's minimum spanning tree algorithm thus the union find data structure.
    • we stop just before we add the k-1 edges.

Analyzing the algorithm

• 4.26: The components C1, C2, …, Ck formed by deleting the k -1 most expensive edges of the minimum spanning tree T constitute a k clusering of maximum spacing.
• proof on page 150.

• basic problems of data compression

encoding symbols using bits

• convert text into binary aka long strings of bits
• could fix a number of bits to each letter. so if we have k letters need 2^k bits.
• this might not be the most efficient.
• how do you lower the average number of bits per letter?

Variable-length encoding schemes

• ex. morse code
• morse code the lettters are prefixes. we don't want this.

prefix code

• means that no letters are prefixes. don't need spaces.
• ex. a = 00, b = 10, c = 11. 110010 is clearly cab.
• we will want an optimal prefix codes aka we want less bits for more frequent letters.
  • will lower abl.
• see def. of encoding length on page 165. (sum of frequencys * length of encoding)

designing the algorithm

• representing prefix codes using bin trees.
  • each leaf is a letter
  • going left is 0 going right is one
  • see ex. on 168
  • will give a prefix code if all the letters are leafs! (4.27)
  • 4.28 the bin tree for optimal prefix code is full
• Top down approach
  • different from how we did it in class
  • this isn't optimal
  • see 4.29 and page 170-171
• Now lets find the optimal prefix code algorithm
  • 4.31 - there is an optimal prefix code, with corresponding tree t* in which the two lowest-frequency letters are assigned to leaves that are siblings in t*
  • called huffman's algorithm
  • see page 172
  • we also did a different algorithm in class

Analyzing Huffman's algoirthm

• proof of optimality - on p. 174. (Very mathy, uses summation notation and not words)
• second part of proof uses proof by contradiction.
• see page 174 - 175
• Running time = o(klogk)

extensions

• can use it with images and encoding messages.
• I can't remember where or why I went to this, (was it at UDEL?, but I remember going to talk and listening to a woman talk about how her job was to do this to encode messages in images.