COMPSCI 61A Lecture Notes - Lecture 19: Kruskal'S Tree Theorem

52 views4 pages
24 Oct 2013
School
Professor
zogo39484755 and 6 others unlocked
COMPSCI 61A Full Course Notes
22
COMPSCI 61A Full Course Notes
Verified Note
22 documents

Document Summary

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} s. intersection({6, 5, 4, 3}) return all elements either in set or in other set return set of all elements that are in both set. What we should be able to do with 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. 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): False if empty(s): return false elif s. first == v: return true else: return set_contains(s. rest, v) def adjoin_set(s, v): 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):

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

Related Questions