270ajay

'''Course: https://www.coursera.org/learn/algorithmic-toolbox#about'''


def knapsackWithRepetitions(maxCapacity, weightsList, valuesList):
    '''returns optimal solution. Maximize total value of items that can fit.
    Knapsack can contain more than 1 quantity of each item'''

    knapsackValList = [None] * (maxCapacity+1)
    knapsackValList[0] = 0

270ajay

'''Course: https://www.coursera.org/learn/data-structures#about'''


class Node:

    def __init__(self, key, next=None):
        self.key = key
        self.next = next

270ajay

'''Course: https://www.coursera.org/learn/data-structures#about'''


class DynamicArray:
    '''How python list works. No restriction on size'''

    def __init__(self):
        self.array = [None] * 2
        self.size = 0
        self.capacity = 2

270ajay

'''Course: https://www.coursera.org/learn/data-structures#about'''


class BinaryHeap:
    '''Priority Queue. Insert values to this data structure and get max value stored quickly'''

    defaultArraySize = 10

    def __init__(self, size=None):
        self.maxSize = size if size != None else BinaryHeap.defaultArraySize

270ajay

import random

'''Course: https://www.coursera.org/learn/data-structures#about'''


def isPrime(num):
    '''src: https://codereview.stackexchange.com/questions/71212/find-smallest-prime-number-greater-than-given-n'''

    if num%2 == 0 or num%3 == 0:
        return False

270ajay

'''Course: https://www.coursera.org/learn/data-structures#about'''

class Node:

    def __init__(self, key, parent=None, leftChild=None, rightChild=None):

        self.key = key
        self.parent = parent
        self.leftChild = leftChild
        self.rightChild = rightChild

270ajay

'''course: https://www.coursera.org/learn/algorithms-on-graphs#about'''

def adjacencyMatrix():
    '''Edges: (A,B), (A,C), (A,D), (C,D), (E,F)
       check if edge exists: O(1)
       list all edges: O(numOfNodes^2)
       list all neighbors: O(numOfNodes)'''

    adjMatrix = {'A': {'A': 0, 'B': 1, 'C': 1, 'D': 1, 'E': 0, 'F': 0},
                 'B': {'A': 1, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0},

270ajay

'''course: https://www.coursera.org/learn/algorithms-on-graphs#about'''


class Node:
    def __init__(self, key, next=None):
        self.key = key
        self.next = next


class SinglyLinkedList:

270ajay

import heapq

'''course: https://www.coursera.org/learn/algorithms-on-graphs#about'''


class PriorityQueue():

    '''credits: Eugene Yarmash
     https://stackoverflow.com/questions/46636656/python-heapq-replace-priority'''

270ajay

import heapq

'''course: https://www.coursera.org/learn/algorithms-on-graphs#about'''

class DisjointSets:
    '''Finds quickly if two points belong to same set'''

    def __init__(self, totalNumOfSets):
        self.parent = [None] * totalNumOfSets
        self.rank = [None] * totalNumOfSets