Question

Problem SubsetSum Input: A string representing a list of base- 10 integers, separated by spaces, followed by a semicolon, followed by a base-10 integer K. Output: "yes" if any subset of the elements in the list sum to K. "no" otherwise. [40 pts. Submit a .py file.] Write a nondeterministic SISO Python program that solves SubsetSum. You must use the nondeterminism utilities from WCBC. [5 pts. Include your answer in your write-up.] How many subsets would you need to look at if you were solving this problem deterministically, and therefore you looked at all possible subsets of the original N elements in a single thread? [5 pts. Include your answer in your write-up.] How many elements does a single sequence of threads look at, in the worst case, in your nondeterministic program? Assume there are N elements total. Here is the general algorithm: 1. Start with the entire list of elements, signifying that you have not picked any to be in your subset yet. 2. Nondeterministically choose one element of your current list to include in your subset. Remove all the elements up until the chosen element and decrease the target by the chosen element. This means launching a thread for each chosen element. 3. Recursively apply this "choose and remove" strategy until you've either run out of elements or your target reaches zero (meaning the subset you've assembled has a sum equal to the original target!). Each time you recurse, spawn threads for each possible choice at that level. Implementation details 1. Parse the input by splitting on the semicolon. Split the left side by space, then convert each element into an integer. These are your elements. Convert the right side into an integer. This is your target K. 2. Like in the solution to MT1 Q4, launch a single thread that runs the helper function with all the elements and the target equal to K (signifying that your subset is empty so far). 3. When launching new threads, get your remaining elements by slicing the existing list starting at the chosen element: newRemaining = remaining [ indexofChosen +1:] (Your variable names will, of course, differ, but this is the general approach.) Only use ndSoln. setSolution( 'yes ') when you are ready to report a success. Don't use ndSoln. setSolution ( 'no ' ) at any point. Letting a thread just end after the helper function returns is good enough to report a failure.

Answer 1

The nondeterministic SISO Python program for SubsetSum using the nondeterminism utilities from WCBC is designed to output "yes" if any subset of the input elements sums to the specified target K, and "no" otherwise.

Step-by-step explanation:

The nondeterministic algorithm operates by exploring various potential subsets through a "choose and remove" strategy. At each step, it nondeterministically selects an element from the current list to include in the subset, updating the remaining elements and target accordingly.

This process is repeated recursively until either the target becomes zero, indicating a successful subset sum, or there are no more elements to consider. The program spawns threads for each possible choice at each level, allowing for parallel exploration of different paths.

In the worst-case deterministic scenario, solving SubsetSum would require examining all possible subsets of the original N elements. The number of subsets of a set with N elements is given by 2^N. Therefore, in a single-threaded deterministic approach, you would need to look at 2^N subsets.

In the nondeterministic program, the number of elements a single sequence of threads considers in the worst case is N. This is because at each level of recursion, one element is chosen from the current list, and the remaining elements are updated accordingly.

The process continues until either a successful subset sum is found or there are no more elements to consider. Therefore, in the worst case, the program explores N elements in a single sequence of threads.