Strategies

Question 1

Divide and conquer

Answer 1

1. Figure out a simple case as the base case
2. Figure out how to reduce the problem and get to the base case

Question 2

Greedy algorithms

Answer 2

• At each step pick the locally optimal solution. Pick the optimal move.
• They are used as approximation algorithms where the exact solution would take too much time (with a big set of items)
• NP-complete problems are solved by using approximation algorithms because they are very hard to solve with an exact solution

Question 3

Dynamic programming 1

Answer 3

• It’s useful when you’re trying to optimize something given a constraint
• Starts by solving subproblems and builds up to solving the big problem
• Every dynamic programming algorithm starts with a grid, that is built progressively. And the solution always will be the largest value, which could be in any row and column of the grid.
• Usually, the values in the cells are what you’re going to optimize

Question 4

Dynamic programming 2

Answer 4

• It only works when each subproblem is discrete. That means when they don’t depend on other subproblems
• Formula for some cases: Max ( 1. Previous max (cell[i-1][j]) vs 2. Value of current item + Value of the remaining space/weight,etc (cell[i-1][j-item’s space/weight/etc]) )