Discrete Struc CECS 228
Popular in Course
Popular in Computer Science and Engineering
This 22 page Class Notes was uploaded by Zackary Cronin on Monday October 5, 2015. The Class Notes belongs to CECS 228 at California State University - Long Beach taught by Todd Ebert in Fall. Since its upload, it has received 54 views. For similar materials see /class/218746/cecs-228-california-state-university-long-beach in Computer Science and Engineering at California State University - Long Beach.
Reviews for Discrete Struc
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/05/15
Lecture 16 Relations 0 Associated reading Rosen7 Section 61 o Homework Section 61 Problems l llodd7 121315 2lodd725 28729 35 Relations between objects are of fundamental importance to both computer science and com puter engineering For example7 databases are collections of tables that represent relations between one or more sets of objects And partial order relations are used to schedule events for ef cient parallel processing Let A and B be subsets A relation from A to B is a subset R of A gtlt B The following are equivalent oaRb oab R o a is related to b77 Example 1 Let A be the set of students enrolled at CSULB during Fall 20027 and B be the set of courses offered during Fall 2002 Let R be a relation from A to B such that Lab 6 R if and only if student a is enrolled in course b Give some examples of elements of the relation A relation R from A to A is called a relation on A Example 2 Let A be the set of logic gates that make up afull adder De ne the connectivity relation Con A In other wordls7 Lab 6 C if gates a and b are connectedl7 and the electric ow is from gate a to gate b Give a list of elements in the relation Properties of a relation R on a set A o re exivity a7 a E R for every 1 E A o irre exivity a7 a Z R for every 1 E A 0 symmetry Lab 6 R a b7a E R7 for every 1 and b in A o antisymmetry Lab 6 RA b7a E R a a b7 for every 1 and b in A asymmetry 17 b E R a b7 1 Z R7 for every 1 and b in A transitivity Lab 6 RA he 6 R a 10 6 R7 for every Lb7 and c in A Example 3 Determine which properties the connectivity relation 0 has Example 4 Let A be the set of United States De ne relation R on A by 17 b E R if and only if a and b share a boarder Which of the above properties does R possess Example 5 Multi tasking operating systems and parallel processing computers need to know the dependencies between different instructions that must be executed ln general7 let T be a set of tasks Let R be a relation on T de ned by thtg if the completion of task t1 is required before task t2 can be started What properties does this relation have Example 6 Let P be a set C programs and R be a relation on P such that 101102 6 R iff program p1 calls program p2 For the relation7 discuss the different relational properties and relate them to programming style and methodology Ways of forming new relations Let R1 and R2 be relations from set A to set E Then the following new relations can be formed 0 union R1 U R2 0 intersection R1 R2 0 difference R1 7 R2 0 symmetric difference R1 EBRZ Example 7 Let A be the set of instructors in CECS7 B the set of CECS Classes offered in Spring 2003 De ne relations R1 and R2 by 0 aRlb iff as favorite course is course b o aRgb iff a is teaching course b in the Spring ln words what do the relations R1 U R2 R1 R2 R1 7 R2 R1 69 R2 represent Lecture 17 Relations II An n ary relation is a subset of A1 gtlt A2 gtlt gtlt An 0 n is called the degree of the relation 0 each set A is called a domain 0 n ary relations represent the basic building blocks of relational databases In this case i the relation is called a relational table 7 each set A is called a eld of the table 7 each element of the table is called a record 7 a set A for which every element of the set occurs at most once in the table is called a primary key Example 1a For the table below identify all the elds records and primary key What is the degree of the relation Last Name ID Midterm 1 Midterm 2 Ballard 1342 82 70 Jones 2167 30 90 Pham 9283 15 80 Pham 7122 30 60 Select Operation Let R C A1 gtlt A2 gtlt gtlt An be an n ary relation and P a predicate whose variables correspond with the elds A1A2 7An Then the selection operation selR7 P is a subset of R such that a17a27an E selR7 P ltgt Pa1a2an 1 Example 1b For the relation of Example 1a7 use the select operation to select only those students who scored above 75 Projection Operation Let A1 gtlt A2 gtlt gtlt An be an n ary relation Then the projection operation Pi grim maps an n th degree relation to an m th degree relation using the following rule Pi1i2im117127 7a at17am 70 Example 2 For the relation of Example 1a7 determine the relations PM and PM Join Operation Let R1CA1gtltA2gtltgtltAmgtltB1gtltB2gtltgtltBn and RZCBIgtltB2gtltgtltBngtlt01gtltO2gtltgtltOp be relations Then 017027 7 L7n7l917l927 bn7017027H 7017 E J0mR1R2 if and only if 0170277am7b17bz77bn E R1 and b17b277bn7017627 70p 6 R2 Example 3 Suppose a student would like to know if a cecs 228 Class he wants to enroll in has a left handed desk in the Classroom it will meet in Use the join operation on the following two tables to determine this Course Information Table Course Section Room CECS 228 1 VEC 518 CECS 228 2 VEC 330 CECS 228 3 VEC 418 CECS 228 4 VEC 330 CECS 228 5 LEGO SCI 225 Room Resource Table Room RHDesks LHDesks VEC 330 32 0 VEC 332 32 0 VEC 418 28 4 VEC 518 32 0 VEC 530 30 2 Joining the course table with the room table Course Section Room RHDesks LHDesks CECS 228 CECS 228 CECS 228 CECS 228 Equivalence Relations An equivalence relation R C A gtlt A is a relation on a set A with the properties of being 0 re exive o symmetric and o transitive For an equivalence relation we write 11 as 1 NR b or just a N b if the relation R is understood Also used is 1 ER b and a E b In all cases this reads a is equivalent to b Example 4 Let P be the set of all C function programs which input and return type int We say that two programs p1 and p2 are related if and only if p1n p201 for every integer n In other words the programs output the same values given the same input Verify that this relation represents and equivalence relation Example 5 For some integer c gt 07 we say that two integers a and b are equal modulo 0 written as a b mod 0 if and only if a 7 b is a multiple of 0 In other wordls7 there is an integer k for which a 7 b ck Show that equality modulo 0 is an equivalence relation Given an equivalence relation R on a set A and an element a 6 A7 the equivalence class of a7 denoted a7 is de ned as lal bla N 5 ln other words7 it is the set of elements from A which are equivalent to 1 Example 6 For the equivalence relation of Example 57 write the equivalence class for both 1 and 13 Given a set A7 a partitioning of A is a collection of sets B1 B2 Bn such that 1 AB1UB2UUBn 2 Bi Bj ifz397 j Example 7 Partition the set of integers into four sets B 17B27B37B47 where each set is in nite Theorem 1 Given an equivalence relation R on a set A7 the set of equivalence classes a a E A forms a partition of set A In other wordls7 for every 1 and b 6 A7 either a b or a b Q 2 Conversely7 given a partition B1 B2 Bn of A7 there exists an equivalence relation R on A whose distinct equivalence classes are B1 B2 7B Proof Example 8 Write out the equivalence classes for the equivalence relation of Example 5 Partial Orderings A partial order R C A gtlt A is a relation on a set A with the properties of being 0 re exive o anti symmetric and o transitive For a partial order 0 we write 11 as a S b and reads a is less than or equal to b 0 we denote a partial order 3 on a set A as a pair A S o a set that has a partial ordering relation de ned on it is commonly called a poset 0 note that there exist strict partial orders for which re exivity is replaced by irre ex ivity and anti symmetry with asymmetry Example 10 Verify that Z S is a partial order where S is the usual inequality relation on numbers Example 11 ls 1333 a partial order where f S 17 if and only if S Given a partial order A S o a and b in A are called comparable if and only if either a S b or b S 1 Otherwise they are called incomparable 0 any relation in which every pair of elements is comparable is called a total order or linear order or chain 0 a E A is called a maximal element if and only if every element that is comparable with a is less than or equal to a o a E A is called a minimal element if and only if every element that is comparable with a is greater than or equal to a o a total ordering A S is called a wellordering if and only if every nonempty subset of A has a minimal element Example 12 Verify that A l is a partial order where A 1 2 20 and all is true if and only if a divides into b What are the minimal and maximal elements of this ordering ls this a total order Example 13 Consider a set of tasks T that must be completed De ne a relation R on T where thtg if and only if the completion of task t1 is necessary for the starting of task t2 ls R a partial order If not what kind of relation is it There exists a nice way to graphically represent partial orderings with what are called Hasse diagrams Each element of A is placed in a number of increasing rows 71371771 Two elements in adjacent rows are then connected by a line segment if and only if they are comparable Drawing the diagram can be described recursively as follows 1 Basis step Place all minimal elements in To 2 Inductive step repeat until every element of A has been placed in a row Suppose rows r0771 77 have been completed Then place an element 0 in row 11 if and only if all of the following conditions are met a c has yet to be placed b there is some element a E Tn for which a S c c there is no element b for which a S b S 0 Example 14 Draw a Hasse diagram for the poset de ned in Example 12 Lecture 5 BigO Notation 0 Associated reading Rosen7 Section 18 o Homework Section 187 problems 137577915719723751741 Growth of Functions BigO f Ogx iff there exists constant C gt 0 such that S Cgx for suf ciently large x Example 1 Using the de nition of big O7 show that f 6x2 7 2x 5 is 0z3 Example 2 Show that f 3 is not 0x2 Example 3 Give as good a big O estimate as possible for the sum 1222n2 BigOmega fx iff there exists constant C gt 0 such that 2 Clgxl for suf ciently large x Example 4 Show that f 3 is BigTheta f gz iff f Ogx and g In this case functions f and g are said to be of the same order Example 5 Show that z is of the same order as 712 little0 f 0gz iff a 0 as x a 00 Example 6 Show that f logx is 0z Some Important bigO results 1 Polynomials of the same degree are of the same order 2 If polynomial P has lesser degree than polynomial Q7 then P 0Q 3 f1 f2 0maxlf1l7lf2l 4 f1 091 and f2 092 i f1f2 09192 Proof of 3 Example 7 Give a big O estimate of the function f slogx4 1 zlog z2 Your answer should be of the form Ogx where g has the smallest order possible Explain
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'