This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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: |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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: |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
OlderNewer