CS61A Lecture 19: Sets

4 Pages
124 Views

Department
Computer Science
Course Code
COMPSCI 61A
Professor
De Nero

This preview shows page 1. Sign up to view the full 4 pages of the document.
Description
Sets One more built-in Python container type Set literals are enclosed in braces Duplicate elements are removed on construction Sets are unordered, just like dictionary entries s = {3, 2, 1, 4, 4} {1, 2, 3, 4} s.union({1, 5}) = {1, 2, 3, 4, 5} return all elements either in set or in other set s.intersection({6, 5, 4, 3}) return set of all elements that are in both set Implementing Sets What we should be able to do with set: Membership testing: Is value an element of a set? Union: return set with all elements in set1 or set2 Intersection: return set with any elements in both set1 and set2 Adjunction: return set with all elements in s and a value v Never mutate input sets, create new output set Sets as Unordered Sequences Proposal 1: A set is represented by recursive list that contains no duplicate item def empty(s): return s is Rlist.empty def set_contains(s, v): """Return true if set s contains value v as an element. >>> set_contains(s, 2) True >>> set_contains(s, 5) False """ if empty(s): return False elif s.first == v: return True else: return set_contains(s.rest, v) def adjoin_set(s, v): """Return a set containing all elements of s and element v. >>> t = adjoin_set(s, 4) >>> t Rlist(4, Rlist(1, Rlist(2, Rlist(3)))) """ if set_contains(s, v): return s else: return Rlist(v, s) def intersect_set(set1, set2): """Return a set containing all elements common to set1 and set2. >>> t = adjoin_set(s, 4) >>> intersect_set(t, map_rlist(s, lambda x: x*x)) Rlist(4, Rlist(1)) """ in_set2 = lambda v: set_contains(set2, v) return filter_rlist(set1, in_set2) def union_set(set1, set2): """Return a set containing all elements either in set1 or set2. >>> t = adjoin_set(s, 4) >>> union_set(t, s) Rlist(4, Rlist(1, Rlist(2, Rlist(3)))) """ not_in_set2 = lambda v: not set_contains(set2, v) set1_not_set2 = filter_rlist(set1, not_in_set2) return extend_rlist(set1_not_set2, set2) Review: Order of Growth For set operation that takes "linear" time, we say that n: size of the set R(n): number of steps required to perform operation R(n) = Theta(n) positive constant k1 and k2 such that k1 * n <= R(n) <= k2 * n for sufficiently large values of n Order of growth: Theta(N^2) Sets as Ordered Sequences Proposal 2: A set is represented by a recursive list with unique elements ordered from least to greatest Order
More Less
Unlock Document

Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit