We Helped With This Python Programming Homework: Have A Similar One?

CPEG 151 Assignment 3 – Recursion (20 Points)

Task 1 – Binomial coefficients (3 Points)

𝑛

Binomial coefficients 𝑘 satisfy the following recurrence:

                                       𝑛        𝑛 − 1        𝑛 − 1

                                             =              +            for all integers n,k: 1 ≤ k ≤ n-1, with

                                      𝑘        𝑘 − 1           𝑘

                                                               𝑛        𝑛

                                                                      =        = 1 for all integers n≥1.

                                                                0        𝑛

Alternatively, they can be defined as

                                                                       𝑛            !

=  for 0 ≤ k ≤ n.

                                                                       _{𝑘        !(           )!}

Here, 𝑛! = ∏       𝑖 denotes “n factorial”. Likewise, 𝑘! = ∏     𝑘

A)    Implement a function recur_binomial(n,k) using this recursion alone.

B)    Implement a function fact(n) to compute the factorial of n.

C)    Implement a function binomial(n, k) using the second definition. 

For all functions, write down the preconditions as stated above using a DocString. Test all functions within the preconditions; recur_binomial() should give the same result as binomial().

Task 2 – Perfect Shuffles (3 Points)

To test sorting functions, it is helpful to generate a list of randomly permuted integers. One algorithm to do so it D. Knuth’s Perfect Shuffle:

1) Generate a list containing all integers from 0 to N-1 2) For each list element at position n:

a.      Generate a random integer k between n and N-1 (both inclusive)

b.      Swap integers at positions n and k

It is important that k includes the current position n, since otherwise fix points (that is, not swapping an integer) are not possible. In a sense, this algorithm is the inverse of selection sort, since it generates one correct element at the front of the list per iteration.

Implement a function perfectShuffle(N) that generates a random sequence of integers 0…N-1. You can generate a random integer between n and N-1 by using random.randint() from module random.

Task 3 – Merge Sort (6 Points)

In class, you saw two sorting algorithms (and variations), insertion sort and selection sort. In this task, you will implement Merge Sort.

The basic idea in merge sort is to split down a list of numbers recursively into lists that each contain a single element. The base case is that a list with only one element is already sorted, and the recursion is stopped. While combining results, two neighboring sorted lists are merged to form the final merged list.

A)    Implement a recursive function merge(L1,L2), where L1 and L2 are lists that contain sorted numbers. At most one of the two lists may be empty. The recursion should terminate when one of the two lists is empty. Otherwise, split each list into head and tail. Return a list containing the smaller of the two tails, followed by a call to merge with one tail and the other list. Test your function and write down the preconditions in a DocString.

B)    Implement a function mergeSort(L), where L is a list containing numbers. The base case is len(L)==1 which should return a (trivially) sorted list. Otherwise, recursively split L into a left and a right half and merge. Test your implementation using a list generated with perfectShuffle(). Write down the preconditions in a DocString.

Task 4 – Binary Search (4 Points)

One reason why we often like to keep data sorted is we can quickly find a given element n in a sorted list using binary searches. The basic idea is to pick an element roughly at the half of the list, called the pivot. If the number n we are looking for is smaller than the pivot, we recursively look for n in the left half of L, otherwise we check the right half of L. 

Implement a binary search function search(L, n, base=0). The function should return the position of n in the list if L contains the element. Otherwise, return None. L is potentially empty list containing sorted numbers, n is the number we are looking for, and base is the starting position of the recursive list with respect to L. For instance, if during a recursion we split the original list L into a left half L1[:k] and a right half L2[k:] for some integer 0 <= k < len(L), we would keep base at its original value for L1 (since it still starts exactly where L started) and set it to base+k for L2 (since L2 starts k elements after L).

Task 5 – Projects (4 Points)

As part of this course, I would like you to implement some projects of your own. These projects will be a bit larger than your homework, but to make up for it, you may work in teams of 2 persons and you will have more time. To make sure you work on a topic you like, please check some of the Python projects others have done online for inspiration. Then, write a short project proposal for a 4-week project, including the following:

•      What modules do you think you need in order to finish the project?

•      What do you realistically hope to have achieved after three weeks?

•      How is the project different from projects others have already done?           Also list the project(s) closest to your proposal that you found.

All proposals will be evaluated and may require changes before approval. Once approved, you will work on the project for 4 weeks and present it in class (ca. 15 minutes per project) at the end of the project. A selection of interesting topics could be image processing, writing a clever user interface in Tcl for some existing project, data mining (for instance, a blockchain parser), a data visualizer, AI-based projects using Keras, TensorFlow, PyTorch, etc. 

Hints

As discussed in class, a non-empty list L can be split into head and tail in Python3 as follows.

head, *tail = L

Also as discussed in class, list elements at positions i and j can be swapped as follows.

L[i], L[j] = L[j], L[i]

Deadline: Submit two files: A python file containing your implementations and a pdf with a brief (one half to one page) project description before Thursday 28-Feb-2019 midnight either by mail to ... or Canvas.