Exercises

 

1. Consider the problem of storing n books on shelves in a library. The order of the books is fixed by the cataloging system and so cannot be rearranged. Therefore, we can speak of a book , where , that has a thickness and height . The length of each bookshelf at this library is L.

   Suppose all the books have the same height h (i.e. for all i, j) and the shelves are all separated by a distance of greater than h, so any book fits on any shelf. The greedy algorithm would fill the first shelf with as many books as we can until we get the smallest i such that does not fit, and then repeat with subsequent shelves. Show that the greedy algorithm always finds the optimal shelf placement, and analyze its time complexity.

2. (*) This is a generalization of the previous problem. Now consider the case where the height of the books is not constant, but we have the freedom to adjust the height of each shelf to that of the tallest book on the shelf. Thus the cost of a particular layout is the sum of the heights of the largest book on each shelf.
   • Give an example to show that the greedy algorithm of stuffing each shelf as full as possible does not always give the minimum overall height.
   • Give an algorithm for this problem, and analyze its time complexity. Hint: use dynamic programming.
3. (*) Consider a city whose streets are defined by an grid. We are interested in walking from the upper left-hand corner of the grid to the lower right-hand corner.

   Unfortunately, the city has bad neighborhoods, which are defined as intersections we do not want to walk in. We are given an matrix BAD, where BAD[i,j] = ``yes'' if and only if the intersection between streets i and j is somewhere we want to avoid.

   (a) Give an example of the contents of BAD such that there is no path across the grid avoiding bad neighborhoods.

   (b) Give an O( X Y ) algorithm to find a path across the grid that avoids bad neighborhoods.

   (c) Give an O( X Y ) algorithm to find the shortest path across the grid that avoids bad neighborhoods. You may assume that all blocks are of equal length. For partial credit, give an algorithm.

4. (*) Consider the same situation as the previous problem. We have a city whose streets are defined by an grid. We are interested in walking from the upper left-hand corner of the grid to the lower right-hand corner. We are given an matrix BAD, where BAD[i,j] = ``yes'' if and only if the intersection between streets i and j is somewhere we want to avoid.

   If there were no bad neighborhoods to contend with, the shortest path across the grid would have length (X-1) + (Y-1) blocks, and indeed there would be many such paths across the grid. Each path would consist of only rightward and downward moves.

   Give an algorithm that takes the array BAD and returns the number of safe paths of length X+Y-2. For full credit, your algorithm must run in O( X Y ).

5. (*) Given an array of n real numbers, consider the problem of finding the maximum sum in any contiguous subvector of the input. For example, in the array

   

   the maximum is achieved by summing the third through seventh elements, where 59+26+(-53)+58+97 = 187. When all numbers are positive, the entire array is the answer, while when all numbers are negative, the empty array maximizes the total at 0.

   • Give a simple, clear, and correct -time algorithm to find the maximum contiguous subvector.
   • Now give a -time dynamic programming algorithm for this problem. To get partial credit, you may instead give a correct divide-and-conquer algorithm.

6. In the United States, coins are minted with denominations of 1, 5, 10, 25, and 50 cents. Now consider a country whose coins are minted with denominations of units. They seek an algorithm that will enable them to make change of n units using the minimum number of coins.

   (a) The greedy algorithm for making change repeatedly uses the biggest coin smaller than the amount to be changed until it is zero. Show that the greedy algorithm does not always give the minimum number of coins in a country whose denominations are .

   (b) Give an efficient algorithm that correctly determines the minimum number of coins needed to make change of n units using denominations . Analyze its running time.

7. (*) In the United States, coins are minted with denominations of 1, 5, 10, 25, and 50 cents. Now consider a country whose coins are minted with denominations of units. They want to count how many distinct ways C(n) there are to make change of n units. For example, in a country whose denominations are , C(5) = 1, C(6) to C(9)=2, C(10)=3, and C(12)=4.
   1. How many ways are there to make change of 20 units from ?
   2. Give an efficient algorithm to compute C(n), and analyze its complexity. (Hint: think in terms of computing C(n,d), the number of ways to make change of n units with highest denomination d. Be careful to avoid overcounting.)
8. (**) Consider the problem of examining a string of characters from an alphabet on k symbols, and a multiplication table over this alphabet, and deciding whether or not it is possible to parenthesize x in such a way that the value of the resulting expression is a, where a belongs to the alphabet. The multiplication table is neither commutative or associative, so the order of multiplication matters.

   a b c

   a a c c

   b a a b

   c c c c

   For example, consider the following multiplication table and the string bbbba. Parenthesizing it (b(bb))(ba) gives a, but ((((bb)b)b)a) gives c.

   Give an algorithm, with time polynomial in n and k, to decide whether such a parenthesization exists for a given string, multiplication table, and goal element.

9. (*) Consider the following data compression technique. We have a table of m text strings, each of length at most k. We want to encode a data string D of length n using as few text strings as possible. For example, if our table contains (a,ba,abab,b) and the data string is bababbaababa, the best way to encode it is (b,abab,ba,abab,a) - a total of five code words. Give an O(nmk) algorithm to find the length of the best encoding. You may assume that the string has an encoding in terms of the table.

10. A company database consists of 10,000 sorted names, 40% of whom are known as good customers and who together account for 60% of the accesses to the data base. There are two data structure options to consider for representing the database:

    • Put all the names in a single array and use binary search.
    • Put the good customers in one array and the rest of them in a second array. Only if we do not find the query name on a binary search of the first array do we do a binary search of the second array.

    Demonstrate which option gives better expected performance. Does this change if linear search on an unsorted array is used instead of binary search for both options?

11. Suppose you are given an array A of n sorted numbers that has been circularly shifted k positions to the right. For example, is a sorted array that has been circularly shifted k=2 positions, while has been shifted k=4 positions.

    • Suppose you know what k is. Give an O(1) algorithm to find the largest number in A.
    • Suppose you do not know what k is. Give an algorithm to find the largest number in A. For partial credit, you may give an O(n) algorithm.
12. (*) Suppose that you are given a sorted sequence of distinct integers . Give an algorithm to determine whether there exists an index i such at . For example, in , . In , there is no such i.