Description
1. A car factory has k assembly lines, each with n stations. A station is denoted by Si,j where i indicates
that the station is on the i
th assembly line (0<i<=k), and j indicates the station is the j
th station along
the assembly line (0<j<=n).
Each station is dedicated to some sort of work like engine fitting, body
fitting, painting and so on. So, a car chassis must pass through each of the n stations in that order before
exiting the factory. The time taken per station is denoted by ai,j . Parallel stations of the k assembly lines
perform the same task. After the car passes through station Si,j , it will continue to station Si, j + 1 unless
we decide to transfer it to another line.
Continuing on the same line incurs no extra cost, but transferring
from line x at station j-1 to line y at station j takes time tx,y. Each assembly line takes an entry time ei
and exit time xi which may be different for each of these k lines. Give an algorithm for computing the
minimum time it will take to build a car chassis.
2. There are n trading posts along a river numbered n, n-1,… 3, 2, 1. At any of the posts you can rent a
canoe to be returned at any other post downstream. (It is impossible to paddle against the river since the
water is moving too quickly). For each possible departure point i and each possible arrival point j(< i),
the cost of a rental from i to j is known C[i, j].
However, it can happen that the cost of renting from i to j is
higher than the total costs of a series of shorter rentals. In this case you can return the first canoe at some
post k between i and j and continue your journey in a second (and, maybe, third, fourth, …) canoe.
There
is no extra charge for changing canoes in this way. Give a dynamic programming algorithm to determine
the minimum cost of a trip by canoe from each possible departure point i to each possible arrival point
j.
For your dynamic programming solution, focus on computing the minimum cost of a trip from trading
post n to trading post 1, using up to each intermediate trading post.
3. Alice and Bob are playing an interesting game. They both each have a string, let them be a and b. They
both decided to find the biggest string that is common between the strings they have. The letters of the
resulting string should be in order as that in a and b but don’t have to be consecutive. Discuss its time
complexity.
4. You’ve started a hobby of retail investing into stocks using a mobile app, RogerGood. You magically
gained the power to see N days into the future and you can see the prices of one particular stock. Given
an array of prices of this particular stock, where prices[i] is the price of a given stock on the ith day, find
the maximum profit you can achieve through various buy/sell actions. RogerGood also has a fixed fee per
transaction.
You may complete as many transactions as you like, but you need to pay the transaction fee
for each transaction.
5. Tommy and Bruiny are playing a turn-based game together. This game involves N marbles placed in
a row. The marbles are numbered 1 to N from the left to the right. Marble i has a positive value mi
. On
each player’s turn, they can remove either the leftmost marble or the rightmost marble from the row and
receive points equal to the sum of the remaining marbles’ values in the row. The winner is the one with
the higher score when there are no marbles left to remove.
Tommy always goes first in this game. Both players wish to maximize their score by the end of the
game. Assuming that both players play optimally, devise a Dynamic Programming algorithm to return the
difference in Tommy and Bruiny’s score once the game has been played for any given input.
6. Consider a group of people standing in a line of size n. Everyone’s heights are given in an array
height [h0, h1, . . . , hn−1]. Write an efficient algorithm to find the longest subsequence of people with strictly
increasing heights and return it. Give the pseudo code and the recurrence relation.
