
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.

(*)
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.

(*)
Consider a city whose streets are defined by an grid.
We are interested in walking from the upper lefthand corner of the
grid to the lower righthand 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.

(*)
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 lefthand corner of the
grid to the lower righthand 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 (X1) + (Y1) 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+Y2.
For full credit, your algorithm must run in O( X Y ).

(*)
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
divideandconquer algorithm.

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.

(*)
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.

How many ways are there to make change of 20 units from ?

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.)

(**)
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.

(*)
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.

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?

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.

(*)
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.