Next: About this document ... Up: My Home Page

Solutions to Homework 2

CSE 373, Prof. Skiena

Maximum marks alloted for a problem are indicated in brackets. Total credit: 70

2-1. The algorithm:

1.
Sort the 2n players according to their ranks, using Heap sort. (Or other $O(n\log n)$ sorting method)
2.
Put the first n players in one team, and the last n players in another.
Running time: Sorting will take $O(n\log n)$ time, and (2) will take O(n) time. Totally, It is an $O(n\log n)$ algorithm.
2-2. The algorithm: (suppose the 2n numbers are stored in array $A(1 \dots 2n))$

1.
Sort $A(1 \dots n)$ using heap sort.
2.
Partition the sorted array in the following way: $(A(1), A(2n)), (A(2), A(2n-1)), \ldots, (A(i), A(2n-i+1)), \ldots, (A(n), A(n+1))$ .

Proof of correctness: Suppose our algorithm does not give the right answer, then there exists another partition P, such that a pair (A(j), A(k)), j<k in P has the maximum sum, and is smaller than the maximum of $A(i)+ A(2n-i+1), i=1, \ldots, n$ . That is, suppose when $i=i_0, A(i_0)+A(2n-i_0+1) = max( A(i)+ A(2n-i+1)), i=1, \ldots, n$ , then A(j)+A(k)<A(i₀)+A(2n-i₀+1). For any $q\leq i_0$ , if $A(p)+A(2n-q+1) \in P$ , we have $A(p)+A(2n-q+1) \geq A(j)+A(k)<A(i_0)+A(2n-i_0+1)$ . but $A(2n-q+1)\geq A(2n-i_0+1)$ , We should have p < q, and thus $p \leq q-1$ . However, q numbers can not be paired with q-1 numbers. Contradiction. $\bigtriangleup$
Running time: Since sorting will take $O(n\log n)$ , the running time of the algorithm will be $O(n\log n)$ time.
2-3. We can use three buckets for the three colors. Since the items are already sorted by number, we can just scan them by this order and put each into the coresponding bucket. The numbers are still kept sorted in each bucket. then will can put all reds before all blues before all yellows. It is an O(n) time algorithm since we scan all the items only twice.
2-4.

a.
algorithm:

1.
Heap sort the array of numbers A(1, ..., n).
2.
mode = 0
3.
k=0
4.
FOR i = 1 TO n-1 DO
5.
if A(i)=A(i+1) then $k \leftarrow k+1$
6.
else if mode < k then $mode \leftarrow k$
7.
$k\leftarrow 0$
8.
END
9.
return mode
The running time is $O(n\log n)$ .
b. (4)
The algorithm:

1.
If There is only one number, return it as the answer.
2.
Put the n numbers into $\lfloor n/2 \rfloor$ pairs. If there is one number alone(lone number), save for future use.
3.
Discard all pairs in which the two numbers are not identical.
4.
Discard one number from a pair with two identical numbers.
5.
If the number of remaining numbers is odd, discard the lone number if it exists.
6.
Repeat the procedure for the remaining numbers.
Proof of Correctness: First observe that in step 3 we discard at least as many bad numbers as good ones, therefore, after step 3, there are more good numbers than bad ones remaining.
If there are odd number of identical pairs, the number of pairs containing good number must exceed the number of pairs containing bad numbers. So if we discard the lone number, the remaining set of numbers still hold the assumption that there are more good numbers than bad ones.
On the other hand, if there are even number of identical pairs, and there is a lone number, it might be the case that the bad number pairs equal to the good number pairs. In this case, the lone number must be good, thus keeping the lone number maintains the assumption. The number in the remaining set is obviously reduced to $\leq \lfloor n/2 \rfloor$ . Also according tothe pigeon hole principle, there is at least one number remained. Thus our algorithm is right. The running time will be $O(n+n/2+n/4+\cdots)=O(2n)=O(n)$ .
2-5. The algorithm:

