MTL342 -  Design and Analysis of Algorithms - Assignment 2 - Solved

Question 3.1
You are given a set of n types of rectangular 3-D boxes, where the ith box has height hi, width wi and depth di (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box. Design an algorithm to create a stack that is as tall as possible.      [3 points]

Question 3.2
You have a set of n integers each in the range [0,K]. Find an algorithm to partition these integers into two subsets such that you minimize |S1S2|, where S1 and S2 denote the sums of the elements in each of the two subsets. [3 points]

Question 3.3
Given two strings a and b which contain “wild-card” characters “∗” and “?”, we want to match the strings in a way, where if one string contains “∗”, it can be matched with any character or number of characters in the other string. On the other hand, if one string has the character “?”, it can be matched with any one character of the other string. Given two strings of length m and n, design an algorithm that checks whether the strings match. [4 points]

Question 3.4
There are A coins (Assume A is even) in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins, Assume that you go first. Return the maximum amount of money you can win. Can you find a simple strategy for not losing (making as much money as your opponent makes)? [4 points]

Question 3.5
You are given an p×q chessboard with some squares removed. Two rooks can attack each other if placed in the same row or in the same column, if there is no removed square between then in that row or column. Find an algorithm to place the maximum number of rooks on the board, such that none of them can attack each other. [3 points]

Question 3.6
Decide whether each of the following statements is true or false. If it is true, give a short explanation. If it is false, give a counterexample.

                   →−             →−

(a)     Let G = (V ; E) be a flow network with source s and sink t, and a positive integer capacity

1

→−

ce on every edge e. If f is a maximum s−t flow in G, then f saturates every edge out of s with flow (i.e., for all edges e out of s, we have f(e) = ce).

                   →−             →−

(b)    Let G = (V ; E) be a flow network with source s and sink t, and a positive integer capacity ce on every edge e. Let (A,B) be a minimum capacity s-t cut with respect to the capacities →−

{ce | e ∈ E}. Now suppose we add 1 to every capacity; then (A,B) is still a minimum s-t

→−

                 cut with respect to these new capacities {ce + 1 | e ∈ E}                                                    [3 points]