### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Greedy Algorithms CSCI 570

USC

### View Full Document

## About this Document

## 5

## 1

## Popular in Analysis of Algorithms

## Popular in Computer science

This 10 page Class Notes was uploaded by Viswambharan Kasturi Rangarajan on Saturday August 13, 2016. The Class Notes belongs to CSCI 570 at University of Southern California taught by in Fall 2016. Since its upload, it has received 5 views. For similar materials see Analysis of Algorithms in Computer science at University of Southern California.

## Similar to CSCI 570 at USC

## Popular in Computer science

## Reviews for Greedy Algorithms

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 08/13/16

Greedy Algorithms Dijkstra’s Algorithm + Suppose the edge weights are always positive; that is, the weight function is of the form w : E ! R . Let’s ▯rst illustrate how we can compute the shortest path tree from a designated starting point (use vertex s). 10 a c v intree(v) parent(v) dist(v) s N/A 0 6 8 0 3 a s b 1 d b 4 c 3 7 5 2 d f e 12 e f Dijkstra’s (Single-Source, Shortest Path Tree) Algorithm for each vertex v do intree(v) = false parent(v) = N/A dist(v) = 1 dist(s) = 0 while 9 vertex u with intree(u) = false do u vertex with intree(u) = false and smallest dist(u) intree(u) = true for each vertex v 2 adj[u] do if d(v) > d(u) + w(u;v) then d(v) = d(u) + w(u;v) parent(v) = u ▯ What is the shortest path tree after this algorithm terminates? ▯ Why does Dijkstra’s algorithm get the right answer? Why is it \safe" to commit to a vertex after assigning it to u inside the while loop? ▯ What is the running time of the above algorithm? Heaps and Priority Queues The key to making Dijkstra’s algorithm (and many others) fast is being able to e▯ciently identify the smallest element in a set. We could keep the set sorted, but with regular insertions, this requires a lot of time spent updating. Alternately, we could do a normal Find-Min across the set every time we needed it, but this also requires much time. Instead, we turn to the heap1 data structure. A heap, as an abstract data type, supports the following operations; the running time is expressed in terms of n, the number of elements in the heap at the time of the operation. Heap Operation Running Time Add O(logn) Find-Min O(1) Delete-Min O(logn) A min heap is a binary tree (not a binary search tree) with the following properties: ▯ The root of the tree is the smallest element ▯ Each node in the tree can have at most two children. ▯ Each node’s value is no larger than the value of any of its children ▯ Every row, except maybe the last, is full. ▯ The last row, if not full, is ▯lled left to right. A heap is conveniently represented in an array. If there are n elements in the heap, they are stored in H :::H . The root is in H and, if H has children, they are in H and H . If a node H has a parent, 1 n 1 i 2i 2i+1 i it is at bi=2c Draw the heap that is represented by the string \CHEMISTRY" (the following array): i 1 2 3 4 5 6 7 8 9 H C H E M I S T R Y i 1For today, when we say \heap" we really are referring to a min-heap. A max heap has the maximum element at the top instead. In CSCI 570, we are only using a binary heap; other types, including binomial and ▯bonacci heaps, exist. Exercise: Suppose your friend is working at the library and is in charge of allowing groups into the various study rooms. For this problem, all study rooms are interchangable. A total of n groups have requested to use a study room tonight; group i would like to use it from s to fi. If iwo groups overlap in their request times, they cannot be placed in the same study room; furthermore, we cannot reject a group. Fortunately, we have a very large library with an in▯nite number of study rooms, although we would prefer to not use all of them if possible. Give an e▯cient algorithm that will assign each group to a room (the rooms are numbered 1;2;3;:::) in such a way that the number of rooms you use is minimized, and no two groups that overlap are assigned to the same room. Explain as best you can why your algorithm achieves the optimal number of rooms (we’ll talk about how to formally prove this momentarily). Unweighted Interval Scheduling Related reading: Kleinberg/Tardos x4.1 Let’s revisit a problem from last week, with a slightly di▯erent approach: Fed up after CSCI 570, your friend has decided to change majors to one that grades based only on attendance. The only question is which classes to take next semester? They all meet once a day at di▯erent times, but are worth the same credits each. Your friend’s goal is to maximize the number of classes taken in Spring without having to skip any. Problem Statement: we are given a set of n intervals, each of which has a start time s , a ▯nish time f . i i Our goal is to select as large of a subset of the intervals such that no two selected intervals overlap. We could call the algorithm from a few weeks ago, with 8 v = 1i iut let’s see if we can ▯nd a di▯erent way to solve this. It’s possible that a simpler algorithm exists than the dynamic programming solution. In fact, one of the following algorithms will get the correct answer. Decide which ones don’t work by providing counter-examples. Don’t worry (yet) about proving one that is correct. Please note: for the homework and exam, you do not need to provide \not working" algorithms, and showing that other algorithms do not work does not demonstrate that yours does. The purpose of this part is to examine candidate algorithms and to think about the problem. ▯ Sign up for the class that begins earliest. Remove it and all overlapping classes from the set of available classes. Repeat this process until no classes remain. ▯ Sign up for the class that meets for the least amount of time. Remove it and all overlapping classes from the set of available classes. Repeat this process until no classes remain. ▯ Sign up for the class that con icts with the fewest other classes. Remove it and all overlapping classes from the set of available classes. Repeat this process until no classes remain. ▯ Sign up for the class that ends earliest. Remove it and all overlapping classes from the set of available classes. Repeat this process until no classes remain. Any of the above algorithms can be implemented in time O(nlogn) { a good exercise would be for you to write pseudo-code for it as part of your review. Unlike the dynamic programming algorithm, the correctness of this algorithm isn’t as easy to see from the description. Right now, the \proof" that it is correct relies on that I told you one of the four was correct, and you’ve seen that the other three aren’t correct. However, such a proof isn’t valid. Proving correctness: once we have an algorithm we believe is correct, we need to prove that it is. Each of the above algorithms can be described as \select some interval, remove con icting intervals, and recursively solve the problem on the rest." We would like to prove that there is an optimal solution that includes the ▯rst interval selected. Claim: There is an optimal solution that includes the ▯rst interval that we choose. Note that I am not claiming that all optimal solutions do. Would any optimal solution that includes our ▯rst interval also include any intervals that overlap with it? What is left to do to prove that the rest of our algorithm is correct? In-Class Exercise Freshly energized after ▯nishing the dynamic programming homework, a friend of yours in CSCI 570 has decided to open a new pizza chain called Algorithmic Pizza. Your friend is interested in servicing a very long stretch of road which currently has no pizza parlors. There are n houses located at various places on this road, and we want to make sure that each house is within 5 miles of an Algorithmic Pizza. Give an algorithm that will achieve this goal with the fewest possible pizza parlors placed, please. Prove that your algorithm achieves the optimal solution; that is, that no alternate arrangement can \cover" every house while using fewer pizza parlors. Minimum Spanning Trees Related reading: Kleinberg/Tardos x4.5, Goodrich/Tamassia Ch. 15, 7 Problem Statement: Given an undirected connected graph G and a function w(e) that maps edges to positive numbers, ▯nd an acyclic subset T ▯ E that connects all the vertices and whose total weight is minimized. Example: Which edges would you keep for the following graph? 8 7 B E G 4 2 9 4 A 11 D 14 I 7 6 10 9 2 1 C F H 1. Why is a tree the appropriate type of subgraph to solve this problem? Why couldn’t the solution contain a cycle? 2. Suppose C is a cycle within G. At least one edge in C won’t be in our solution. Which edge and why? 3. Can we come up with an algorithm based on this? 4. Could a correct algorithm omit edge (C,F)? Why or why not? 5. Could a correct algorithm omit edge (E,H)? Why or why not? 6. Given an edge, can we determine if it either can be, must be, or must not be in a minimum spanning tree? 7. Recall Dijkstra’s single-source shortest path tree algorithm. for each vertex v do intree(v) = false parent(v) = N/A dist(v) = 1 dist(s) = 0 while 9 vertex u with intree(u) = false do u vertex with intree(u) = false and smallest dist(u) intree(u) = true for each vertex v 2 adj[u] do if d(v) > d(u) + w(u;v) then d(v) = d(u) + w(u;v) parent(v) = u Can you modify Dijkstra’s shortest path tree algorithm to compute a minimum spanning tree? Does it matter which vertex is the start vertex s in this case? 8 7 B E G 4 2 9 4 A 11 D 14 I 7 6 10 9 1 2 C F H Scheduling with Deadlines Related reading: Kleinberg/Tardos x4.2 Let’s examine a di▯erent algorithm for scheduling intervals. In the last lecture, each interval had pre- designated start and end times. Instead, let’s consider a problem where each interval i is a task that must be completed; each has a designated time t , iut we can designate any start time for it. Each interval also has a deadline d i which can be di▯erent for each interval. We must assign each interval a start time in such a way that no two intervals overlap. Ideally, we would like to schedule everything to be ▯nished before its deadline, but this is not always possible. We say the lateness liof a job is how late it is ▯nished compared to its deadline, si+t ▯i , ir 0 if it has been completed by the deadline. Our goal is to minimize the maximum lateness: the amount by which the most late job exceeds its deadline. Example 1: What is the optimal schedule for the following? Time 1 2 3 Deadline 2 4 6 Example 2: What is the optimal schedule for the following? Time 1 2 3 4 Deadline 2 4 6 6 Some Possible Algorithms One of the following algorithms will correctly schedule the tasks. Decide which one you think it is, and show that the other two do not correctly schedule these. ▯ Sort the jobs by increasing time t i schedule them in that order. ▯ Sort the jobs by d i t i schedule them in that order. ▯ Sort the jobs by deadline d i schedule them in that order. Proof Since every schedule (optimal or otherwise) includes every task, we cannot follow the same model proof as the covering problems. Instead, we will show: ▯ When deciding start times, don’t leave any gaps; s i+1 = s i t i ▯ Any schedule that doesn’t agree with our algorithm has at least one pair of consecutive intervals i;i+1 that are inverted relative to our order. Note: You may take this fact as a given for the related homework problem. You do not need to prove it again. ▯ Any schedule with an inversion can be modi▯ed to be more like our algorithm’s output without making it worse. In-Class Exercise Business is booming for Algorithmic Pizza. You are the manager at a speci▯c store, and you have been ooded with n di▯erent pizza orders. Making a pizza is divided into two stages: (1) preparation, wherein the chef tosses the dough, and applies the sauce, cheese, and toppings, and (2) baking. Order i takes p timei in stage 1, and b iime in stage 2. You only have a single chef, so only a single pizza can be in stage one at any given time. You have a large oven, however, so you can bake any or all of the pizzas simultaneously. Give an algorithm that will choose an order in which to begin preparing the pizzas so that the last pizza comes out of the oven as soon as possible. Note that due to di▯erent baking times, the last pizza into the oven is not necessarily the last one out. Prove that your algorithm achieves this. Hu▯man Codes Associated Reading: K/T x4.8, G/T x10.3 Computers read bits, not characters. We translate each character to a string of bits which a computer can understand. What would be a good encoding? Identify problems and ine▯ciencies with the following encodings. ▯ a = 0, b = 1, c = 00, d = 01, e = 10, etc ▯ a = 00000, b = 00001, c = 00010, ..., z = 11001 ▯ a = 00000, b = 00001, ..., v = 10101, w = 1100, x = 1101, y = 1110, z = 1111 Formal de▯nition of the problem we’ll be solving today: each letter i has a frequency 0 ▯ f ▯ 1, with P i ifi= 1. We must choose a bit encoding for each letter such that no code is a prePx of another code. Let bibe the length of the encoding for letter i. Our goal is to ▯nd a valid encoding thafi i.imizes i Question: How could we use a binary tree to represent an encoding? Consider the following pre▯x code tree: S G H R J N A F I O T Exercise: What is the message that would be compressed as 000101000010111111111010011000, assuming a left-child to means ‘0’ and a right-child means ‘1’? Exercise: How would you encode the message \TROJANS" using the above tree? Suppose we want to encode a document with a pre▯x code that has the following frequencies: letter xfrequencyxf A 21% B 18% C 6% D 5% E 12% F 23% G 15% And suppose we have to do so via the following tree: Exercise: Where should the letters go in order to minimize the average bit length of a compressed message? Question: Is there a better tree for that distribution of characters? Question: Is there a way to produce the optimal tree for any given distribution of characters?

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.