macroxela

###################################################################
#Box Stacking
#Given n boxes (L, W, H), find the height of the tallest
#possible stack. Box (Li, Wi, Hi) can be on top of box (Lj, Wj, Hj)
#if Li < Lj and Wi < Wj
#
#Based on video from Reducible
#Box Stacking: https://www.youtube.com/watch?v=aPQY__2H3tE
###################################################################

macroxela

###################################################################
#Partition Count
#Write a function that counts the number of ways you can
#partition n objects using parts up to m assuming m >= 0
#
#
#Based on videos from Reducible
#Partition Count: https://www.youtube.com/watch?v=ngCos392W4w
###################################################################

macroxela

#################################################################################################################
#   Sorting Algorithms
#   Various sorting algorithms including
#   • Merge Sort        O(nlogn)
#   • Counting Sort     O(n+k) with k being value of largest element
#   • Radix Sort        O(d*[n+k])  with d being number of digits
#
#
#################################################################################################################
def merge(seq1, seq2):

macroxela

############################################################################################
#   Max Sum Rectangle (2D Kadane Algorithm)
#   Finds the submatrix with the largest sum of its values using Kadane's algorithm
#   
#   
#   
############################################################################################
def Kadane(arr):
    #Keep track of sums
    current_sum = arr[0]

macroxela

###############################################################################
#   Subset Sum Problem
#   Find all subsets s of S that sum to value V
#
#                                   include value   exclude value
#   Recursive Equation: SS(S, V) = SS(S-1, V - s_v) + SS(S-1, V)
#
###############################################################################

#Retrieves actual subsets in solution. Based on (https://stackoverflow.com/questions/42417352/subset-sum-recover-solution)

macroxela

######################################################################################################################
#   Edit Distance
#   Find the minimum number of operations (replace, delete, insert) to convert string a to string b. Uses a bottom up
#   dynamic programming approach. Based on example from YouTube channel 'Back to Back SWE': https://www.youtube.com/watch?v=MiqoA-yF-0M
#
#                                         replace       delete      insert
#   Recursive Equation: ED(a, b) = min( ED(a-1, b-1), ED(a-1, b), ED(a, b-1) ) where a-1 means removing 1 character from string a
#
######################################################################################################################

macroxela

########################################################################
# Rotates N x N matrix by 90, 180, or 270 degrees without using any
# extra space.
########################################################################


#Swap elements from two sets of indicies in matrix
def swapMat(matrix, i1, j1, i2, j2):
    temp = matrix[i1][j1]
    matrix[i1][j1] = matrix[i2][j2]

macroxela

###################################################################################
#0-1 Knapsack Problem
# • Find which gems maximize profit given list of values, weights, and weight limit
#
###################################################################################

#Finds the max profit possible with given gems & weight limit
def knapsack(v, w, limit):
    matrix = [[0 for i in range(0, limit+1)] for j in range(0, len(v)+1)]
    

macroxela

################################################################
# Given integers a with digits a1 a2 ... am and b with digits
#b1 b2 ... bn find the largest permuation of b's digits so 
# b < a
################################################################

from itertools import permutations
import math

################################################################

macroxela

############################################################################
#Find how many ways you can make change with coins c = [c1, c2, ..., cm]
#for change N. Similar to the Subset Sum problem
#
############################################################################

#Dynamic Programming Solution
def cchange(Cents, coins):
    #Initialize matrix to store values
    matrix = [[0 for i in range(0, cents+1)] for j in range(0, len(coins)+1)]