1.
Heap sort S₁.
2.
For each number a_i in S₂ Do
3.
binary search x-a_i in S₁.
4.
If found, return true.
5.
End
6.
return false
The sorting will take $O(n\log (n))$ time. Each binary search will take $O(\log (n))$ time and there are n of them. Therefore the running time is $O(n\log (n))$ .
2-6

(a)
Find the max and min of the set takes O(n) time, and |max-min| is the number we want.
(b)
return |S(n)-S(1)|.
(c)
the algorithm:

1.
heap sort the n numbers.
2.
return the maximum of |S(i)-S(i+1)| for $i=1, \ldots, n-1$ .

(d)
same as the second step of (c).
2-11. the algorithm:

1.
median = partition(A, 1, n); low=1; high=n
2.
while $median \neq \lfloor n/2 \rfloor$ do
3.
if $median<\lfloor n/2 \rfloor$ then high = median-1
4.
else low = median+1
5.
median=partition(A, low, high)
6.
end
7.
return A(median)

Since each time the algorithm will partition one the part that contains the median, the running time will be $O(n)+O(n/2)+O(n/4)+\cdots=O(n)$ .
2-13.

(a)
$\theta(n^{2})$ . Since each time an array with length i will be partitioned two parts with length i-1 and 0.
(b)
$\theta(n\log n)$ . Since each time the array will be partitioned into the parts with similar length.
(c)
$\theta(n^2)$ . Since each time an array with length i will be partitioned two parts with length i-2 and 1.
(d)
$\theta(n\log n)$ . Since each time the array will be partitioned into the parts with similar length.
2-16. Define an array $P(1, \ldots, 2n)$ for the 2n starting and ending points of the n line segments which form the polygon. Let p_ip_i+1 be an edge of the polygon. $\alpha _{i} =\angle p_{i}qo$ , $\alpha _{i+1}=\angle p_{i+1}qo$ , then $P(2i-1).angle = \alpha_{i}, P(2i).angle = \alpha_{i+1}$ . If $\alpha_{i}<\alpha_{i+1}$ then P(2i-1).type = '(', P(2i).type = ')' Otherwise, P(2i-1).type = ')', P(2i).type = '('. The algorithm:

1.
Calculate all the angles and assign P.
2.
sort P according to the angle field of P.
3.
max=0; k=0;
4.
for i=1 to 2n do
5.
if P(i).type='(' then $k \leftarrow k+1$
6.
if max<k then $max \leftarrow k$
7.
else $k \leftarrow k-1$
8.
end
9.
return max
The running time of the algorithm is $O(n \log n)$ , since the sorting takes $O(n \log n)$ time.
4.

(a)
Sort the bills and checks using the name. After that you can run through the bills in serial order and identify the unpaid ones. The worst case complexity of this is $O(n \log n)$ .
(b)
This can be done using bucket sorting with different buckets for the various publishers. This can be done in O(n) time worst case.
(c)
Sort the cards on the key , name of the person issuing the book. This is $O(n \log n)$ worst case.
5. The Algorithm:

1.
Form a min heap with the array of n unsorted integers. Time take O(n).
2.
Repeat the next two steps k times.
3.
Delete the next top element in the heap and put it in the output.
4.
Move the last element to the top of the heap and heapify.

The third and fourth steps in the above expression is execute k times. The heapify in the fourth step takes $O(\log n)$ worst case. So overall time complexity is $O(k \log n)$ .
6. The Algorithm:
Our algorithm will assume that the element is present in the list. It does not handle the case where the element x is not there in the list.

1.
Let the heap be in array A. Let the value to be searched be value and k be as defined in the problem. Let x and k be globally accessible.
2.
Keep a counter count := 0 initially.
3.
Call function Checkcounter(A,0) (Root of the heap is at index '0').
4.
If count is some value not equal to k then the element is not the kth smallest element in the heap else it is. Checkcounter calls itself a maximum of 2k times for a total of k elements found to be less than or equal to x. thus this step is O(k).
function Checkcounter(A,position)

