Answered step by step
Verified Expert Solution
Question
1 Approved Answer
3. (30 points) Set Intersection Python has a built in set data structure. A set is a collection of elements without repetition. In an interactive
3. (30 points) Set Intersection Python has a built in set data structure. A set is a collection of elements without repetition. In an interactive Python session, type the following to create an empty set: s=set() To find out what operations are available on sets, type: dir(s) Some fundamental operations include add, remove, and __contains__ and __len_.. Note that __contains__ and __len__ are more commonly called with the syntax element in set and len(set). All four of these operations run in constant time i.e. O(1) time. For this problem, we will be analyzing the runtime of s.intersection( t ) that takes two sets, s and t, and returns a new set with all the elements that occur in both s and t. We will then use intersection in a new version of the Document Distance code from the first lecture. (a) (5 points) Using notation, make a conjecture for the asymptotic running time of s.intersection( t ) in terms of the sizes of the sets: s and t. Justify your conjecture. HINT: Think about the fundamental operations above. (b) (10 points) Determine experimentally the running time of s. intersection( t), by running it with different sized sets. Fill in the following chart. Include in your PDF submission a snippet of code that determines one of the entries in the chart. Note: there are a number of ways to time code. For example, you can use the timeit module (see https://docs.python.org/3/1ibrary/timeit.html for documentation on how to use it). (c) (5 points) Give an approximate formula for asymptotic running time of s.intersection(t) based on your experiments. How does this compare with your conjecture in part (a)? If the results differ from your conjecture, make a new conjecture about the algorithm used
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started