Dynamic Programming and Graph Algorithm Problems

Here are what we went over in the class. In addition here are the links to the MIT Course I mentioned and to my repo that has a lot more implementations of different types of algorithms and strategies.

Dynamic Programming

Dynamic programming is about approaching problems with overlapping substructures. We are taking a careful brute force method where exponential search space is reduced to polynomial search space.

Canonical Example: Fibonacci Sequence


In [9]:
def fib(n):
    
    if n < 0:
        raise Exception("Index was negative. Cannot have a negative index in a series")
        
    if n < 2:
        return n
    
    return fib(n-1) + fib(n-2) 

fib(25)


Out[9]:
75025

In [4]:
def fib(n):
    
    if n < 0:
        raise Exception("Index was negative. Cannot have a negative index in a series")
        
    if n < 2:
        return n
    
    pred_pred, pred = 0, 1
    
    for _ in range(n-1):
        current = pred + pred_pred
        pred_pred = pred
        pred = current
    
    return current

fib(25)


Out[4]:
75025

In [8]:
class Fibber:
    def __init__(self):
        self.memo = {}
    
    def fib(self, n):
        if n < 0:
            raise Exception('Index was negative. No such thing as a negative index in a series')
        
        elif n < 2:
            return n;
        
        if n in self.memo:
            return self.memo[n]
        
        result = self.fib(n-1) + self.fib(n-2)
        
        self.memo[n] = result
        
        return result

fibs = Fibber()
fibs.fib(25)


Out[8]:
75025

There are two approaches to dynamic programming problems.

  1. Guessing + recursion + memoization. Pick out a feature of the problem space that we don't know and brute force an answer. Then we recurse over the problem space until we reach the part that is relevant for our specific instance. Then we memoize. Memoization takes what is often exponential time and makes linear/polynomial.

  2. The second is a bottom-up approach. We build a dynamic programming table until we can solve the original problem.

Problems to try:

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are 'off limits' such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.


In [10]:
# Triple Step

class triple_step():
    def __init__(self):
        self.memo = {}
        
    def triple_step(self, step):
        if step < 0:
            return 0
        
        self.memo[0] = 1
        if step == 0:
            return self.memo[0]
        
        self.memo[1] = 1
        if step == 1:
            return self.memo[1]
        
        result = self.triple_step(step-1) + self.triple_step(step-2) + self.triple_step(step-3)
        self.memo[step] = result
        
        return result
    
t = triple_step()
t.triple_step(4)


Out[10]:
7

0/1 Knapsack Problem

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 cannot split an item.


In [12]:
# a cake tuple (3, 90) weighs 3 kilograms and has a value
# of 90 pounds
cake_tuples = [(7, 160), (3, 90), (2, 15)]
capacity = 20

def max_duffel_bag_value(cake_tuples, weight_capacity):
    
    # we make a list to hold the max possible value at every
    # duffel bag weight capacity from 0 to weight_capacity
    # starting each index with value 0
    
    #initialize an array of zeroes for each capacity limit
    max_values_at_capacities = [0]*(weight_capacity + 1)
    
    for current_capacity in range(weight_capacity + 1):
    
        current_max_value = 0
        
        #iterate through our range of weights from 0 to capacity
        for cake_weight, cake_value in cake_tuples:
        
            
            if cake_weight <= current_capacity:
                #check the cake would fit at all
                
                #take the value from the current capacity - the cake weight and add to the value of this cake
                max_value_using_cake = cake_value + max_values_at_capacities[current_capacity - cake_weight]
                
                #do this for each cake, take the one that gives us the highest value 
                current_max_value = max(max_value_using_cake, current_max_value)
         
        #set that max value to the current capacity 
        max_values_at_capacities[current_capacity] = current_max_value
    
    
    return max_values_at_capacities[weight_capacity]

max_duffel_bag_value(cake_tuples, capacity)


Out[12]:
555

In [ ]:
def getPath(self, maze):
    if len(maze) == 0 or len(maze[0]) == 0:
        return None
    path = []
    failedPoints = set()
    if self.pathFinder(maze, len(maze), len(maze[0]), path, failedPoints):
        return path
    return None

