Description

Greedy Strategy
1. There are N robbers who have stolen N items. You would like to distribute the items among the robbers (one item per robber). You know the precise value of each item. Each robber has a particular range of values they would like their item to be worth (too cheap and they will not have made money, too expensive and they will draw a lot of attention). Devise an algorithm that either distributes the items so that each robber is happy or determines that there is no such distribution.
2. (Timing Problem in VLSI chips) Consider a complete binary tree with n = 2k leaves. Each edge has an associated positive number that we call the length of the edge (see figure below). The distance from the root to a leaf is the sum of the lengths of all edges from the root to the leaf. The root emits a clock signal and the signal propagates along all edges and reaches each leaf in time proportional to the distance from the root to that leaf. Design an algorithm which increases the lengths of some of the edges in the tree in a way that ensures that the signal reaches all the leaves at the same time while the total sum of the lengths of all edges is minimal. (For example, in the picture below if the tree A is transformed into trees B and C all leaves of B and C have a distance of 5 from the root and thus receive the clock signal at the same time, but the sum of the lengths of the edges in C is 17 while sum of the lengths of
the edges in B is only 15.)
3 2 1 2 1 2

2 2 3 3 2 1 1 3 4 4 3 3

B A C
3. Assume that you are given a complete graph G with weighted edges such that all weights are distinct. We now obtain another complete weighted graph G0 by replacing all weights w(i,j) of edges e(i,j) with new weights w(i,j)2.
(a) Assume that T is the minimal spanning tree of G. Does T necessarily remain the minimal spanning tree for the new graph G0?
(b) Assume that p is the shortest path from a vertex u to a vertex v in G. Does p necessarily remain the shortest path from u to v in the new graph G0?
4. Assume that you are given a complete weighted graph G with n vertices v1,…,vn and with the weights of all edges distinct and positive. Assume that you are also given the minimum spanning tree T for G. You are now given a new vertex vn+1 and the weights w(n+1,j) of all new edges e(n+1,j) between the new vertex vn+1 and all old vertices vj ∈ G, 1 ≤ j ≤ n. Design an algorithm which produces a minimum spanning tree T 0 for the new graph containing the additional vertex vn+1 and which runs in time O(nlogn).
Hint: Suppose N = A + B and pretend you wish to sell all items to Alice, but must choose B of them to give to Bob instead. Which ones do you want to give to Bob first? Then extend your approach to handle N < A + B as well.
6. Assume that you have an unlimited number of $2, $1, 50c, 20c, 10c and 5c coins to pay for your lunch. Design an algorithm that, given the cost that is a multiple of 5c, makes that amount using a minimal number of coins.
7. Assume that the denominations of your n + 1 coins are 1,c,c2,c3,…,cn for some integer c > 1. Design a greedy algorithm which, given any amount, makes that amount using a minimal number of coins.
8. Give an example of a set of denominations containing the single cent coin for which the greedy algorithm does not always produce an optimal solution.
9. Given two sequences of letters A and B, find if B is a subsequence of A in the sense that one can delete some letters from A and obtain the sequence B.
11. Let X be a set of n intervals on the real line. A subset of intervals Y ⊆ X is called a tiling path if the intervals in Y cover the intervals in X, that is, any real value that is contained in some interval in X is also contained in some interval in Y . The size of a tiling cover is just the number of intervals. Describe and analyse an algorithm to compute the smallest tiling path of X as quickly as possible. Assume that your input consists of two arrays XL[1..n] and XR[1..n], representing the left and right endpoints of the intervals in X.

A set of intervals. The seven shaded intervals form a tiling path.
12. Assume that you are given n white and n black dots lying in a random configuration on a straight line, equally spaced. Design a greedy algorithm which connects each black dot with a (different) white dot, so that the total length of wires used to form such connected pairs is minimal. The length of wire used to connect two dots is equal to the straight-line distance between them.

