Description
1 Question 1
I solved this question through the following logic:
1. Consider strings A = a0a1a2a3…an−1 and B = b0b1b2b3…bm−1.
2. For each letter l in B: If l is equal to the first letter in A, add the number of occurences found
by repeating this procedure with strings C and D where C = a1a2a3…an−1 and D = l…bm−1
Note: The above is a recursive algorithm and the base case is when a is of length 1, in which we
just add 1 to the number of occurences (when l == a0) instead of repeating the procedure.
The following c++ code also defines the algorithm:
int getOccurenceCount ( s t r i n g a , s t r i n g b ){
char bchar = b [ 0 ] ;
int o c c u r e n c e = 0 ;
for ( int i = 0 ; i < b . s i z e ( ) ; ++i ){
i f ( a [ 0 ] == b [ i ] ) {
i f ( a . s i z e ( ) == 1 )
o c c u r e n c e++;
e l s e
o c c u r e n c e += getOccurenceCount ( a . s u b s t r ( 1 , a . s i z e ( ) − 1 ) ,
b . s u b s t r ( i + 1 , b . s i z e ( ) − 1 ) ) ;
}
}
return o c c u r e n c e ;
}
int main ( int argc , char ∗ argv [ ] ) {
s t r i n g a ;
s t r i n g b ;
a = argv [ 1 ] ;
b = argv [ 2 ] ;
c ou t << getOccurenceCount ( a , b ) << e n dl ;
return 0 ;
}
1
2 Question 2
I solved this question by the following logic:
1. Create an array A of pairs<weight, IQ> and sort by descending IQ.
2. Then we only look at the weights part of each array element. We need to find the largest
subsequence that is ascending. Since that will mean that IQ is descending and weight is
ascending which is what the question asks for.
3. To do this we:
Create an array of arrays of pairs<weight, IQ> L.
L[0][0] ← A[0];
for i = 1 .. A.size() we set L[i] to equal the longest increasing subsequence that finishes at
element i. (Remember that we are only looking at the weights part of the pair).
We then iterate through L and find k that has L[k] as the longest in L.
This is then (one of) the longest increasing subset(s).
Pseudocode:
Imagine that we are given the elephants in an array of struct elephant{double weight, double IQ}.
el e p h a n t A[ n ] ;
A. s o r t ( by el e p h a n t . IQ ) ;
A. r e v e r s e ;
el e p h a n t L [ ] [ ] ;
L [ 0 ] . push back (A[ 0 ] ) ;
for i = 1 . . A. s i z e ( ) {
for j = 0 . . i − 1{
i f ( (A[ j ] . wei gh t < A[ i ] . wei gh t ) && (L [ i ] . s i z e ( ) < L [ j ] . s i z e ( ) + 1 ) ) {
L [ i ] = L [ j ] ;
}
}
L [ i ] . push back (A[ i ] ) ;
}
/∗ L i s now such t h a t L [ k ] h o l d s t h e l a r g e s t i n c r e a s i n g s u b s e q u e n c e
t h a t ends w i t h e l e p h a n t A[ k ] ∗/
el e p h a n t se q [ ] ;
int l o n g e s t I n d e x = 0 ;
for i = 0 . . L . s i z e ( ) {
i f (L [ i ] . s i z e ( ) > L [ l o n g e s t I n d e x ] . s i z e ( ) ) {
l o n g e s t I n d e x = i ;
}
}
se q = L [ l o n g e s t I n d e x ] ;
/∗ s e q now h o l d s t h e r e q u i r e d s u b s e q u e n c e o f e l e p h a n t s ∗/
2
3 Question 3
I solved this question by the following algorithm:
1. Start at the root. Now find the maximal sum with this root allowed to be included.
2. To do this, we find the maximal sum of each of the children for two cases (we also keep a list
for each case):
(a) The child is allowed to be included.
(b) The child is NOT allowed to be included.
We then decide whether we should use the root node or the children of the root for a maximal
sum.
i.e.
if (ΣChildrenusing their root node − ΣChildrennot using their root node > root) :
Don0
t use the root node
else :
Do use the root node
3. We continue recursively until we reach the leaves and hence reach the base case. We can then
unravel the recursion to determine the solution to the original problem.
More detailed description and pseudocode:
Notes:
• Assume we are given a tree T with the president as the root node.
• In the below code, 0 represents a function or list in which the root node is allowed to be
included whilst 1 represents a function or list in which the root node is NOT allowed to be
included.
• getFunLevel(List l) is a simple function that adds the fun level of each of the elements in list
l and returns the result. This function has not been coded for sake of succinctness.
/∗
∗ Func t ion t h a t r e t u r n s a l i s t o f t h e maximal sum o f t h e t r e e bel ow
∗ t h e node g i v e n in t h e i n p u t parame ter w i t h t h i s r o o t node a l l ow e d
∗ t o be i n c l u d e d in t h i s l i s t .
∗/
L i s t getMaximal0 ( node n ){
/∗ Base c a se − when we have re ac he d a l e a f we j u s t need t o r e t u r n
a l i s t c o n t a i n i n g j u s t t h i s l e a f ∗/
i f ( n has no c h i l d r e n ){
return L i s t ( n ) ;
}
/∗ L i s t t h a t c o n t a i n s t h e nodes in t h e t r e e t h a t are a
3
maximal sum i f t h e r o o t node i s no t used .
i . e . t h e r o o t nodes o f t h e c h i l d r e n are a l l ow e d . ∗/
L i s t sumChildren0 ;
for each c h i l d c o f n :
sumChildren0 . add ( getMaximal0 ( c ) ) ;
/∗ L i s t t h a t c o n t a i n s t h e nodes in t h e t r e e t h a t are a
maximal sum i f t h e r o o t node i s used .
i . e . t h e r o o t nodes o f t h e c h i l d r e n are NOT a l l ow e d . ∗/
L i s t sumChildren1 ;
for each c h i l d c o f n :
sumChildren1 . add ( getMaximal1 ( c ) ) ;
/∗ See p t 2 o f t h e l o g i c above ∗/
i f ( ge tFunLevel ( sumChildren0 ) − ge tFunLevel ( sumChildren1 ) > ge tV al ( n ) ) {
return sumChildren0 ;
} e l s e {
sumChildren1 . add ( n ) ;
return sumChildren1 ;
}
}
/∗
∗ Func t ion t h a t r e t u r n s a l i s t o f t h e maximal sum o f t h e t r e e bel ow
∗ t h e node g i v e n in t h e i n p u t parame ter w i t h t h i s r o o t node NOT a l l ow e d
∗ t o be i n c l u d e d in t h i s l i s t .
∗/
L i s t getMaximal1 ( node n ){
/∗ Base c a se − i f n i s a l e a f and we can ’ t use i t t hen we
need t o j u s t r e t u r n an empty l i s t ∗/
i f ( n has no c h i l d r e n ){
return L i s t ( ) ;
}
L i s t sumChildren1 ;
for each c h i l d c o f n :
sumChildren1 . add ( getMaximal0 ( c ) ) ;
return sumChildren1 ;
}
/∗
∗ The main f u n c t i o n t h a t g e t s t h e p a r t y l i s t f o r t h e g i v e n t r e e T .
∗/
L i s t g e tP a r t y Li s t ( Tree T){
/∗ We s im ply need t o r e t u r n t h e p a r t y l i s t found by g e t t i n g t h e
maximal sum o f t h e t r e e o f t h e r o o t node w i t h t h e r o o t node
a l l ow e d t o be i n c l u d e d ∗/
return ( getMaximal0 (T−>r o o t ) ) ;
}
4
4 Question 4
This problem can be defined by the following recurrence:
The minimum cost of cutting the stick is equal to the minimum of (the minimum cost of cutting
the left part of the stick plus the right part of the stick for every possible cut) plus the cost of the
initial cut.
More simply, if we define the cuts required to be at positions c1, c2, …, cn and the end points of the
stick to be c0 and cn+1 respectively and C(c0, cn+1) to be the problem. We can split the original
problem into two sub-problems:
C(c0, cn+1) = min
k∈(1,…,n)
[C(c0, ck) + C(ck, cn+1)] + cost(c0, cn+1)
Where cost(a, b) is simply the cost of making a cut on the stick with endpoints a, b.
So cost(a, b) = b − a
i.e. the length of the stick.
We can generalise this recurrence to be valid for any sub-stick:
C(ci
, cj ) = min
k∈(i+1,…,j−1)
[C(ci
, ck) + C(ck, cj )] + cost(ci
, cj )
Thus, for a DP solution we simply recurse according to the above whilst keeping the value for any
sub-problem we solve.
Pseudo-code:
Notes:
• Let C be an array that holds the location of all cuts, IN ORDER. Including the end points.
g l o b a l v a r i a b l e s :
int dp [ numCuts + 2 ] [ numCuts + 2 ]
int C[ numCuts ] ;
int minCost ( int i , int j ){
/∗ I f t h e r e are no c u t s in be tween p o i n t i and p o i n t j
t hen t h e c o s t i s 0 ∗/
i f ( j == i + 1 ){
dp [ i ] [ j ] = 0 ;
return 0 ;
}
/∗ I f we have a l r e a d y computed t h i s we do no t need t o
recompu te ∗/
i f ( dp [ i ] [ j ] != −1)
return dp [ i ] [ j ] ;
/∗ Apply t h e r e c u r s i o n ∗/
dp [ i ] [ j ] = minCost ( i , i +1) + minCost ( i +1, j ) ;
for ( int k = i + 1 ; k < j ; ++k ){
int tempMin = minCost ( i , k ) + minCost ( k , j ) ;
5
i f ( tempMin < dp [ i ] [ j ] )
dp [ i ] [ j ] = tempMin ;
}
dp [ i ] [ j ] += C[ j ] − C[ i ] ;
/∗ r e t u r n t h e answer ∗/
return dp [ i ] [ j ] ;
}
int ge tMinC o s tO fS tick ( S ti c k s ){
return ( minCost ( 0 , s . numCuts + 1 ) ) ;
}
6
5 Question 5
A naive way to solve this is to simply:
1. If the first character of X matches the first character of Z we move one character ahead in X
and Z and then recursively check.
2. If the first character of Y matches the first character of Z we move one character ahead in Y
and Z and then recursively check.
3. If either 1 or 2 returns true then we have an interleaving.
However, this has time complexity of O(2n
). To make the algorithm more efficient I have used a
DP solution in which we store the solutions of sub-problems in a table.
Let us store solutions of the sub problems in a 2D table:
bool interLeaved[m][n]
Now interLeaved[i][j] == True iff (Z[0..i+j-1] is an interleaving of X[0..i-1] and Y[0..j-1])
Now for the sub-problems to be useful we need to be able to apply them to the original problem. There are 5 cases to ’expand’ the sub problems and 1 base case:
1. Case 1 – base case when X and Y are empty they interleave an empty string Z. Thus interLeaved[0][0] = TRUE
2. Case 2 – X is empty:
interLeaved[i][j] = True iff((Y[j – 1] == Z[j – 1] && interLeaved[0][j – 1]
3. Case 3 – Y is empty:
interLeaved[i][j] = True iff((X[i – 1] == Z[i – 1]) && interLeaved[i – 1][0])
4. Case 4 – Current character of Z matches with current character of X but does NOT match
current character of Y:
interLeaved[i][j] = True iff((interLeaved[i – 1][j]) && Z[i + j – 1] == X[i – 1])
5. Case 5 – Current character of Z matches with current character of Y but does NOT match
current character of X:
interLeaved[i][j] = True iff((interLeaved[i][j – 1]) && Z[i + j – 1] == Y[j – 1])
6. Case 6 – Current character of Z matches both current character of X and Y:
interLeaved[i][j] = True iff((interLeaved[i – 1][j] || interLeaved[i][j – 1]) && Z[i + j – 1] == X[i
– 1], Y[j – 1])
Pseudocode:
bool i s I n t e r L e a v e d ( s t r i n g X, s t r i n g Y, s t r i n g Z , int m, int n ){
\∗ C re a te DP t a b l e and s e t a l l t o f a l s e o r i g i n a l l y ∗/
bool i n t e rL e a v e d [m+ 1][ n+1] = {FALSE} ;
7
/∗ Note t h a t i r e p r e s e n t s how many l e t t e r s o f X
we are c o n s i d e r i n g and j r e p r e s e n t s how many
l e t t e r s o f Y we are c o n s i d e r i n g ∗/
for ( int i = 0 ; i <= m; ++i ){
for ( int j = 0 ; j <= n ; ++j ){
\∗ Case 1 − The b a se Case :
two empty s t r i n g s have an
empty s t r i n g a s an i n t e r l e a v i n g ∗/
i f ( i == 0 && j == 0 )
i n t e rL e a v e d [ 0 ] [ 0 ] = TRUE;
/∗ Case 2 − X i s empty ∗/
e l s e i f ( i == 0 && Y[ j − 1 ] == Z [ j − 1 ] )
i n t e rL e a v e d [ 0 ] [ j ] == i n t e rL e a v e d [ 0 ] [ j − 1 ] ;
/∗ Case 3 − Y i s empty ∗/
e l s e i f ( j == 0 && X[ i − 1 ] == Z [ i − 1 ] )
i n t e rL e a v e d [ i ] [ 0 ] == i n t e rL e a v e d [ i − 1 ] [ 0 ] ;
/∗ Case 4 − Z [ i + j − 1 ] ma tches X[ i − 1 ]
BUT doe s NOT match Y[ j − 1 ] ∗/
e l s e i f (X[ i − 1 ] == Z [ i + j − 1 ] && Y[ j − 1 ] != Z [ i + j − 1 ] )
i n t e rL e a v e d [ i ] [ j ] = i n t e rL e a v e d [ i − 1 ] [ j ] ;
/∗ Case 5 − Z [ i + j − 1 ] ma tches Y[ j − 1 ]
BUT doe s NOT match X[ i − 1 ] ∗/
e l s e i f ( Y[ j − 1 ] == Z [ i + j − 1 ] &&
X[ i − 1 ] != Z [ i + j − 1 ] )
i n t e rL e a v e d [ i ] [ j ] = i n t e rL e a v e d [ i ] [ j − 1 ] ;
/∗ Case 6 − Z [ i + j − 1 ] ma tches X[ i − 1 ]
AND ma tches Y[ j − 1 ] ∗/
e l s e i f (X[ i − 1 ] == Z [ i + j − 1 ] &&
Y[ j − 1 ] == Z [ i + j − 1 ] )
i n t e rL e a v e d [ i ] [ j ] = ( i n t e rL e a v e d [ i − 1 ] [ j ]
| | i n t e rL e a v e d [ i ] [ j − 1 ] ) ;
e l s e
/∗ No th ing ma tches so l e a v e as FALSE ∗/
}
}
return i n t e rL e a v e d [m] [ n ] ;
}
8
6 Question 6
I solved this question by the following logic:
1. Sort turtles in increasing order of (weight + strength).
2. For each i from 1..n find the lightest legitimate tower using turtles T0, …, Ti for each height
k = i..1. By using the solution for the lightest legitimate tower of height k – 1 using turtles
T0, …, Tj for j = i – 1.
Note: The base case is when i = 0, the highest legitimate tower is simply T0.
Explanation and more detailed description of algorithm:
• Let us number the turtles in a tower from Top to bottom.
• By ordering the turtles in increasing order of (weight + strength) we restrict the solution to
only containing towers that increase in (weight + strength) from the top of the tower to the
bottom of the tower. However we can show that this does not miss any optimal solutions:
– Consider a tower that is optimal such that there exists two turtles Ti and Ti+1 such that
Ti
is directly above Ti+1 in the tower and wi +si > wi+1 +si+1. i.e. An optimal solution
that our dynamic programming solution would miss.
– Consider swapping Ti and Ti+1:
– Ti+1 will definitely not crack since it has less weight on it than before.
– The turtles above the pair are clearly not affected and the turtles below the pair are not
affected since the same total weight is above them.
– Thus we only need to consider Ti
. Let wabove denote the total weight of the turtles above
the pair. Thus, Ti must withstand wabove + wi+1 i.e. si > wabove + wi+1 must hold.
wi + si > wi+1 + si+1 (1)
∴ si > wi+1 + si+1 − wi (2)
Also, since Ti+1 was in a legitimate tower before the swap:
si+1 ≥ wabove + wi (3)
Then, by subbing (3) into (2):
si > wi+1 + (wabove + wi) − wi (4)
≥ wi+1 + wabove (5)
∴ si > wabove + wi+1 as required (6)
– Thus, we have shown that if there exists an optimal solution that does not follow the
restriction that we place on the solution (namely that wi + si < wi+1 + si+1 for all i),
we can swap adjacent turtles without affecting the legitimacy of the tower. We can then
continue swapping adjacent turtles for which wi + si < wi+1 + si+1 is broken until we
obtain a legitimate tower such that wi + si < wi+1 + si+1 holds for all i. Thus, we have
a different optimal solution to the given one, but of the same height.
9
Algorithm run through:
Consider we have 5 turtles with the following weight, strength values:
{1, 6}, {2, 2}, {3, 8}, {5, 4}, {2, 4}.
We then sort them in increasing order of weight + strength:
T1 = {2, 2}
T2 = {2, 4}
T3 = {1, 6}
T4 = {5, 4}
T5 = {3, 8}
We then run through the algorithm:
i = 1 :
Tower [ 1 ] = 2 \\ c o n t ai n s onl y T1
i = 2 :
k = 2 :
Can Tower [ 1 ] be ex tended by adding T2 t o the bottom ? YES
Tower [ 2 ] = 4
\\ c o n t ai n s T1 , T2
k = 1 :
Do we have a new l i g h t e s t tower o f s i z e 1? YES
Tower [ 1 ] = 2
\\ c o n t ai n s T1 s i n c e T2 i s not LIGHTER than T1
i = 3 :
k = 3 :
Can Tower [ 2 ] be ex tended by adding T3 t o the bottom ? YES
Tower [ 3 ] = 5
\\ c o n t ai n s T1 , T2 , T3 s i n c e T3 . s t r e n g t h >= Tower [ 2 ]
k = 2 :
Do we have a new l i g h t e s t tower o f s i z e 2? YES.
Tower [ 2 ] = 3
\\ c o n t ai n s T1 , T3 s i n c e T3 . wei gh t < T2 . wei gh t
k = 1 :
Tower [ 1 ] = 1
\\ c o n t ai n s T3
i = 4 :
k = 4 :
Can Tower [ 3 ] be ex tended by adding T4 t o the bottom ? NO
// S ince T4 . s t r e n g t h < Tower [ 3 ] .
k = 3 :
Do we have a new l i g h t e s t tower o f s i z e 3? NO.
// S ince i f we ex t e n d Tower [ 2 ] by a d d ing T4 t o t h e bottom , i t i s h e a v i e r thk = 2 :
Do we have a new l i g h t e s t tower o f s i z e 2? NO.
// S ince i f we ex t e n d Tower [ 1 ] by a d d ing T4 t o t h e bottom , i t i s h e a v i e r thk = 1 :
Do we have a new l i g h t e s t tower o f s i z e 1? NO.
10
// S ince T4 . w e i g h t > Tower [ 1 ]
i = 5 :
k = 4 :
Can Tower [ 3 ] be ex tended by adding T5 t o the bottom ? YES.
// S ince T5 . s t r e n g t h = 8 < Tower [ 3 ] = 5 .
At th is p oi n t we have f i n i s h e d s i n c e we have gone through a l l i <= numTurtles .
Thus an op tim al s o l u t i o n i s :
Tower [ 4 ] = {Tower [ 3 ] , T5} = {T1 , T2 , T3 , T5}
11
