Analysis of Algorithm Chapter 7 : Dynamic Programming

Which are two key properties of the problem that could lead to the solution using dynamic programming?

• Overlapping subproblem

• Optimal substructure

• Non-overlapping subproblem

• Greedy subproblem

• Polynomial time complexity

Which are the reasons that cause the time from the recursive control structure becomes too high ?

• There are too many function calls on smaller size input

• The large table are required to store data

• Using the recursive stack for collecting function call value

• The n at base condition is relatively low compared to the input n.

What is a key point of dynamic programming?

• The storage of results in the smaller case to use for solving the bigger one.

• The recursive calls of function

• The division of the problem into sub-problems for easier solving

• Including multiple ways of solutions to solve the problem based on inputs

Which are types of dynamic programming based on storing

• Tabulation

• Dynamic memory

• Top up

• Memoization

• Static memory

From the tabulation derived from the dynamic programming approach of Longest Increasing Subsequence algorithm, what is the value of A + B

Note that if two elements have the equal LIS value, choose the one with the less value.

Based on this resulting tabulation, which elements are NOT in the longest increasing subsequence?

• 47

• 46

• 18

• 38

• 25

Given N be the number of items, C be the capacity of the knapsack, W be the list of item weights and V be the list of item values, which is the dimension of the tabulation storing the result of this 0/1 knapsack problem.

• N x (max(W)+1)

• N x (C+1)

• C x (len(W)*len(V))

• len(W) x len(V)

The item i (w[i], v[i]) can be chosen at W = X, which ones are TRUE

• X - w[i] ≥ 0

• If v[i] > dp[i - 1][X]

  then item i is chosen

• If i = 1 then dp[1][X] = v[1]

• If dp[i][X-w[i]] + v[i] < dp[i-1][X]

  then, item i is not chosen.

ข้อใดไม่ใช่กระบวนการที่ถูกต้องของการทำรูปเล่มเอกสาร หลังจากนำเสนอเสร็จแล้ว

• แปะวางเนื้อหาจากแหล่งข้อมูลให้ครบทุกหน้า

• แปะวางเนื้อหาจากสไลด์นำเสนอให้ครบทุกหน้า

• ให้ลิงค์คลิปยูทูปหรือเพจ โดยไม่ใส่วันที่ที่อ้างอิง

• เขียนเนื้อหาสรุปใหม่ และเพิ่มรูปประกอบที่อาจไม่อยู่ในสไลด์

• เขียนเนื้อหาเป็นย่อหน้าตามความเข้าใจแบบย่อ