1.
If count > k return;
2.
If A $[position] > {\bf {value}}$ return;
3.
count++;
4.
Checkcounter(A, 2*position + 1);
Checkcounter(A, 2*position + 2);
7. The Data Structure to be used is a tree like structure implemented by means of another array of size n. Let us call this array B. The elements stored in the array B will be as follows. The first n/2 elements will have the sum of consecutive pairs of numbers of A e.g. sum of A[1] and A[2] will be stored in B[1], sum of A[3] and A[4] will be stored in B[2] and so on.
Similarly the next n/4 elements of B will store the sum of consecutive pairs of numbers in the range B[1..n/2]. Onwards if we fill up the rest of the array we will end up with an element containing the sum of all elements in A.
Now to add a value y to the ith number in A we will have to cascade the effect on A[i] through $\log (n)$ elements in B all the way till the element in B containing the sum of all the elements in A. Thus this step is now $O( \log n)$ in time.
The partial sum is now calculated using the partial sums stored in B. Any partial sum for elements from A[1] to A[i]. will require $\log n$ accesses to A and B and $\log (n)$ additions. An example is Partial-sum(7) is A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
Now the values of A[1] + A[2] + A[3] + A[4] , A[5] + A[6] are stored in elements in B. The element A[7] can be directly extracted from A. Thus the Partial-sum(7) requires only two additions and three array accesses which are both about $\log(7)$ .
8.

(a)
With US coinage the greedy algorithm will always give the least number of coins in change. The proof is as follows
If American coinage did not have the quarter, each coin would be an exact multiple of all lower denomination coins, thus a greedy algorithm would work.
When we add the quarter, for it to cause a greedy algorithm to fail, there must be a greedy solution that does include at least one quarter whereas the optimal solution does not. Further, the optimal solution must contain a total greater than 25 cents in coins under a quarter for the greedy algorithm to have made this error.
A solution cannot contain more than one quarter, or else a half dollar would have been chosen instead. By similar logic, the optimal solution cannot contain more than 4 dimes, 1 nickle, or 4 pennies.
If the optimal solution has zero dimes in it, it contains a maximum of 9 cents; less than 25 cents, so the greedy algorithm would be correct.
If the optimal solution has one dime in it, we have a maximum of 19 cents, again less than 25.
If the optimal solution has two dimes in it, it cannot have a nickle or else it would have substituted two dimes and a nickle for a quarter. Thus we have a maximum of 24 cents.
The optimal solution cannot have 3 or 4 dimes in it; 3 dimes would have been replaced by a quarter and a nickle.
Therefore, we have shown that it is not possible to have a case where the greedy algorithm chooses a quarter where the optimal solution does not contain one, and hence the greedy algorithm is optimal.
(b)
An example where the greedy algorithm does not work is making change for 48 pence. The greedy algorithm would give the change as one 30 pence coin, one 12 pence coin and one six pence coin. On the other hand the optimal change would be 2 twenty four pence coins.
(c)
Portuguese coinage is optimal. The proof is along the lines of (a).
(d)
Martian coinage is provable optimal for change since the minimu change we can make with martian coinage is the sum of the digits of the base-p number for the amount for which change is required.
9. No standard answer. The edit distances are 12 for the first two strings, 14 for the next pair and 6 for the third pair.
3-1. Proof by contradiction. Assume that the greedy algorithm doesn't give an optimal solution. Consider optimal solution S. We can transform S into a greedy solution as follows: Pack as many books as possible from shelf 2 to shelf 1, then from shelf 3 to shelf 2, etc. This will give the same placement as the greedy algorithm does, and uses no more shelves than S. Contradiction.
3-2.
- a counter example: let h_i, t_i be the hight and thickness of book i, respectively, and L be the length of the shelf. Consider 3 books with the following properties: t1=t2=t3=L/2; h1=1; h2=2; h3=3.
  greedy algorithm will give: h1, h2 on shelf 1, h3 on shelf 2. sum of heights is Max(h1, h2)+Max(h3)=h2+h3=4.
  optimal solution: h1 on shelf 1, h2, h3 on shlef 2. the sum of heights is Max(h1)+Max(h2, h3)=h1+h3=3. It is better than the greedy algorithm solution.
