From Noisebridge
Jump to: navigation, search

Notes on Nick's talk on graphs

Noisebridge PythonClass GitHub 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[edit]'s a thing

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()

how many steps[edit]

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

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


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[edit]

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
  2. Depth-first and Breadth-first search
  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)