# Talk:PyClass

Notes on Nick's talk on graphs

https://try.jupyter.org/ was used as the primary way to test/write the code

• Introduction to memo'izing with Fibonacci Numbers
• Counting steps problem, with either 1, 2, or 3 steps at a time on n steps staircase
• Binary search trees
• Canonical Dynamic Programming Problems
• Shortest Path
• Parenthization
• Knapsack
• Towers of Hanoi
• Edit Distance
• Eith Queens

## fibonacci w/memo'ization

...it's a thing https://www.python-course.eu/python3_memoization.php

```class Fibber:
def __init__(self):
self.memo = {}

def fib(self, n):
if n < 0:
raise Exception("Oh Snap!")
elif n < 2:
return 2
if n in self.memo:
return self.memo[n]
result = self.fib(n-1) + self.fib(n-2)
self.memo[n] = result

return result

f = Fibber()
f.fib(10)
```

## how many steps

nick goes up n stairs, he goes up the stairs one, two or three steps at a time, how many steps do they take.

```#tripples
class triple_steps():
def __init__(self):
self.memo = {}
def triple_step(self, step):
if step < 0:
return 0
...
```

## knapsack

Given a set of tuples that represent the weight and value of different goods, cakes in our examples, find the maximum value we can get given a knapsack with a certain weight restriction. Find the point where the value is maximum and the sum of their weight is equal to the total weight allowed by the knapsack. 0/1 means you can not split an item.

```#knapsack problem
```

## binary trees

discussion about nodes, branching structure with a root/parent node, with two children. Traversal orders, in order, pre order, and post order. In order traversal is sorted array.

build a binary tree from a sorted array

1. Inorder, preorder, Postorder traversal
3. Check if a BST is balanced
4. Validate tree is a BST (must adhere to BST properties)
5. Find comman ancestor between to nodes
```class Node:
def __init__(self, value):
self.value = vlaue
self.left = None
self.right = None

#BST Binary Search Tree
def checkBST(node):
return (checkBSThelper(node, -math.inf, math.inf))

def checkBSThelper(node, mini, maxi):
if node is None:
return True
if node.v < mini or node.v >= maxi:
return False
return checkBSThelper(node.left, mini, node.v) and checkBSThelper(node.right, node.v, maxi)
```

(talk) 04:27, 9 January 2018 (UTC)