Discrete Math EECS 203
Popular in Course
Popular in Engineering Computer Science
This 41 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 203 at University of Michigan taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/231553/eecs-203-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Discrete Math
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Antisymmetric Relations 0 De nition A relation R on A is said to be an tisymmetric if VabEAaRbbRa gtab o The picture for this is Except For C 0 Example The relation on R ifa b and b g a then a b 0 Example The subset relation g on 73X if AQB anngAthenAB Operations on Relations 0 Because relations are sets of ordered pairs7 we can combine them using set operations of union7 intersec tion7 and complement These are called the Boolean operations on relations 0 Example Let A 1 b c R a b a 0 ahdS c 1 Then BUS a b a c c 1 R H S Q and R AXBR 1 a b a b b b c c a c b c 0 Example Let A be the set ofpeople Let B brother of and S sister 0f Then B U S sibling of and B H S Q Composing relations 0 Because relations are generalizations of functions7 it makes sense to ask if we can compose them like func tions 0 Consider the enrolled i117 relation and the offered by77 relation The rst one is between students and courses7 and the second is between courses and de partments c We can compose the two relations to nd out which students participate in which departments 0 Let E stand for the enrolled in relation7 and 0 be the offered by relation We picture on the next slide the composition 0 o E 0 Even though E is the rst relation7 we respect the conventions for functional composition Recall that F o Gc new Participation in Departments OFFERED BY Ling STUDENTS COURSES DEPARTMENTS OFFERED BY 0 ENR STUDENTS DEPARTMENTS De ning relational composition 0 De nition Let R be a relation between A and B and S be a relation between B and C In this case the composition S o R can be de ned and is given by the following 80R ac E AXC Elbab E R and be E o This de nition says that in order to relate a to c all the way across fom A to 07 there has to exist a bridge element77 b in the set B o This suggests that there is some connection between the operation of relational composition and the con cept of transitivity Relational Composition related to Transitivity o If R is a relation on a set A a subset of A X A then we can always compose R with itself ln this case B o R a c awn b e R and b c e 3 Recall that R is transitive iff for all a 5 C7 if a b E R and b C E R then a C E R 0 Theorem A relation R on A is transitive if and only ifRoRg R The proof is in two parts i Assume that R is transitive Let a C E R O R We show a C E R Because a C E ROB7 there is a b so that 11 E R and b C E B By transitivity of R a C E R ii Conversely7 assume R o R g R We must show that R is transitive Applying the de nition of tran sitivity7 let 11 E R and b C E R Then a C E RoR Since RoR g R we get aC E R as we wanted QED Relational Composition and Boolean Matrix Multiplication o If you use the Boolean matrix representation of re lations on a nite set7 you can calculate relational composition using an operation called matrix multi plication See Chapter 2 for some background 0 Let R be a relation on a nite set A with n elements The Boolean matrix of R Will be denoted R and is an n X n array Rij7 Where Lj E A X A7 and 1 if 1 j e R 0 otherwise RM 0 Example Let A 1 2 3 and let R 1 2 2 3 3 2 3 3 Thequot 010 R 001 011 Example continued 0 Further7 let S 13317 so that the matrix of S is 001 S 000 100 0 We get the matrix for S o R by taking the matrix product R gtllt This is given by the formula 77 3 SW if ltRlltjgt SW 16gt j1 0 Note the similarity to the relational composition def inition z k e 801 H 3331 g j g nz j e RAj k e S Example concluded 0 1 0 0 0 1 0 Recall R O O 1 and S O O O 0 1 1 1 0 0 o For example7 to get the 173 entry of R gtllt we take row 1 of BL which is O 1 O7 and column 3 of 1 S7 which is O 7 and form 0 0A110000 using the truth tables for and V 0 You have to repeat this row i by column k for each entry 139 k of the product Closures of relations Sometimes you have a relation which isn7t re exive7 or isn7t symmetric7 or isn7t transitive For each of these properties7 we can add ordered pairs to the relation7 just enough to make it have the given property The resulting relation is called the re ex ive closure7 symmetric closure7 or transitive closure respectively Another way to say this is that for property X 7 the X closure of a relation R is the smallest relation containing R that has property X 7 Where X can be re exive or symmetric or transitive We denote the re exive closure of R by refcltRgt7 the symmetric closure of R by syde7 and the tran sitive closure by tcR Another popular notation7 though7 for the last is P Re exive and Symmetric Closures 0 These are easy and also are not used a lot 0 De nition The reflextve closure of a relation R on a set A ts de ned to be refePt RU MA 0 Example IfR 12 23 32 33 then V6f0ltRgt lt1gt2gt7lt273gt7lt372gt7lt373gtgtlt1gt1gtgtlt2gt2gt39 0 De nition The symmetric closure of a relation R on a set A ts de ned to be symeR R U R WW6 R 3495 55106 R Example IfR 12 23 32 33 then symCltRgt 12gtlt21gtlt23gtlt32gt7lt373gt Transitive Closure o This is more interesting adding ordered pairs is an iterative process 0 Transitive Closure on directed graphs shows where you can go using some number of arcs c To get the transitive Closure7 you rst add all arrows that traverse jump two original arrows then those that traverse three7 and so forth 0 We illustrate on the next slide Graphical construction of transitive closure NW a d b c Original Relation 1 Original Relation plus Zjurnps a d Original Relation plus 2ju1nps plus 3jurnp Recursive De nition of Transitive Closure 0 Given a binary relation R on a set A7 we use the following rules to construct the relation tcR x Basis if 3311 E R then 3311 E tCR Induction if 3611 E teltRgt and 112 E teat7 then as 2 E teR No pair is in teltRgt unless it is shown there using D 00 a nite number of applications of rules 1 and 2 o Example Ustng these rules on the example on the last sltde we rst use rule 1 three ttmes to put 11 96 and e d tnto teR 0 We add the two jumps wtth two uses of rule 2 once from 11 and 90 to get 10 and then from b e and e d to get I d 0 We then use rule 2 from 10 and gal to get a d the three jump 0 We need rule 3 to insure that teltRgt is the smallest transitive relation containing R For example7 S A X A is a much bigger transitive relation containing R Proving that tcR is what s advertised 0 We have to show that t0ltRgt is transitive7 and ii that if R g S and S is transitive then t0ltRgt g S o Proving is easy lf 3631 and 112 are in tCltRgt then they got there by some nite number of rule applications Just one more application of rule 2 puts as 2 into tcR o The proof of ii is a little harder Let 3 2 E tCR We use induction on the number n of rule applica tions necessary to get as 2 E tCltRgt7 to show that as 2 E S The proof continues on the next slide Proof continued Basis n 1 Then we used rule 17 which says as 2 E R Since R g S we have 332 E S7 completing the basis case Induction step Assume that whenever uv can be put into tcR by using k or fewer rule applications7 then uv E S Suppose we can put 13 2 into tCR using k 1 rule applications The last rule we use is without loss rule 27 so we had an 3311 E tCR k or fewer applications7 and also a 112 in tcR k or fewer applications By inductive hypothesis twice 3311 E S and 112 E S But S is transitive7 so as 2 E S7 as we wanted QED using using Characterizing tcR other ways 0 Since transitivity is connected to composition7 it makes sense to see if therels a way to express teltRgt using composition 0 There is a formula to that eiclect7 which leads to a matrix algorithm for calculating transitive closure 0 The formula requires de ning powers of a relation inductively 0 De nition Let R be a binary relation on A For j Z 1 we de ne the powers PM of R put R1 R and R7 PM o R 0 Theorem tcR a U37 j1 R1UR2UURjU You can prove by induction on n that 13 2 gets into teltRgt by n or fewer rule applications if and only if 6 z E U1Rj mnnn trio Quine northwestern e Introduction to Computer Engineering EECS 203 http39 i dickri it Review Quine McCluskey twolevel logic minimization lnstructor Robert Dick TA Nesi Ozs ornce L477 Tech ornce Tech inst L375 Email dickrp northwestern edu Pnone 847745770033 Compute prime implicants With a welledefined algorithm Pnone 84745772298 Email nealozz u nortnwestern edu Start from mmterms TT DEW BM Merge adjacent implicants until further merging impossible 0 TECH 395 L470 I Select minimal cover from prime implicaan Pnone 84749172083 Email debiidonortnwestern edu 39 Unate COVermg PVOblem o What is happening ab 33 Definition Unate covering on Prime implicants Use these to Given a matrix for which all entries are 0 or 1 find the minimum 01X 0X0 xm X11 cardinality subset of columns such that for every row at least one column in the subset contains a 1 On set MIWWW minterms M cover these N MIUUU I39ll give an example lmplicant selection reduction 0 Eliminate rows covered by sential columns a Eliminate rows dominated by other rows Eliminate columns dominated by other columns CMOS Summary Prepared by Robert Dick NMOS Transistors No current ows between gate and source or gate and drain If VGS gt VT7 they re on closed 7 Current may ow between drain and source If VGS lt VT7 they re off open 7 No current ows between drain and source They re good at transmitting 0s They re bad at transmitting 1s PMOS transistors s A 640 T No current ows between gate and source or gate and drain If VGS lt 7VT7 they re on closed 7 Current may ow between drain and source If VGS gt 7VT7 they re off open 7 No current ows between drain and source They re good at transmitting 1s They re bad at transmitting 0s Welcome to EECSCS 281 Me Sugih Jamin email jamineecsumichedu Office 4737 CSE Hours TueThu 300345 Fri 300400 and by appt but never right before lecture Tel 1 734 763 1583 Prereqs EECS 203 and 280 Strict GSls and IA 0 Brian Kirby kirbyb o TBD TBD 0 Christopher Peplin peplin GSI office hours will be held at the NE corner of the Dude 3rd flr Sugih Jamin Gamineecsumich edu Readings Required o Preiss Data Structures and Algorithms With ObjectOriented Design Patterns in C a Class handouts a Web site and Forum Recommended 0 Soulie J C Tutorial online 0 C stdib and iostream Reference online 0 Sebern string class online 0 Stroustrup The C Programming Language 3rd ed 0 Lippman and Lajoie C Primer 4th ed 0 Josuttis The C Standard Library Sugih Jamin Gamineecsumich edu Web site and Forum Web site httpirleecsumichedujamincourseseecs281 Forum not up yet 0 register first 0 DON T use your CAEN passwd 0 either use your uniqname as the forum account or use your umich email so that we can verify membership 0 DON T post solutions Honor Code violation No here s my code why doesn t it compilerun No this problem can be solved using data structure X or algorithm Y If in doubt err on caution and ask by email Sugih Jamin Gamineecsumich edu What 281 covers How to build various tools from existing ones data structures How some tools are better for certain tasks than other tools performance analysis When you have a hammer every problem looks like a nail Not How to go about solving a task using the tools algorithms How to improve the tools and solutions and to hone your programming skills Sugih Jamin Gamineecsumich edu Data Structures and Algorithms Data structures collections of variables possibly of different data types connected in various ways Algorithms methods for solving problems that are suited for computer applications Algorithm Data Structures Programs N Wirth Algorithmic Thinking Conceptualize problems with digital representations and seeks algorithms that express or find solutions PJ Denning Sugih Jamin Gamineecsumich edu Discussion Session Make sure you register for a discussion session 0 W 330430 2150 DOW o W 330430 1003 EECS o F 1302301006 DOW there will be NO discussion this week Sugih Jamin Gamineecsumich edu Grading Policy Course grade composition 0 Final 20 o Midterm 20 o HomeworksHWs 12 0 Programming Assignments PAs 46 0 Class Participation 2 Four free late days incl weekends and holidays You must keep track of your own late days Sugih Jamin lamineecsumich edu Regrade 0 except for arithmetic error in grade computation all regrade requests must be made in writing 0 must explain the technical reasons requiring regrade a must be made 5 working days after the work is returned to the class except same day for final exam 0 the whole work will be regraded Sugih Jamin Gamineecsumich edu Cheating and Collaboration You are encouraged to learn from each other We look fonIvard to lively discussions in class and on the forum However cheating is not tolerated and will be reported to the Honor Council Cheating is when you copy with or without modification someone else s work It is also considered cheating to knowingly expose your solutions or to use some other publicly available solutions NOTE It is also considered cheating to have a different algorithm implemented than the one specified in the programming assignment When in doubt ask Sugih Jamin lamineecsumich edu Exams Midterm Thu Oct 25th 600800 pm Final Exam Wed Dec 19th 400600 pm Scheduling conflicts 0 only documented medical or personal emergency allowed a if you need extra time to complete an exam due to personal disability please inform us 1 week in advance a other scheduling conflicts will not be considered two weeks after the start of the term today a outside commitments eg job interviews marching band trips topcoder contests are not considered valid reasons for missing an exam Sugih Jamin lamineecsumich edu Assignments Homeworks to be turned in hardcopy in the 281 lockbox in 2420 EECS Programming assignments o no group project 0 no STL 0 must not include external materials eg opensource code downloads unless requested 0 must compile and run on CAEN s Linux with the latest version of g Put your uniqname on EVERYTHING you turn in Do NOT submit ANYTHING by email Sugih Jamin lamineecsumich edu Programming Assignment Grading Grading criteria 0 code compiles 0 code runs correctly 0 code runs fast 0 code is readable welldocumented eg o no use of literals 0 code reuse instead of cutandpaste o algorithm is efficient o implementation is efficient eg o no unnecessary copying o no loop invariant statement in loop Sugih Jamin lamineecsumich edu Magic Show Sugih Jamin Gamineecsumich edu Performance Analysis of Name Search Best case Worst case Average case Common case What s the difference between average and common cases Sugih Jamin Gamineecsumich edu Execution Cost Algorithms take resources to execute Resources 0 Space memory bandwidth 0 Time Two types of resource cost 0 fixed cost 0 variable cost Sugih Jamin Gamineecsumich edu Space Time Tradeoff If you can load all your data into memory you can sometimes come up with very fast algorithm Where space matters 0 handheld devices 0 embedded systems 0 large dataset problems examples Sugih Jamin Gamineecsumich edu Timing Cost Fixed cost onetime cost a coding time o compile time a variable initializations o etc Variable cost a run time depends on the size of the problem Sugih Jamin lamineecs umich edu Runtimes of our name search problem Assume can search 10 namesms Population size l Linear l Binary EECS 281 100 10 ms 07 ms Iookup 7 names UM 40000 4 secs 15 ms Washtenaw 35 secs 18 ms MI 9 mil 15 mins 23 ms US 290 mil 8 hours 28 ms World 6 billion 7 days 33 ms Implication there is usually more than one way to solve a problem Want the most efficient way Sugih Jamin iamineecsumich edu Algorithm Design Typical approach 0 define problem to be solved 0 understand its complexity o decompose it into smaller subtasks Algorithmic Thinking Conceptualize problems with digital representations and seeks algorithms that express or find solutions PJ Denning Sugih Jamin lamineecsumich edu Algorithm Design Typical approach 0 define problem to be solved 0 understand its complexity o decompose it into smaller subtasks Creative refinements 0 think outside the box exploit any particular characteristics of the workload or problem 0 don t lose the forest for the tree find the real performance bottleneck of the whole program how also note the human labor cost 0 optimize for the common case Sugih Jamin lamineecsumich edu Mirror mirror on the wall Given two algorithms how do you determine which is more efficient Example roofing problem 0 A new house is being built down the road 0 The builders are currently working on the roof 0 There are three different methods for moving shingles from the shingle truck to the roof Sugih Jamin lamineecsumich edu Three Roofing Methods Method 1 A builder can carry two shingles on his shoulder as he climbs up the ladder He then climbs down and carries two more shingles up the ladder Each round trip up and down the ladder costs 2 Method 2 The builder rents a lift for 10 The lift can move 20 shingles up the roof at one time at a cost of 1 per round trip Method 3 The builder rents a superlift for 40 Unfortunately the lift has a slow leak in its hydraulic system It is able to lift half of the necessary shingles to the roof on the first roundtrip However on the second trip it is only able to lift half of the remaining shingles then half of the remaining down to the minimum of one shingle per round trip Each round trip costs 2 In all three methods it costs 4shingle to nail it to the roof Sugih Jamin lamineecsumich edu