Talk:PyClass: Difference between revisions
(Nick's Python Lesson) |
m (github.com/noisebridge/PythonClass) |
||
Line 1: | Line 1: | ||
Notes on Nick's talk on graphs | Notes on Nick's talk on graphs | ||
[https://github.com/noisebridge/PythonClass Noisebridge PythonClass GitHub] | |||
https://try.jupyter.org/ was used as the primary way to test/write the code | |||
*Introduction to memo'izing with [https://en.wikipedia.org/wiki/Fibonacci_number Fibonacci Numbers] | *Introduction to memo'izing with [https://en.wikipedia.org/wiki/Fibonacci_number Fibonacci Numbers] | ||
Line 55: | Line 59: | ||
== | == 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. | 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. | ||
<pre> | <pre> | ||
# | #knapsack problem | ||
</pre> | </pre> | ||
Line 69: | Line 73: | ||
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. | 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 | |||
#Inorder, preorder, Postorder traversal | |||
#Depth-first and Breadth-first search | |||
#Check if a BST is balanced | |||
#Validate tree is a BST (must adhere to BST properties) | |||
#Find comman ancestor between to nodes | |||
<pre> | |||
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) | |||
</pre> | |||
[[User:Ⅹ|Ⅹ]] ([[User talk:Ⅹ|talk]]) 04:27, 9 January 2018 (UTC) | [[User:Ⅹ|Ⅹ]] ([[User talk:Ⅹ|talk]]) 04:27, 9 January 2018 (UTC) |
Latest revision as of 21:46, 8 January 2018
Notes on Nick's talk on graphs
Noisebridge PythonClass GitHub
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[edit]
...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[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.
#tripples class triple_steps(): def __init__(self): self.memo = {} def triple_step(self, step): if step < 0: return 0 ...
knapsack[edit]
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]
https://en.wikipedia.org/wiki/Binary_tree
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
- Inorder, preorder, Postorder traversal
- Depth-first and Breadth-first search
- Check if a BST is balanced
- Validate tree is a BST (must adhere to BST properties)
- 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)