Extra Homework 2

extra02.zip

Due by 11:59pm on Tuesday, November 2

Instructions

Download extra02.zip. Inside the archive, you will find a file called , along with a copy of the Ok autograder.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored.

Using Ok

The ok program helps you test your code and track your progress. The first time you run the autograder, you will be asked to log in with your @berkeley.edu account using your web browser. Please do so. Each time you run ok, it will back up your work and progress on our servers. You can run all the doctests with the following command:

python3 ok

To test a specific question, use the -q option with the name of the function:

python3 ok -q <function>

By default, only tests that fail will appear. If you want to see how you did on all tests, you can use the -v option:

python3 ok -v

If you do not want to send your progress to our server or you have any problems logging in, add the --local flag to block all communication:

python3 ok --local

When you are ready to submit, run ok with the --submit option:

python3 ok --submit

Readings: You might find the following references useful:

Ray Tutorial

Multiprocessing in Python using Ray

If you face timeout errors, you might want to use the timeout flag while running the tests. Try --timeout 60 for a 60 seconds timeout.

Installing Ray

Before running the assignment you would need to install ray. You can simply run pip install -U ray in your console. For further details, you can visit Ray Installation Guide.

Q1: Parallel Map

Implement parallel_map, which takes a list arr and a mapping function f. It should return a new list computed by applying f to each element of arr. A serial version of the map function, serial_map is given for your convenience in understanding the problem and also for evaluating your solution (along with the function func). You must not change serial_map or func. Notice that ray has been initialized for you with 4 processes and you do not need to call ray.init().

Hint: The driver program, i.e., extra02.py runs in one of the 4 processes allocated for Ray. Hence, you can assume you have 3 more unused processes for your use.

def serial_map(arr, f):
    """A serial implementation of map. DO NOT CHANGE.
    >>> serial_map(list(range(10)), lambda x: x*2)
    [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
    >>> serial_map(list(range(10)), lambda x: x**2)
    [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
    """
    return [f(x) for x in arr]

def func(x):
    time.sleep(0.1)
    return x

def parallel_map(arr, f):

    """A parallel implementation of map
    >>> import time
    >>> parallel_map(list(range(10)), lambda x: x*2)
    [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
    >>> parallel_map(list(range(10)), lambda x: x**2)
    [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
    >>> arr = list(range(50))
    >>> start = time.time()
    >>> res_s = serial_map(arr, func)
    >>> end = time.time()
    >>> time_s = end - start
    >>> start = time.time()
    >>> res_p = parallel_map(arr, func)
    >>> end = time.time()
    >>> time_p = end - start
    >>> (res_s == res_p) == True
    True
    >>> (time_s/time_p > 1.5) == True
    True
    """
    "*** YOUR CODE HERE ***"

Q2: Parallel Merge Sort

Implement parallel_merge_sort, which takes a list arr and returns a new list with the elements sorted in ascending order. A serial version of the map function, sequential_merge_sort is given for your convenience in understanding the problem and also for evaluating your solution. You must not change sequential_merge_sort. Notice that ray has been initialized for you with 4 processes and you do not need to call ray.init().

Hint: The driver program, i.e., extra02.py runs in one of the 4 processes allocated for Ray. Hence, you can assume you have 3 more unused processes for your use. Hint: As we have a limited number of processes available, you might want to stop calling remote functions(which require new processes) after a certain depth of recursion.

def sequential_merge_sort(arr):
    """A parallel implementation of merge sort.
    >>> arr = [1,5,3,2,4,9,8,7,6]
    >>> sequential_merge_sort(arr)
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    """
    arr2 = arr.copy()
    if len(arr) > 1:

         # Finding the mid of the array
        mid = len(arr)//2

        # Dividing the array elements
        L = arr[:mid]

        # into 2 halves
        R = arr[mid:]

        # Sorting the first half
        L = sequential_merge_sort(L)

        # Sorting the second half
        R = sequential_merge_sort(R)

        i = j = k = 0

        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr2[k] = L[i]
                i += 1
            else:
                arr2[k] = R[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(L):
            arr2[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr2[k] = R[j]
            j += 1
            k += 1

    return arr2

def parallel_merge_sort(arr):

    """A parallel implementation of merge sort.
    >>> import random
    >>> import time
    >>> nums = list(random.sample(range(0, 1000000), 1000000))
    >>> start = time.time()
    >>> s1 = sequential_merge_sort(nums)
    >>> time_s = time.time() - start
    >>> start = time.time()
    >>> s2 = parallel_merge_sort(nums)
    >>> time_p = time.time() - start
    >>> (s1==s2) == True
    True
    >>> (time_s/time_p > 1.5) == True
    True
    """
    "*** YOUR CODE HERE ***"

Optional Questions

Section 2.4.9 describes a system for solving equations with multiple free parameters using constraint programming, a declarative style of programming that asserts constraints and then applies a general method of constraint satisfaction. The following questions ask you to extend that system. The code for the system appears at the end of this homework.

Q3: Triangle Area

Implement the function triangle_area, which defines a relation among three connectors, the base b, height h, and area a of a triangle, so that a = 0.5 * b * h:

def triangle_area(a, b, h):
    """Connect a, b, and h so that a is the area of a triangle with base b and
    height h.

    >>> a, b, h = [connector(n) for n in ('area', 'base', 'height')]
    >>> triangle_area(a, b, h)
    >>> a['set_val']('user', 75.0)
    area = 75.0
    >>> b['set_val']('user', 15.0)
    base = 15.0
    height = 10.0
    """
    "*** YOUR CODE HERE ***"

Q4: Squarer

The multiplier constraint from the readings is insufficient to model equations that include squared quantities because constraint networks must not include loops. Implement a new constraint squarer that represents the squaring relation:

def squarer(a, b):
    """The constraint that a*a=b.

    >>> x, y = connector('X'), connector('Y')
    >>> s = squarer(x, y)
    >>> x['set_val']('user', 10)
    X = 10
    Y = 100
    >>> x['forget']('user')
    X is forgotten
    Y is forgotten
    >>> y['set_val']('user', 16)
    Y = 16
    X = 4.0
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q squarer

Q5: Pythagorean Theorem

Use your squarer constraint to build a constraint network for the Pythagorean theorem: a squared plus b squared equals c squared:

def pythagorean(a, b, c):
    """Connect a, b, and c into a network for the Pythagorean theorem:
    a*a + b*b = c*c

    >>> a, b, c = [connector(name) for name in ('A', 'B', 'C')]
    >>> pythagorean(a, b, c)
    >>> a['set_val']('user', 5)
    A = 5
    >>> c['set_val']('user', 13)
    C = 13
    B = 12.0
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q pythagorean