def pathFinder(self, maze, row, col, path, failedPoints):
    if col < 0 or row < 0 or not maze[row][col]:
        return False
    p = (row, col)
    if p in failedPoints:
        return False
    isAtOrigin = (row == 0) and (col == 0)
    if isAtOrigin or self.pathFinder(maze, row, col-1, path, failedPoints) or self.pathFinder(maze, row-1, col, path, failedPoints):
        path.append(p)
        return True
    failedPoints.append(p)
    return False

Common dynamic programming problems:

  1. Fibonacci
  2. Shortest Path
  3. Parenthesization
  4. Shortest Path
  5. Knapsack
  6. Towers of Hanoi
  7. Edit Distance
  8. Eight Queens/ N Queens
  9. Coin change
  10. Longest Common Subsequence

Graph and Trees

Differences between graphs and trees

Trees has a direct child/parent relationship and don't contain cycles. Trees are a DAG (directed acyclic graph) with the restriction that each child has one parent.

Binary Trees

Binary Trees are a great restricted case of a graph problem that are a great way to get familiar with traversing and interacting with graph structures before jumping to something more abstract.

A binary tree is only a binary tree if an inorder traversal is a sorted list of values.

Full - Every node should have exactly 2 nodes except the leaves. The leaves have 0 children

Complete - Every level, except the last, is completely filled, and all nodes are as far left as possible. A binary tree can be complete with nodes which have a single child if it is the leftmost child.

Balanced - The left and right sides of the tree have a height difference of 1 or less.

Here are some tasks you should know how to do with binary search trees:

  1. Build a binary tree from a sorted array
  2. Inorder, Preorder, Postorder traversal
  3. Depth-first and Breadth-first search
  4. Check if a BST is balanced
  5. Validate tree is a BST (must adhere to BST properties)
  6. Find common ancestor between two nodes

In [ ]:
class Node:
    def __init__(self, value):
        self.v = value
        self.right = None
        self.left= None

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)

In [ ]:
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def checkBalanced(root):
    if root is None:
        return 0
    
    left = checkBalanced(root.left)
    right = checkBalanced(root.right) 
    
    if abs(left - right) > 1:
        return -1
    
    return max(left, right) + 1

Graph Structures

There are many graph structures that are useful.

  1. Tries- Tries are great for indexing words, alphabets, anything where you are trying to keep track of words tries are useful. The key to tries are that the letters lie along the edges of the graph and the vertices represent the word up to that point. Make sure that at the end of a word you have a special character to denote that you have reached the end of the word even if there are edges that continue towards another word.

  2. DAG - Directed Acyclic Graphs: DAG are really good structures for represented relationships between items.


In [ ]:
class Trie:
    
    def __init__(self):
        self.root_node = {}
        
    def check_present_and_add(self, word):
        
        current_node = self.root_node
        is_new_word = False
        
        for char in word:
            if char not in current_node:
                is_new_word = True
                current_node[char] = {}
            current_node = current_node[char]
            
        if "End of Word" not in current_node:
            is_new_word = True
            current_node["End Of Word"] = {}
        
        return is_new_word

In [ ]:
#[2::][1::2]
import collections

words = ["baa", "", "abcd", "abca", "cab", "cad"]

def alienOrder(words):
    pre, suc = collections.defaultdict(set), collections.defaultdict(set)
    for pair in zip(words, words[1:]):
        print(pair)
        for a, b in zip(*pair):
            if a != b:
                suc[a].add(b)
                pre[b].add(a)
                break
    print('succ %s' % suc)
    print('pred %s' % pre)
    chars = set(''.join(words))
    print('chars %s' % chars)
    print(set(pre))
    free = chars - set(pre)
    print('free %s' % free)
    order = ''
    while free:
        a = free.pop()
        order += a
        for b in suc[a]:
            pre[b].discard(a)
            if not pre[b]:
                free.add(b)
    
    if set(order) == chars:
        return order 
    else:
        False
#     return order * (set(order) == chars)
    
alienOrder(words)