DiegoGallegos4

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

class List:
    def __init__(self, head=None):
        self.head = head
        self.tail = None
    

DiegoGallegos4

def partition(A, left, right):
    pivot, j = A[left], left
    for i in range(left + 1, right + 1):
        if A[i] <= pivot:
            j += 1
            A[i], A[j] = A[j], A[i]
    A[left], A[j] = A[j], A[left]
    return j

DiegoGallegos4

def merge(A, B):
    C = []
    while len(A) and len(B):
        a, b = A[0], B[0]
        if a <= b:
            C.append(A.pop(0))
        else:
            C.append(B.pop(0))
    while len(A):
        C.append(A.pop(0))

DiegoGallegos4

def selection_sort(A):
    for i in range(len(A)):
        min_index = i
        for j in range(i+1, len(A)):
            if A[j] < A[min_index]:
                min_index = j
        A[i], A[min_index] = A[min_index], A[i]
    return A

DiegoGallegos4

def karatsuba(A, B, n):
    """
    A(x) = a_1 * x + a_0
    B(x) = b_1 * x + b_0
    
    C(x) = a_1 * b_1 * x^2 + (a_1 * b_0 + a_0 * b_1) * x + a_0 * b_0
    
    Rewrite as 
    
    C(x) = a_1 * b_1 * x^2 + ((a_1 + a_0) * (b_0 + b_1) - a_1 * b_1 - a_0 * b_0) * x + a_0 * b_0

DiegoGallegos4

import math

import numpy as np


def dc_poly_mult(A, B, n, a, b):
    """
    A(x) = D1(x) * x^n/2 + D0(x)
    where
    D1(x) = a_n-1 * x^(n/2-1) + a_n-2 * x^(n/2-2) + ... + a_(n/2)

DiegoGallegos4

def naive_poly_mul(A, B, n):
    """
    Multiplies two n -1 polynomials A and B

    Args:
    A(x) = a_n-1 * x^n-1 + a_n-2 + ... + a_1*x + a_0
    B(x) = b_n-1 * x^n-1 + b_n-2 + ... + b_1*x + b_0

    Returns:
    C(x) = c_2n-2 * x^2n-2 + c_2n-3 * x^2n-3 + ... + c_1 * x + c_0

DiegoGallegos4

def find_max_coin(money, coins):
    max_coin = float('-inf')
    for coin in coins:
        if money - coin >= 0 and coin > max_coin:
            max_coin = coin
    return max_coin

def change_greedy(money, coins):
    """
    Running time: 

DiegoGallegos4

def binary_search(A, low, high, k):
    """
    Search in a sorted array
    Args:
    A sorted array A[low...high]
    (∀low <= i < high: A[i] <= A[i+1]) monotonically decreasing

    Returns:
    An index, i, (low <= i <= high) where A[i] = k
    Otherwise the greatest index such that A[i] < k

DiegoGallegos4

def linear_search(A, low, high, key):
    if high < low:
        return 'NOT_FOUND'
    if A[low] == key:
        return low
    return linear_search(A, low + 1, high, key)