Set Intersection Python has a built in set data structure. A set is a collection

Question

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. You can use the timeit module (see http://www.diveintopython.net/performance tuning/timeit.html for a good description of how to use it). Alternatively, if you have ipython installed (see http://ipython.scipy.org), you can use their builtin timeit command which is more user friendly. time in µs |s| = 103 |s| = 104 |s| = 105 |s| = 106 |t| = 103 |t| = 104 |t| = 105 |t| = 106 (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.

Explanation / Answer

http://www.programiz.com/python-programming/set

please do refer this link.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.