## Week 11 & 12 Update

On weeks 11 and 12 worked on:
- 📊 [Formulating prover criteria for the optimization model](https://docs.google.com/presentation/d/1oEi9rlmAGij89XoQVJBtVmpmSGCfR-73/edit?usp=sharing&ouid=100030655387880205054&rtpof=true&sd=true)
- [Full version](https://docs.google.com/document/d/1UBD-ZL5VG5D-TrOQj1O_CyhwMFYBztbmgwjVpwdxBVM/edit#heading=h.hhqec7y0zue8)
- 📝 [Taking notes on the prover mechanism research](https://hackmd.io/@nilu/provernotes)

Had a very productive discussion with Norbert. We decided to start designing the simulation model alongside formulating metrics. Preparing for agent-based simulation with cadCAD:
- Here's a great link for getting started: [cadCAD Onboarding](https://www.notion.so/cadcad/cadCAD-Onboarding-TL-DR-e0da826e676344ee94d71d39d65d4fc2)
- Enrolled in [cadCAD bootcamp](https://www.cadcad.education/start) to learn to use the simulation tool effectively 📚👩‍🎓

#
### Notes on Optimization

[1. Introduction, Optimization Problems (MIT 6.0002 Intro to Computational Thinking and Data Science)](https://www.youtube.com/watch?v=C1lhuz6pZC0&t=456s)
- An objective function that is to be maximized or minimized
- Minimize time spent traveling from New York to Boston
- A set of constraints (possibly empty) that must be honored
- Cannot spend more than $100
- Must be in Boston before 5:00PM

**0/1 Knapsack Problem**
You have limited strength, so there is a max weight you can carry

- "Each item is represented by a pair, <value, weight>
- The knapsack can accommodate items with a total weight of no more than w
- A vector, L, of length n, represents the set of available items. Each element of the vector is an item
- A vector, V, of length n, is used to indicate whether or not items are taken. If V[i] = 1, item /[i] is taken. If V[i] = 0, item I[i] is not taken

Find a V that maximizes the value

n-1
ΣV[i]* I[i].value
i=0

subject to the constraint that the total weight is less than or equal to w

n-1
ΣV[i]* [[i].weight ≤ w
i=0

**Brute Force Algorithm** enumerates all possible combinations of the items and remove the combinations whose weight exceeds the allowed weight. It's not very efficient due to the 0/1 knapsack problem being exponential!

**Greedy Algorithm** puts the "best" available item in the knapsack first

What defines the best?
- Most valuable
- Least expensive
- Highest value/units

def testGreedys(foods, maxUnits):
    print('Use greedy by value to allocate', maxUnits,
          'calories')
    testGreedy(foods, maxUnits, Food.getValue)
    print('\nUse greedy by cost to allocate', maxUnits,
          'calories')
    testGreedy(foods, maxUnits,
               lambda x: 1/Food.getCost(x))
    print('\nUse greedy by density to allocate', maxUnits,
          'calories')
    testGreedy(foods, maxUnits, Food.density)


names = ['wine', 'beer', 'pizza', 'burger', 'fries',
         'cola', 'apple', 'donut', 'cake']
values = [89,90,95,100,90,79,50,10]
calories = [123,154,258,354,365,150,95,195]
foods = buildMenu(names, values, calories)
testGreedys(foods, 1000)

The problem of the algorithm is it can get stuck on a local optimum (local maximum) rather than the globally optimal solution (global maximum)!

[2. Optimization Problems](https://www.youtube.com/watch?v=uK5yvoXnkSk&t=112s)

**Search Tree Implementation** builts top down from the root as items are selected. As another item is added to the bag, a node gets created as a left branch (as long as the constraint are meet). On the other hand a right branch is formed reflecting the consequence of not including the added item. The process is then **recursively** applied to non-leaf children At the end a node with the highest value is choosen.

The downside is **it gets too long to compute a solution** with big data sets. The same as brute force, an inherently exponential problem!

**Dynamic Programming**
- **Memoization**
If we consider Fibonnaci's recursive implementation, it would repeat the same calculation, which would take a long time. Thus, it is more efficient to create a dictionary of the computations performed and check if the computation has the answer. The system looks it up and returns the value, otherwise will compute it.

def fastFib(n, memo = {}):
    """Assumes n is an int >= 0, memo used only by recursive calls
       Returns Fibonacci of n"""
    if n == 0 or n == 1:
        return 1
    try:
        return memo[n]
    except KeyError:
        result = fastFib(n-1, memo) + fastFib(n-2, memo)
        memo[n] = result
        return result

for i in range(121):
print('fib(' + str(i) + ') =', fastFib(i))

When does it work?
- **Optimal substructure:** a globally optimal solution can
be found by combining optimal solutions to local
subproblems
- For x > 1, fib(x) = fib(x - 1) + fib(x – 2)

- **Overlapping subproblems:** finding an optimal solution
involves solving the same problem multiple times
- Compute fib(x) or many times

Summary
- Many problems of practical importance can be formulated as optimization problems.
- Greedy algorithms often provide adequate (though not necessarily optimal) solutions.
- Finding an optimal solution is usually exponentially hard.
- But dynamic programming often yields good performance for a subclass of optimization problems— those with optimal substructure and overlapping subproblems:
- Solution always correct
- Fast under the right circumstances
#
### Exciting Resources
- [Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming by Tim Roughgarden](https://www.coursera.org/learn/algorithms-greedy)
- [Tim Roughgarden's Online Courses](http://www.timroughgarden.org/videos.html)
- [Advanced Mechanism Design (Stanford CS364B, Winter 2014)](https://www.youtube.com/playlist?list=PLEGCF-WLh2RI77PL4gwLld_OU9Zh3TCX9)