Problem Solving
Exercises
Problem 1
• Reverse characters of each word in a
sentence
• Convert “my career stack” to “ym reerac
kcats”.
Problem 2
• Find if a word is composed of two separate
and meaningful words.
• Newspaper => news & paper
Assembly Line Optimization
Introduction to Algorithms(Thomas
Cormen, Charles E Leiserson, Ronald
L Rivest, Clifford Stein) 15.1
Problem Statement
• Scheduling two automobile assembly lines
• Each line has n stations
• Si,j = jth station on line i | j=1,2…n & i=1,2
• S1,j == S2,j in terms of functionality
• S1,j != S2,j in terms of time spent
• ai,j = time required at station Si,j
• ei = entry time for the chasis to enter assembly line i
• xi = exit time for the chasis to leave assembly line i
The assembly line
S1,1 S1,2 S1,3 S1,n-1 S1,n
Assembly Line 1 a1,1 a1,2 a1,3 a1,n-1 a1,n
t1,1 t1,2 t1,n-1 x1
e1
Chasis
enters ****** Car
Leaves
e2
t2,1 t2,2 t2,n-1
x2
a2,1 a2,2 a2,3 a2,n-1 a2,n
Assembly Line 2
S2,1 S2,2 S2,3 S2,n-1 S2,n
Problem Statement(Contd..)
• ti,j = time to transfer a chasis from one line to
the other. Where, i=1,2 & j=1,2…n-1(after nth
station, assembly is complete)
• Minimize the total time
SOLUTIONS?
Brute Force
• Infeasible when n is very large
• Total possibilities with switching= 2n
• Ω(2n)
• Θ?
DYNAMIC PROGRAMMING
Step 1:Characterize the structure of an
optimal solution
• What is the fastest possible way for a chasis to
get from the starting point through station S1,j?
– For j=1, only one way, taking time e1
– For j=2,3…n
• Chasis could have come from Si,j-1 =>Si,j
• From S2,j-1 => transfer to S1,j in t2,j-1
Step 1:Optimal Substructure
• For fastest way through station Si,j it must pass
through station j-1 from line 1 or 2
• The fastest way through S1,j is either:
– Through S1,j-1 and then directly through station S1,j;
or
– Through S2, j-1, a transfer from line 2 to line 1 and
then through station S1,j
Step 1:Optimal Substructure
• For fastest way through station Si,j it must pass
through station j-1 from line 1 or 2
• The fastest way through S2,j is either:
– Through S2,j-1 and then directly through station S2,j;
or
– Through S1, j-1, a transfer from line 1 to line 2 and
then through station S2,j
Step 1:Optimal Substructure
• To solve fastest way through station j of either
line
• Solve the subproblems of finding the fastest
ways through station j-1 on both lines.
• Thus an optimal solution to an instance of the
assembly-line scheduling problem lies in
optimal solutions of subproblems
Step 2:A recursive solution
“Define the value of an optimal solution
recursively in terms of optimal solutions to
subproblems”
• Subproblems:
– Find the fastest way through station j on i | j=1,2,
…n & i=1,2
Step 2:A recursive solution
• Let fi[j] = fastest possible time to get a chasis
from starting point through station Si,j
• f* = fastest time to get a chasis all the way
through the factory
• f* = min(f1[n]+x1,f2[n]+x2)
– fastest way through the entire factory with n
stations
Step 2:A recursive solution
• f1[1] = e1+a1,1
• f2[1] = e2+a2,1
• time to get through station 1 on either line
Step 2:A recursive solution
• fi[j] =? where j = 2,3…n and i=1, 2
• The fastest way through S1,j is either:
– Through S1,j-1 and then directly through station S1,j;
• f1[j] = f1[j-1]+a1,j
– Through S2, j-1, a transfer from line 2 to line 1 and then
through station S1,j
• f1[j] = f2[j-1]+t2,j-1+a1,j
• Thus: f1[j] = min(f1[j-1]+a1,j , f2[j-1]+t2,j-1+a1,j)
• Symmetrically: f2[j] = min(f2[j-1]+a2,j , f1[j-1]+t1,j-1+a2,j)
Step 2:A recursive solution
e1+a1,1 if j=1
f1[j] =
min(f1[j-1]+a1,j , f2[j-1]+t2,j-1+a1,j) if j>=2
e2+a2,1 if j=1
f2[j] =
min(f2[j-1]+a2,j , f1[j-1]+t1,j-1+a2,j) if j>=2
A recursive solution
• fi[j] gives the values of optimal solutions to subproblems.
• Let li[j] be the fastest path involving line 1 or 2, whose
station j-1 is used in a fastest way through Si,j; where i=1,2
& j=2,3,…n
• li[1] is not defined because j-1 would be -1 then(No station
precedes station 1 on either line)
• l* = line, whose station n is used in a fastest way through
the entire factory
Step 3: Computing the fastest times
• Running time of this recursive algo = 2n
– Let ri(j) be the number of references made to fi[j]
in a recursive algorithm
• ri(n) = 1 where i=1 or 2
– f* = min(f1[n]+x1,f2[n]+x2)
• ri(j) = r1(j+1)+r2(j+1) where i=1 or 2 & j=1,2…n-1
because
e1+a1,1 if j=1
f1[j] =
min(f1[j-1]+a1,j , f2[j-1]+t2,j-1+a1,j) if j>=2
e2+a2,1 if j=1
f2[j] =
min(f2[j-1]+a2,j , f1[j-1]+t1,j-1+a2,j) if j>=2
Step 3: Computing the fastest times
• ri(j) = 2n-j,
– thus f1[1] alone is referenced 2n-1 times
• The total number of references to all fi[j] values is Ω(2n)
• Is there a better solution?
– For j>=2, each value of fi[j] depends only on the values of
f1[j-1] and f2[j-1].
– By computing the fi[j] values in order of increasing station
numbers j, we can compute the fastest way through the
factory and time it takes in Θ(n) time.
Thank you
FASTEST-WAY ALGORITHM