Old Exams Practice (topics may be different)

def test():
    """ Returns 0.
    """
    # your code here

# For example:
print(test()) # prints 0

Write the objective function for this task. That is, given a point (x, 0) in the x-axis, find the average distance from this point to each of your friends' houses.

def friend_objective_function(POINTS, x):
    """
    Returns the average distance from the point (x, 0) to each of the points in POINTS.
    """
    # your code here

# For example:
print(friend_objective_function([(10, 9)], 0))        # prints 13.4536...
print(friend_objective_function([(5, 4), (2, 3)], 2)) # prints 4 (average of 3 and 5)

Write a function that finds the point on the x-axis which minimizes the average distance to your friends' houses. It is possible that this point's x-value may not be an integer.

The grader will accept any answer that is at most 0.000001 away from the true answer.

def friend_min_distance(POINTS):
    """
    Returns a number x, such that the minimum average distance 
    from a point on the x-axis to each of the points in POINTS
    is achieved by the point (x, 0).
    """
    # your code here

# For example:
print(friend_min_distance([(10, 9)]))        # prints 10
print(friend_min_distance([(5, 4), (2, 3)])) # prints 3.285714...

def generate_selections_of_three(n):
    """
    Returns a list of all possible lists of length n,
    where each element is one of the integers 0, 1, or 2.
    """
    # your code here

# For example:
print(generate_selections_of_three(0)) # prints [[]]
print(generate_selections_of_three(1)) # prints [[0], [1], [2]]
print(generate_selections_of_three(2))
# prints [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]

You may change the function's signature by adding optional arguments (e.g. my_function(m, n, memo={})), if you want. However, make sure that the function calls still work as written below.

def my_function(m, n):
    if m < 0 or n < 0:
        return 0
    if m == 0:
        return 2
    if n == 0:
        return 3
    ans = (my_function(m-1, n) + 
        my_function(m-3, n-2) + 
        my_function(m, n-1) + 
        my_function(m, n-4) + 
        my_function(m-1, n-3)) % 10

    return ans

# For example:
print(my_function(0, 0)) # prints 2
print(my_function(4, 4)) # prints 6
print(my_function(6, 7)) # prints 8

Consider the following modified version of the knapsack problem: instead of having one of each item, individual items can be ordered more than once (for example, if these were food items from a grocery store). Assume that all items have weight at least 1.

Rewrite the code to solve this modified version.

def knapsack_memo(items, capacity, memo = None):
    """
    items: a list of Item objects, capacity > 0
    Solves the unbounded knapsack problem, where each item
    may appear more than once in the bag.
    Return a tuple of an optimal list of items and their
    total value
    """
    # your code here

# For example:
item_burger = Item("burger", 5, 3) # value 5, cost 3
item_candy = Item("candy", 1, 1)   # value 1, cost 1

print(knapsack_memo([item_burger], 10)) # returns 15
print(knapsack_memo([item_candy], 10)) # returns 10
print(knapsack_memo([item_burger, item_candy], 10)) # returns 16

# TODO check for multiple answers

Rewrite the code to solve this modified version.

def knapsack_memo(items, capacity, memo = None):
    """
    items: a list of Item objects, capacity > 0
    Solves the knapsack problem in the case where no item
    can have weight exceeding half the capacity of the bag.
    Return a tuple of an optimal list of items and their
    total value.
    """
    # your code here

# For example:
item_burger = Item("burger", 30, 6) # value 30, cost 6
item_candy  = Item("candy", 10, 3)  # value 10, cost 3
item_shake  = Item("shake", 20, 4)  # value 20, cost 4

print(knapsack_memo([item_burger], 10)) # returns 0
print(knapsack_memo([item_burger, item_candy, item_shake], 10)) # returns 30
print(knapsack_memo([item_burger, item_candy, item_shake], 12)) # returns 50

Estimate the probability of you winning this game. You are guaranteed that m and n are between 1 and 10.

def prob_of_winning(m, n):
    """ Returns the probability
    """
    # your code here

# For example:
print(test()) # prints 0

def dfs_graph_search(graph, source, target, verbose=False):
    def dfs_internal(path, shortest):
        if verbose:
            print('Current DFS path:', path_to_string(path))

        last_node = path[-1]
        if last_node == target:
            if verbose:
                print('Path found')
            return path

        if shortest and len(path) + 1 >= len(shortest):
            return None

        best_path = None
        for next_node in graph.children_of(last_node):
            if next_node in path:
                continue
            new_path = dfs_internal(path + [next_node], shortest)
            if new_path:
                if not best_path or len(new_path) < len(best_path):
                    best_path = new_path
                if not shortest or len(new_path) < len(shortest):
                    shortest = new_path
        return best_path

    return dfs_internal([source], None)

def split_data(x_vals, y_vals, frac_training=0.7):
    training_size = int(len(x_vals)*frac_training)
    training_indices = random.sample(range(len(x_vals)), training_size)
    training_x, training_y, test_x, test_y = [], [], [], []
    for i in range(len(x_vals)):
        if i in training_indices:
            training_x.append(x_vals[i])
            training_y.append(y_vals[i])
        else:
            test_x.append(x_vals[i])
            test_y.append(y_vals[i])
    return (training_x, training_y), (test_x, test_y)

def r_squared(observed, predicted):
    error = ((predicted - observed)**2).sum()
    mean_error = error / len(observed)
    return 1 - mean_error / np.var(observed)

import numpy as np
import random

def find_best_fit(x, y, min_deg, max_deg):
    """ - x and y are numpy arrays of floats
        - x elements are in ascending order
        - min_deg and max_deg are ints > 0 with min_deg <= max_deg

    The values in y are known to be generated from the values in
    x by some process that can be modeled by a polynomial function
    plus noise of some degree between min_deg and max_deg, inclusive.

    Return the degree of the polynomial that best models the  
    polynomial function without overfitting. """
    # your code here

# For example:
x = [1,2,3,4,5,6,7,8,9,10]
y = [1,4.2,7.9,15.3,27.5,38,51.2,63.1,88,98.9]
print(find_best_fit(x, y, 1, 4))    # prints 2

def highest_window_correlation(A, B, w):
    """ - A and B are lists of numbers
        - w is an int <= min(len(A), len(B))

    Returns the highest correlation between two contiguous 
    windows of length w. We compare correlations by their
    numerical value. One window is over A and the other 
    over B. Round the highest correlation found to 3 digits.
    """
    # your code here


# For example:
A = [1, 2, 3, 4, 5, 6]
B = [3, 4, 2, 5, 7, 8]
print(highest_window_correlation(A, B, 3))  # prints 0.982

A = [1, 2, 3, 4, 5]
B = [2, 4, 6, 8, 10]
print(highest_window_correlation(A, B, 2))  # prints 1.0