- Define cost(i) to be the cost of the optimal layout of books $b_{1} , b_{2}, \cdots, b_{i}$ . T(0)=0 if there is no book to be placed. Let $cost(i, j), (i \leq j)$ represent the cost of putting exactly the books $b_{i}, \ldots, b_{j}$ on the same shelf. If $b_{i}, \ldots, b_{j}$ do not fit on the same line, set $cost(i, j)=\infty$ .
  
  $\begin{displaymath}cost(i, j)=\left \{\begin{array}{ll} max(b_{i}, \ldots, b_{j}... ...i}^{j} h_{k} \leq L \\ \infty & otherwise \end{array} \right. \end{displaymath}$
  
  We can now phrase the optimal substructure properties of the problem as follows:
  
  $\begin{displaymath}T(j) = \min_{1 \leq i < j}(cost(i, j)+T(i-1))\end{displaymath}$
  
  The algorithm:
  
  1.
  T(0)=0
  2.
  for j=1 to n do
  3.
  $T(j) = \min_{1 \leq i < j}(cost(i, j)+T(i-1))$
  4.
  end
  5.
  return T(n)
  Time complexity: There are n iterations, eac computes a minimum. It only takes O(M) steps to compute this minimum where M is the maximum number of books that can be put in one shelf. The computation of cost(i, j) takes O(M) time. Thus each iteration of the loop takes O(M²) time. Since there are n iterations, the total running time becomes O(nM²). It turns out that we can improve the performance to O(nM) by incrementally computing the cost(i, j). If M is at the order of n, then the overall time complexity will be O(n²). If M can be considered as a constant, then the overall running time will be O(n).
3-5.
- The $\theta(n^2)$ algorithm is very simple. For all i,j < n (n is the size of the array) calculate the sum of all elements in the array from indices i to j inclusive. The highest such sum will indicate the contiguous subvector with the maximum sum. This algorithm is obviously $\theta(n^2)$ since one has to consider at most n²/2 + n/2 sums. If we compute these sums in a two dimensional array then we can compute the sum of all elements from i to j by just adding the j th element to the sum of all elements from i to j-1. This is done in constant time. Hence this algorithm is $\theta(n^2)$ .
- The recurrence relationship for the dynamic programming algorithm is given by the following relationship. Assuming A[1..n] is the array holding the numbers and D[0..n] is the array holding the partial sum of the present contiguous subvector. maxsum = max(maxsum , D[i])
  D[i] = D[i-1] + A[i] if D[i-1] > 0
  D[i] = A[i] otherwise
  The algorithm is
  
  1.
  initialize
  max=0; maxstartrange=0; maxendrange=0;
  D[0] =0; maxsum=0;
  2.
  for i= 1 to n do
  3.
  if D[i-1] > 0 then
  4.
  D[i] = D[i-1] + A[i];
  5.
  endrange=i;
  6.
  else
  7.
  D[j] = A[j];
  8.
  startrange=i;
  9.
  if max( maxsum , D[i]) > maxsum then
  10.
  maxsum = D[i];
  11.
  maxstartrange = startrange;
  12.
  maxendrange = endrange;
  13.
  return maxstartrange, maxendrange, maxsum
3-8. Let $x_{i}, \ldots, x_{j}$ be the string, and t be the goal element. Define V(i, j) be the set of all possible values that can be got from $x_{i}, \ldots, x_{j}$ . The algorithm:

1.
initialize: V(i, i) = x_i for $1 \leq i \leq n$ .
2.
for j = 2 to n do
3.
for i = j-1 downto 1 do
4.
for k = i to j do
5.
for $y\in V(i, k), z\in V(k+1, j)$ do
6.
add yz to V(i, j)
7.
end
8.
end
9.
end
10.
end
11.
if $t \in V(1, n)$ return true else return false
Since there are at most k symbols in V(i, j), the inner loop to calculate V(i, j) from V(i, k), V(k+1, j) will take O(k²) time. There are three outer loops, so the overall running time will be O(n³k²).
13.

(a)
The algorithm is

1.
initialise low = 1, high= N
2.
search array T for $S[\lfloor (low + high)/2 \rfloor]$ using Binary Search. Use a binary search modified to return the index of the nearest lower element to the searched element. Let the index returned be i.
3.
if $i + \lfloor (low + high)/2 \rfloor > n$ then
4.
$low=\lfloor (low + high)/2 \rfloor + 1$ ;
5.
else
6.
if $i + \lfloor(low + high)/2 \rfloor < n$ then
7.
$high=\lfloor(low + high)/2 \rfloor - 1$ ;
8.
else
9.
return $S[\lfloor (low + high)/2 \rfloor]$
10.
if low < high then
11.
goto step 2.
12.
initialise low=1, high=N
13.
search array S for $T[\lfloor (low + high)/2 \rfloor]$ using Binary Search. Use a binary search modified to return the index of the nearest lower element to the searched element if searched element is not found. Let the index returned be i.
14.
if $i + \lfloor (low + high)/2 \rfloor > n$ then
15.
$low=\lfloor (low + high)/2 \rfloor + 1$ ;
16.
else
17.
if $i + \lfloor(low + high)/2 \rfloor < n$ then
18.
$high=\lfloor(low + high)/2 \rfloor - 1$ ;
19.
else
20.
return $T[\lfloor (low + high)/2 \rfloor]$
21.
if low < high then
22.
goto step 13.

The above algorithm has time complexity $O((\log (n))^2)$ . This is because we are narrowing down the range of our element in one array using a binary search like procedure on the basis of a binary search on the current key in the other array. Each step taken to narrow down in the source array requires a search of $O(\log(n))$ in the other array. Since the number of narrowing down steps in the source array will be $O(\log(n))$ the resultant algorithm's complexity is $O((\log(n))^2)$
(b)
A faster algorithm for this problem is the following.

1.
Start with the full arrays S and T. Compare the middle elements (medians) of both.
2.
If both the middle elements are equal return one of them and the algorithm terminates.
3.
In case the two elements are not equal then for the next round we retain the larger half of the array with the larger median and the smaller half of the array with the smaller median. We are guaranteed that the median for the combination of the elements of both arrays will be retained in our next round elements.
4.
Repeat the process with whatever elements are left at each iteration. The final iteration occurs when there are only 4 elements in consideration.
5.
From the last four elements find the second smallest element. This is the median of the combination of our two sorted arrays.
This algorithm is $\theta(\log n)$ because at each iteration we reduce the search space for median by half. The algorithm willl therefore terminate in about $\log (2*n)$ steps i. e. $\theta(\log n)$ . This is also the lower bound for this problem.
3-11.
- the O(1) algorithm:
  
  1.
  $k'\leftarrow k$ mod n
  2.
  if $k' \neq 0$ then return A(k')
  3.
  else return A(n)
- the $O(\log n)$ algorithm:
  
  1.
  $low \leftarrow 1$ ; $high \leftarrow n$ ;
  2.
  while low < high-1 do
  3.
  $k \leftarrow \lfloor low+high \rfloor$
  4.
  if A(k) < A(low) then $high \leftarrow k$
  5.
  else $low \leftarrow k$
  6.
  end
  7.
  return max(A(low), A(high))
  
  in each iteration the array will be cut into half the length, and the max of A will always in the subarray. Thus the max of A will be returned and the running time is $O(\log n)$ .

About this document ...

Next: About this document ... Up: My Home Page

Steve Skiena
2000-11-01