CS140-lecture-20211101

Dynamic programming #

Dynamic programming is an algorithm design technique. In dynamic programming, you solve the problem bottom-up (as opposed to top-down in divide and conquer).

image_2021-11-01-16-06-25

Another trait of dynamic programming is that when a sub problem is solved, it is only solved once (which may not be the case in divide and conquer).

image_2021-11-01-16-07-14 image_2021-11-01-16-07-27

  • Notice that multiple sub problems are solved multipled times

image_2021-11-01-16-12-24

image_2021-11-01-16-14-21

Assembly line scheduling problem #

image_2021-11-01-16-14-30

  • \( e_n \) is the arrival time in assembly line \( n \)
  • \( a_{i,j} \) is the time it takes at station \( j \) in assembly line \( i \)
  • \( t_{i,j} \) is the transfer time
  • \( x_n \) is the exit times for assembly line \( n \)

image_2021-11-01-16-18-06 image_2021-11-01-16-18-33 image_2021-11-01-16-19-46 image_2021-11-01-16-19-55 image_2021-11-01-16-23-27

  • the idea is that \( a_{1,j} \) has the optimal subproblem solution to \( a_{1,j-1} \) and the optimal subproblem solution to \( a_{2,j-1} \) in it

image_2021-11-01-16-23-38 image_2021-11-01-16-25-42 image_2021-11-01-16-27-41 image_2021-11-01-16-30-12

So in general

\[\begin{aligned} f_1[j] &= \text{min}(f_1[j-1] + a_{1,j}, f_2[j-1] + t_{2,j-1} + a_{1, j}) \end{aligned}\]

image_2021-11-01-16-32-22 image_2021-11-01-16-33-30

We want to solve this bottom up, which means we’ll start with the base cases.

image_2021-11-01-16-36-32 image_2021-11-01-16-36-37 image_2021-11-01-16-37-12 image_2021-11-01-16-38-04 image_2021-11-01-16-38-59

Note: \( 18^{[1]} \) indicates that the total time to exit the station is 18, coming from assembly 1.

image_2021-11-01-16-40-42

  • each cell is the solution to some sub problems

image_2021-11-01-16-41-28

  • you need an array big enough to fit the solution to each sub problem

image_2021-11-01-16-46-23

  • time complexity here is \( \Theta(n) \) .

image_2021-11-01-16-49-29 image_2021-11-01-16-52-01

line 1 station 5
line 1 station 4
line 1 station 3
line 2 station 2
line 1 station 1