Write all of your Python code for this assignment in a single file named lab1.py. You should have two functions, followed by a “main” at the bottom:
# Problem 1
def power_set(S):
# Your code here
# Problem 2
def show_marathon_options(movies, low, high): # Your code here
# Problems 3-4
if name == ‘ main ’: # Your code here
1. (12 points) Consider a set S of n elements, a1, a2, a3, ..., an . P (S), the power set of S, is the set of all subsets of S. Note that we can find all the subsets of S recursively. To understand the algorithm, first observe that given any element in S, the subsets of S can be divided evenly into those that contain that element and those that do not. For example, consider the element Rowlet from the set {Torchic, Rowlet, Piplup}. There are 4 subsets that contain Rowlet:
{Rowlet}, {Torchic, Rowlet}, {Rowlet, Piplup}, {Torchic, Rowlet, Piplup}. And there are 4 subsets that don’t contain Rowlet: {}, {Torchic}, {Piplup}, {Torchic, Piplup}.
1
We can approach the problem of finding all subsets of {Torchic, Rowlet, Piplup} like this:
• First, remove Rowlet and find all subsets of {Torchic, Piplup}: {}, {Torchic}, {Piplup},
{Torchic, Piplup}
• Now, make a copy of those subsets, and insert Rowlet into each of them: {Rowlet},
{Torchic, Rowlet}, {Rowlet, Piplup}, {Torchic, Rowlet, Piplup}
• Combine the two sets of subsets from above to get the answer. Now we can generalize! To find all subsets of set S:
• Pick any element x ∈ S, and remove x from S.
• Find all subsets of S, which is now smaller by one element (this looks awfully recursive...)
• Now, make a copy of those subsets, and add x to each of them.
• Combine the two sets of subsets from above to get the answer.
Write a Python function power set(S) that returns the power set of S using this recursive algorithm. Represent the sets using Python lists. The empty set can be represented with the empty list, []. The power set function should return a list of lists. For example, calling power set([1, 2]) should return something like [[], [1], [2], [1, 2]].
Recursion hint: What should your base case be?
Python hint: Suppose you have a list named list1 and you want to make a copy of it. Writing list2 = list1 is legal, but it only creates a shallow copy. Any changes to list1 will also be reflected in list2. (This is the same idea as having two references to the same array in Java.)
To make list2 independent from list1, you can ask Python to make a deep copy. An easy way of doing this is to use the built-in deepcopy function, located in the copy module:
from copy import deepcopy list2 = deepcopy(list1)
Note: You are expected to implement power set recursively, using the algorithm presented here. Do not use itertools or similar modules.
2. (12 points) Suppose you want to organize a movie marathon night for you and some friends, and you have the following movies available:
Title Runtime (minutes)
Back to the Future 116
How to Train Your Dragon 98
The Land Before Time 69
The Lord of the Rings: The Return of the King 201
Tangled 100
Titanic 194
There are many ways to pick movies for a marathon of a certain length. If you want the marathon to be between 3-5 hours (180-300 minutes), for example, any of these would be valid options:
• Titanic (total runtime: 194 minutes)
• Back to the Future, How to Train Your Dragon, The Land Before Time (total runtime: 283 minutes)
• How to Train Your Dragon, Tangled (total runtime: 198 minutes)
For this problem let’s disregard the order in which the movies are played – we care only about
which movies are picked for the marathon.
One way to see which combinations of movies are possible is to consider all subsets of your set of movies. For each subset, compute its total runtime, and keep only those subsets that have a total runtime within the desired range.
Each movie in your collection can be represented in Python as a list of two elements: the title (a string) and the runtime in minutes (an integer). For example, Tangled can be stored as the list [‘Tangled’, 100]. The entire set of movies can then be represented as a list of these lists (i.e., a 2D list).
Write a Python function show marathon options(movies, low, high) to show your options. Specifications:
• The parameter movies is a 2D list formatted as described above, and the parameters low and high are the minimum and maximum total runtime of your marathon in minutes, inclusive.
• The function should print all possible combinations of movies that meet those conditions, formatted like the example below. Again, the order of the movies in each combination is ignored – we care only about which movies are selected.
• The function should not return any value.
• The function should work for any list of movies structured this way – don’t hard-code the values from the table into the function.
• Call your power set function as needed.
Example: calling show marathon options(movies, 180, 300) with movies defined as above should result in this output:
1. Back to the Future, How to Train Your Dragon, total runtime: 214 mins
2. Back to the Future, The Land Before Time, total runtime: 185 mins
3. Back to the Future, How to Train Your Dragon, The Land Before Time, total runtime: 283 mins
4. The Lord of the Rings: The Return of the King, total runtime: 201 mins
5. How to Train Your Dragon, The Lord of the Rings: The Return of the King, total runtime: 299 mins
6. The Land Before Time, The Lord of the Rings: The Return of the King, total runtime: 270 mins
7. Back to the Future, Tangled, total runtime: 216 mins
8. How to Train Your Dragon, Tangled, total runtime: 198 mins
9. Back to the Future, The Land Before Time, Tangled, total runtime: 285 mins
10. How to Train Your Dragon, The Land Before Time, Tangled, total runtime: 267 mins
11. Titanic, total runtime: 194 mins
12. How to Train Your Dragon, Titanic, total runtime: 292 mins
13. The Land Before Time, Titanic, total runtime: 263 mins
14. Tangled, Titanic, total runtime: 294 mins
3. (4 points) Within your code’s main portion, write some test code for both of your functions.
For power set, verify that the function works correctly for arguments of several different lengths. Be sure to test with a list of length 0 too!
For show marathon options, test by using the set of movies from the earlier table.
4. (6 points) Our approach to finding all marathon options requires considering all subsets of the set of movies. Since we have only 6 movies to consider, there are 26 = 64 total subsets to analyze, which is trivial for a computer. But what if we modestly increase the size of the movie collection to 20? Suddenly we’re looking at 220 = 1,048,576 subsets!
Within your code’s main portion, create a new 2D list representing a set of 20 movies. You can use real movie data, or just make up some data. Then time how long it takes for your show marathon options function to run on this set of 20 movies. You can use Python’s process time function, located in the time module:
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
