If you find a good move, look for a better one.
-- Emanuel Lasker
🎯 Objectives:
- Iteration
- Recursion
- Brute Force
- Backtracking
- Heuristics
- Divide and conquer
- Dynamic Programming
- Branch and Bound
Fish Reunion
You're given a list of saltwater fish and a list of freshwater fish, both in alphabetical order.
How do you create a list featuring all the fish in alphabetical order?
function merge (list1, list2)
result <- List.new
while not (list1.empty and list2.empty)
if list1.top_item < list2.top_item
item <- list1.remove_top_item
else
item <- list2.remove_top_item
result.append(item)
return resultGenerating power sets = generating truth tables
Exploring Scents
Floral fragances are made combining scents from flowers. Give a set of flowers
F, how do you list all fragances that can be made?
function power_set (flowers)
fragances <- Set.new
fragances.add(Set.new)
for each (flower in flowers)
new_fragances <- copy(fragances)
for each (france in new_fragances)
fragances.add(flower)
fragances <- fragances + new_fragances
return fragancesCode: power-set.js
is a function that calls itself
has a base case
spawn numerous clones of itself, introducing computational overhead
can be visualized with recursion trees
How do you code a function that returns the
nthFibonacci number?
function fib (n)
if n <= 2
return 1
return fib(n - 1) + fib(n - 2)Code: fibonacci.js
function palindrome (word)
if (word.length <= 1)
return true
if (word.first_char != word.last_char)
return false
w = word.remove_first_and_last_chars
return palindrome(w)Code: palindrome.js
function recursive_power_set (items)
ps <- copy(items)
for each (e in items)
ps <- ps.remove(e)
ps <- ps + recursive_power_set(ps)
ps <- ps.add(e)
return psCode: power-set-recursive.js
solves problems by inspecting all of the problem's possible solution candidates aka exhaustive search
You have the daily prices of gold for a interval of time. You want to find two days in this interval such that if you had bought then sold gold at those dates, you'd have made the maximum possible profit.
function best_trade (gold_prices)
buyingDate
sellingDate
maxProfit
for each (buyingPrice in gold_prices)
for each (sellingPrice in gold_prices)
profit <- sellingPrice - buyingPrice
if profit > maxProfit
maxProfit <- profit
buyingDate <- indexOf(buyingPrice)
sellingDate <- indexOf(sellingPrice)
return maxProfitCode: best-trade.js
You have a knapsack to carry products for selling. It holds up to a certain weight, not enough for carrying all your products - you must choose which ones to carry. Knowing the weight and sales value of each product, which choice of products gives the highest revenue?
function knapsack (items, max_weight)
best_value <- 0
for each (candidate in power_set(items))
if (total_weight(candidate) <= max_weight)
if sales_value(candidate) > best_value
best_value <- sales_value(candidate)
best_candidate <- candidate
return best_candidateCode: knapsack.js
works best in problems where the solution is a sequence of choices and making a choice restraings subsequent choices.
"Fail early, fail often."
How do you place eight queens on the board such that no queens attack each other?
function queens (board)
if board.has_8_queens
return board
for each (position in board.unattacked_positions)
board.place_queen(position)
solution <- queens(board)
if (solution)
return solution
board.remove_queen(position) # backtracking
return falseA greedy algorithm tries to make the best choice at each step and never coming back. It's the opposite of backtracking.
Evil Knapsack
A greedy burglar breaks into your home to steal the products you wanted to sell. He decides to use your knapsack to carry the stolen items. Which items will he steal? Remember, the less time he spends in your home, the less likely he is to get caught.
function greedy_knapsack (items, max_weight)
bag_weight <- 0
bag_items <- List.new
for each (item in sort_by_value(items))
if max_weight <= bag_weight + item.weight
bag_weight <- bag_weight + item.weight
bag_items.append(items)
return bag_items;Code: greedy-knapsack.js
Problems with optimal substructure can be divided into similar but smaller subproblems.
NOTE:
$x=\log_{2}n \to 2^x = n$
function merge_sort(list)
if list.length = 1
return list
left <- list.first_half
right <- list.last_half
return merge(merge_sort(left), merge_sort(right));Code: merge-sort.js
You have the daily prices of gold for a interval of time. You want to find two days in this interval such that if you had bought then sold gold at those dates, you'd have made the maximum possible profit.
function trade (prices)
if prices.length = 1
return 0
former <- prices.first_half
latter <- prices.last_half
case3 <- max(latter) - min(former)
return max(trade(latter), trade(former), case3)You have a knapsack to carry products for selling. It holds up to a certain weight, not enough for carrying all your products - you must choose which ones to carry. Knowing the weight and sales value of each product, what would be the highest possible revenue?
$w_i$ is the$i^{th}$ item's weight$v_i$ is the$i^{th}$ item's value
Code: knapsack-dnc.js
is identifying repeated subproblems in order to compute them only once.
is a technique to store and reuse partial calculations to repeated subproblems
How do you code a function that returns the
nthFibonacci number?
M <- [1 -> 1; 2 -> 2]
function dfib (n)
if n not in M
M[n] <- dfib(n - 1) + dfib(n - 2)
return M[n]Code: dynamic-fibonacci.js
You have a knapsack to carry products for selling. It holds up to a certain weight, not enough for carrying all your products - you must choose which ones to carry. Knowing the weight and sales value of each product, what would be the highest possible revenue?
Code: knapsack-dp.js
Calculate base cases first, and assemble them over and over again until we get the general solution
You have the daily prices of gold for a interval of time. You want to find two days in this interval such that if you had bought then sold gold at those dates, you'd have made the maximum possible profit.
function best_trade_dp (P)
B[1] <- 1
sell_day <- 1
best_profit <- 0
for each (n from 2 to P.length)
if P[n] < P[B[n - 1]]
B[n] <- n
else
B[n] <- B[n - 1]
profit <- P[n] - P[B[n]]
if profit > best_profit
sell_day <- n
best_profit <- profit
return (sell_day, B[sell_day])Code: best-trade-bottom-up.js
Many problems involve minimizing or maximizing a target value. They're called optimization problems.
When a solution is a sequence of choices, we use the strategy branch and bound
- An upper bound sets the limit on how high the value can be.
- A lower bound sets the limit on how low the value can be.
This algorithm provides the upper bound of the optimal profit, while the Greedy Knapsack algorithm provides the lower bound.
You have a knapsack to carry products for selling. It holds up to a certain weight, not enough for carrying all your products - you must choose which ones to carry. Knowing the weight and sales value of each product, what would be the highest possible revenue?
function powdered_knapsack (items, max_weight)
bag_value <- 0
bag_weight <- 0
bag_items <- List.new
items <- sort_by_value_weight_ratio(items)
for each (i in items)
weight <- min(max_weight - bag_weight, i.weight)
bag_weight <- bag_weight + weight
value <- weight * i.value_weight_ratio
bag_value <- bag_value + value
bag_items.append(item, weight)
return bag_items, bag_valueCode: powdered-knapsack.js