DiegoGallegos4

def min_refills(stations, full_tank_limit):
    """
    Find min refills for gas tank in a trip between point A and B

    Args:
    stations (array): possible gas stations to refill including start(A) and end(B).
    full_tank_limit (int): gas tank maximum limit.

    Returns:
    (int) number of refills needed to make the trip between A -> B

DiegoGallegos4

items = [(20, 4), (18, 3), (14, 2)]
W = 7

def fractional_knapsack_naive(items, bag_weight):
    """
    Maximize the value of items that fit into knapsack
    constrained to bag_weight

    Args:
    items: list of tuples containing (value_i, weight_i) pairs

DiegoGallegos4

def linear_search(A, k):
    """
    Args: 
    A array: array with n elements
    
    Returns
    index i where A[i] = k, if there is not such i, then NOT_FOUND
    """
    for (index, item) in enumerate(A):
        if item == 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)

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 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 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

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 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

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