Description
Q1. 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.
Below figure provides one example to explain the problem. The example shows k=2 assembly
lines and 5 stations per line. To illustrate how to evaluate the cost, let’s consider two cases: If we
always use assembly line 1, the time cost will be:
e1 + a1,1 + a1,2 + a1,3 + a1,4 + a1,5 +x1
If we use stations s1,1
-> s2,2
-> s1,3
-> s2,4
-> s2,5
, the time cost will be :
e1 + a1,1 + t1,2+ a2,2 + t2,1 +a1,3 +t1,2+a2,4+a2,5+x2
a) Define (in plain English) subproblems to be solved. (2 pts)
b) Recursively define the value of an optimal solution (recurrence formula) (8 pts)
c) Describe (using pseudocode) how the value of an optimal solution is obtained
using iteration. Make sure you include any initialization required. (8 pts)
d) What is the complexity of your solution in part b? (4 pts)
Q2.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. It is 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.
a) Define (in plain English) subproblems to be solved.
b) Recursively define the value of an optimal solution (recurrence formula) (5 pts)
c) What will be the iterative program for the above ? (5 points)
d) Analyze the running time of your algorithm in terms of n. (5 pts)
Q3 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.
Write the subproblems in English, Recurrence Relation and Pseudo code as well (20 Points)
a) Define (in plain English) subproblems to be solved. (2 pts)
b) Write down the base cases: (2 Points)
c) Write the recurrence relation: (6 Points)
d) Write the pseudoCode for telling if such a string can be found and if so, find the resulting
string. (8 Points)
e) Write the time complexity (2 Points)