13. Assume you are given n sorted arrays Pi, 1 ≤ i ≤ n, of different sizes ei. You are allowed to merge any two arrays into a single new sorted array and proceed in this manner until only one array is left. Design an algorithm that achieves
this task and uses minimal total number of moves of elements of the arrays. Give an informal justification for why your algorithm is optimal.
14. A photocopying service with a single large photocopying machine faces the following scheduling problem. Each morning they get a set of jobs from customers. They want to schedule the jobs on their single machine in an order that keeps their customers the happiest. Customer i’s job will take ti time to complete. Given a schedule (i.e., an ordering of the jobs), let Ci denote the finishing time of job i. For example, if job i is the first to be done we would have Ci = ti, and if job j is done right after job i, we would have Cj = Ci +tj. Each customer i also has a given weight wi which represents his or her importance to the business. The happiness of customer i is expected to be dependent on the finishing time of their job. So the company decides that they want to order the jobs to minimise the weighted sum of the completion times, . Design an efficient algorithm to solve this problem. That is, you are given a set of n jobs with a processing time ti and a weight wi for job i. You want to order the jobs so as to minimise the weighted sum of the completion times, .
15. You are running a small manufacturing shop with plenty of workers, but just a single milling machine. You have to produce n items; item i requires mi machining time first, then pi polishing time by hand; finally it is packaged by hand and this takes ci amount of time. The machine can mill only one item at a time, but your workers can polish and package in parallel as many objects as you wish. You have to determine the order in which the objects should be machined so that the whole production is finished as quickly as possible. Prove that your solution is optimal.
17. Assume that you got a fabulous job and you wish to repay your student loan as quickly as possible. Unfortunately, the bank Western Road Robbery which gave you the loan has the condition that you must start your monthly repayments by paying off $1 and then each subsequent month you must pay either double the amount you paid the previous month, the same amount as the previous month or half the amount you paid the previous month. On top of these conditions, your schedule must be such that the last payment is $1. Design an algorithm which, given the size of your loan, produces a payment schedule which minimises the number of months it will take you to repay your loan while satisfying all of the bank’s requirements. If the optimality of your solution is obvious from the algorithm description, you do not have to provide any further correctness proof.
18. Alice wants to throw a party and is deciding whom to invite. She has n people to choose from, and she has created a list consisting of pairs of people who know each other. She wants to invite as many people as possible, subject to two constraints: at the party, each person should have at least five other people whom they know and at least five other people whom they do not know. Give an efficient algorithm that takes as input the list of n people and the list of all pairs who know each other and outputs a subset of these n people which satisfies the constraints and which has the largest number of invitees. Argue that your algorithm indeed produces a subset with the largest possible number of invitees.
19. In Elbonia cities are connected with one way roads and it takes one whole day to travel between any two cities. Thus, if you need to reach a city and there is no direct road, you have to spend a night in a hotel in all intermediate cities. You are given a map of Elbonia with toll charges for all roads and the prices of the cheapest hotels in each city. You have to travel from the capital city C to a resort city R. Design an algorithm which produces the cheapest route to get from C to R.
20. You are given a set S of n overlapping arcs of the unit circle. The arcs can be of different lengths. Find a largest subset P of these arcs such that no two arcs in P overlap (largest in terms of the total number of arcs, not in terms of the total length of these arcs). Prove that your solution is optimal.
21. You are given a set S of n overlapping arcs of the unit circle. The arcs can be of different lengths. You have to stab these arcs with a minimal number of needles so that every arc is stabbed at least once. In other words, you have
to find a set of as few points on the unit circle as possible so that every arc contains at least one point. Prove that your solution is optimal.
22. You are given a connected graph with weighted edges. Find a spanning tree such that the largest weight of all of its edges is as small as possible.
23. You need to write a very long paper titled “The Meaning of Life”. You have compiled a sequence of books in the order that you will need them, some of them multiple times. Such a sequence might look something like this:
B1,B2,B1,B3,B4,B5,B2,B6,B4,B1,B7,…
Unfortunately, the library only lets you borrow ten books at a time, so every now and then you have to make a trip to the library to exchange books. On each trip you can exchange any number of books. Design an algorithm which decides which books to exchange on each library trip so that the total number of trips which you will have to make to the library is as small as possible.
24. Assume that you are given a set X of n disjoint intervals I1,I2,…,In on the real line and a number k ≤ n. You have to design an algorithm which produces a set Y of at most k intervals J1,J2,…,Jk which cover all intervals from X
) and such that the total length of all intervals in Y is
minimal. (Note that we do not require that Y ⊆ X, i.e., intervals Jj can be new. For example, if your set X consists of intervals [1,2], [3,4], [8,9], and [10,12] and if k = 2, then you should choose intervals [1,4] and [8,12] of total length 3 + 4 = 7.)
25. Assume that you are given a complete undirected graph G = (V,E) with edge weights {w(e) : e ∈ E} and a proper subset of vertices U ⊂ V , U =6 V . Design an algorithm which produces the lightest spanning tree of G in which all nodes of U are leaves (there might be other leaves in this tree as well).
26. You are given a connected graph with weighted edges with all weights distinct. Prove that such a graph has a unique minimum spanning tree.
27. You have N students with varying skill levels and N jobs with varying skill requirements. You want to assign a different job to each student, but only if the student meets the job’s skill requirement. Design an algorithm to determine the maximum number of jobs that you can successfully assign.
28. There are N towns situated along a straight line. The location of the i’th town is given by the distance of that town from the westernmost town, di (so the location of the westernmost town is 0). Police stations are to be built along the line such that the i’th town has a police station within Ai kilometers of it. Design an algorithm to determine the minimum number of police stations that would need to be built.
29. There are N people that you need to guide through a difficult mountain pass. Each person has a speed in days that it will take to guide them through the pass. You will guide people in groups of up to K people, but you can only move as fast as the slowest person in each group. Design an algorithm to determine the fewest number of days you will need to guide everyone through the pass.
30. There are N courses that you can take. Each course has a minimum required IQ, and will raise your IQ by a certain amount when you take it. Design an algorithm to find the minimum number of courses you will need to take to get an IQ of at least K.