Week 3

Question 1

4 jenis traversal?

Answer 1

– Pre-order Traversal
• parent–left–right

– Level-order Traversal
• parent–left–right(eachlevel)

– In-order Traversal
• left–parent–right

– Post-order Traversal
• left–right–parent

Question 2

A problem has 4 solutions:

Answer 2

1. Universal Solution (right and wrong)
2. Feasible Solution
   all possible correct solutions, but different levels of truth
3. Objective function (better)
4. Optimal Solution
   the most correct (best) solution

Question 3

Popular techniques in problem solving?

Answer 3

1. greedy method
2. dynamic programming
3. data compression
4. backtracking
5. branch and bound

Question 4

Variation of Knapsack problem?

Answer 4

1. fractional knapsack problem
   - items should be brought in part (in fractional units)
   - tergantung pada kuantitas ketersediaan barang
   - can be solved by greedy method
   - OPTIMAL
2. 0/1 knapsack problem
   - each item is only 1 or 0
   - can NOT be solved by greedy method
3. bounded knapsack problem
   - each item is available in N units
4. unbounded knapsack problem
   - each item is available in more than one unit, the number is unlimited.
   - can be solved by greedy method

Question 5

2 knapsack problem yang sering muncul?

Answer 5

1. unbounded knapsack problem (item dengan berat fix, tidak dapat dipecah)
2. fractional knapsack problem (item dengan berat dapat dipecah)