### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Discrete Mathematics I CS 2102

UVA

GPA 3.71

### View Full Document

## 14

## 0

## Popular in Course

## Popular in ComputerScienence

This 14 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 2102 at University of Virginia taught by John Knight in Fall. Since its upload, it has received 14 views. For similar materials see /class/209678/cs-2102-university-of-virginia in ComputerScienence at University of Virginia.

## Popular in ComputerScienence

## Reviews for Discrete Mathematics I

### 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: 09/21/15

More On Predicates e John c KnightZDDE 7 All rights reserved Quantifiers El Quantified expressions are propositions T or F El Recall the quantifiers are I Existential El a Unique 31 I Universal V El General forms I El variablelist predicate7 o predicate2 I V variablelist predicatej o predicate 1 university arVireinie Bound Variables El The variablelist has the general form I variablename type variablename type El The name of a variable is just an identifier El The type of a variable is just a set El The scope of a variable is just the quantifier El These variables are called bound variables El Examples V x mycomputers laptopx o IBMx V x 39 computers y 39 users laptopx adulty V o OKtousey x University er Virginie Negation Of Quantifiers El We need to understand the following 3 variablelist predicate7 o predicatez V variablelist predicatej o predicate El Natural language meaning is pretty obvious El How can we get rid of the parentheses i We looked at quantifier equivalence remember El That is what this is University arVireinie Negation Of Quantifiers ii Existential Such That ForWhich 3 valiabeiisll predicate v valiabeiisl qpledicale 3 variabeiisl j piedcalm predicate v valiabeiisl j pied05291 wredrcalez El Universal Such That 1 valiabeiisl predicate 39 H Is The Case mi 3 variabeiisl qpledicale 1 valiabeiisl j piedGala predicate 3 variabeiisl j medicare ipamaze m Mae E en mi mi 5 University er Virginia Vacuous Truth Of V El Universal quanti er is only meaningful ifquanti cation is ver a nonempty set El Consider negation there exists an element that does not havet e property El If set is empty this is false so original predicate must be ytrue El Example I Original in myicompulers j app8X Negation COOX VX myicompulers j app9x cooX Rewriting El x myicompulers j app9x acoox epemnigwmmmi 5 University arVireinie Universal Conditional Statement El Recall general form of universal quantifier V variabeist predicate o predicate2 I This looks a lot like a conditional statement V variablelist if predicate then predicate2 El It is in fact the Universal Conditional Statement UnivErSitV at Virginia Starting Point El Universal conditional statement V variabeist predicate o predicate2 El An example V x mycomputers laptopx o IBMX For all ofthe computers that l have ifthe computeris a laptop then it is an IBM Thinkpad Universitv at Virginia Recall Conditional Statement nndmunai in vers e CEnverse Ou ntgar pDSitive p a an an IHEI 313 A 3 T T F F T T T T T F F T 39F T T 39 F F T T F T F F T F F T T T T T T El These look like they might apply to universal conditional statements UnivErSiW urwamia Contrapositive Converse Inverse n Contrapositive V variablelist apredicatez o apredicate E g V x myicomputers T BWx aptopbx n Converse V variablelist predicate o predicate Eg Vx myicomputerSTBWx apt0px Such That El Inverse ltls The Case That V variablelist apredicate o apredicatez E g VX myicomputers T aptomx BM x m Universit i urwamia Multiple Quantifiers El A quanti ed statement is just a predicate 1 So quanti ed statements can be combined in more complex statements 1 Have to be a little bit care Jl to be sure we know what we mean 1 Have to be a little bit care Jl to make sure that we understand what is happening with bound variables 1 Some combinations ofquanti ers tend to be very common W a Wme n Universitv DfVirQinia Important Cases in Universal and existential quantifier V variable re catev Ie variablez El Exam ple V xmycomputers 3 aMACaddro uniquex a n Existential and universal quantifier 3 variable V variable 0 predicatevariable variablez in Example 3 pprinter V xmycomputers o printonx p w x1 magenmwwm University DfVirginia Languages Grammars And Finite State Automata a Jahh c KnightZDDE a All hart reserved rm sue mm 9 mquot mmmue University er Vlrglnla Specification Problems El Need to be able to specifydefine languages El Valid input sequences for programs I Eg Calculator program keystrokes El Formats for records in files I Eg Bank account information El Data sequences in networks I Eg IP and TCP El Menu trees I Eg Windows Specification Problems El Usefulimportant sequences of characters I Eg Passwords or names El Programming languages I Eg Java Ada LISP El Remember formal speci cation of programming languages El Solution Phrase Structured Grammars Phrase Structured Grammars n A phrase structured grammar G is a fourtuple V T S Pwhere I y lsthe Vocabulary I T l5 the set or Terminals I 8 l5 the start symbol I P l5 the set ofProductions n T is a subset ofV u The set V T is the set N the Nonterminals n Productions are literally the way in which one string can replace or produce another a Language ofG is all strings derivable from S Example Rosen av abABS EIT ab IN AB IS EIP SHABa AgtBB Baab ABHb LHS can be replaced by RHS El Strings include I ha abababa I Others How odd Types Of Languages El Types distinguished by the form of the productions in the languages that generate them El Classification introduced by Chomski El Type 0 El Type 1 Contextsensitive languages El Type 2 Contextfree languages I Productions LHS A Le single nonterminal El Type Regular languages I Productions LHS A HS a or aB where A and B are nonterminals and a is a terminal Derivation Tree sexes a b UwZAlt ab El More commonly referred to as a parse tree Really Cool Things s l l AB 5 57gtAEla Aeaa Bead Aged B B B l l l ab ab ii Recursive productions A ii BackusNaur Form BNF l structure notation used to denne contextrnee grammars l Completely fennel easyto read precise l Standard Way that tne syntax ofprogrammlrig languages are denned D You can use all this to define languages that matter to ou eg communications protocols between programs or bits of programs you are writing Java CF Grammar In BNF statement variable declaratlunl x resslu E l quotb ak39 identifier quotcontinuequot identifier Java CF Grammar In BNF whileisbatement quotwhilequot quotquot expression quotquot statement ifstatem ent expre on statement ssi elsequot statement Quick Bits Of Notation n x aka the Kleene star or closure means the set of elements with zero or more x s l e g e m a a aaa aaaa aaaaa n x means the set ofelements with one or more x s l eg aquot a aa aaaaaaa aaaaa ii xm means exactly m x s n x ymeansxory I eg a l b x can be a set in which case the result is concatenation of set elements I e g a b ll a b a ab bb aaa aab aba baa abb bab bba Quick Bits of Notation El This ideas are used to specify regular languages I a b CV I Examples include a aa bccc abcabc aaccbbb I a b I Examples include a a aaabbb abbbbb aaaaab El Regular languages occur all the time Language Recognizers u Need programs to answer the question Is this input string 8 a sentence in the language de ned by G u Examples I Prdeessing any input speeitied bya grammar D How could we build a recognizer u Unwevs Wand F And Now for Something Completely Different Or Is It i mm Wand SpeCIfIcatIon Problem u Need tei speeity and analyze systems sden as mamas I oeiiteiennanes I ELMEIVVS un digital watenes I Vendi ainaenines H mm systems are rererred tei as reactive U Need tn define state than ES I Slate enanae depends an input ate enanae depends un euiient sale to a I St U Need nite state au mat i Unwevs Wand Finite State Auto mata u A nitestate automaton is a vetuple I i set at symbuis tne input alphabet Literally the set ofinput symbols I s A set at states that it can be i I 5D A designated initialstate I A A set at designated states eaiied tine a epting states I N Tine nextstatefunctiunNSxes i mm Wand Example Vending Machine u Based on Epp page 746 but simpler ii Unwevs Wand Example Vending Machine u Based on Epp page 746 but simpler i mm Wand Example Parity Checking El Example strings I 1010101010 I 1100110010 This looks awfully like a recognizer for strings in a Ianguag Language Recognizers ii iltieene s theorem The set oflanguages defined by type 3 regular grammars is identical to the set of languages accepted by finitestate automata Thus forariy regularlariguage there is a rinite state automaton that recognizes it n gt 2 9 I The set of languages defined by type 2 context free grammars is identical to the set oflanguages accepted by pusndown automata ii Thus forariy contextnfree language there is a pushdowri automaton that recognizes it i A pushdown automaton is a finite state automaton supplemented With a pushdowri stack El Really cool thing given a contextfree or regular Iang a 9 there are programs parser generators that wi build the automaton for us Specification Of Reactive Systems El Reactive systems are systems that do things to the operating environment based on their input El 80 a microwave oven controller is a reactive system it can turn on the oven El Can we specify these in Z El Are there better ways i How does discrete math fit in El Are there specialcustom languages for this I Yes Statecharts Statecharts li Developed for specifying reactive systems El Graphic Overall its VERY clever stuff El First introduced in mid 1980 s El Developed by David Harel at the Weizmann Institute El Original application was avionics for Lavi fighter Israeli Aircraft Industries Statecharts El Very Popular In US Industry Most Used Formal Technique El Supported By Powerful Toolset Statemate iLogix Inc El Adapted By Other Notations Eg RSML El Incorporated Wholesale Into Others Eg UML l Many Extensions Developed Part of Harel s Stopwatch i Miami Mama llgh V v quotEmmi Graph Theory Jahn lt2 mm zone 7 m mm reserved dummy 1 word Topics El Terminology lots of It El Real graphs are BIG applications requir Frndrng patns Colleetrng rnrorrnatron El Representing graphs hmmm tricky Adlaeenev rnatnx Adlaeenev nst El Simple application Travenng salespersun Route plannrng Transport svstern desrgn mm Worm The Internet A Graph ww w thesw izk Waggonmm html Unwevs Mqumu Maps o For Lus Angeles try aorldmg a road map Checking correctness otmap deposeer map I Remembe prewavsreos Tramengms orrdgeswnwegm Rallwaycmssmgs o ans is a grapn wrtn tvpreal appneatrons o Frndrng a route rrorn one loeatron to anotner o Desrgnrng a set orpos rootes Begin nlngs El Kaliningrad Russia nee Konigsberg Prussia Drvrded lntu roorseetons Seven pndges aerosstne Pregel nverauowed passage arnongsttne sectluns Town leaders wanted a parade arne e El Stanand end atthe pornt rossrng each ondge onee Held a contest to deterrnrne a solutron Unwevs Mqumu Beg in nings El Euler solved the problem in the negative El There is no solution meeting the constraints El Reduced problem to questions about graphs Can we a e a erreorttnatoses every Edge Can we nave a srrnple erreort rrtnere rs a vertex wrtn an odd nornper of edges Graph Model mm atwminu Solution El Consider an arbitrary node El Visiting the node in a path requires traversing one edge to arrive and one edge to leave El To visit times without traversing an edge twice requires 2iedges incident on the node El Thus the desired path is impossible if a node has an odd number of edges El In the Konigsberg bridges example all of the nodes have an odd number of incident edges NV lVV V 7 Terminology El Graph G V E M I V non empty set of vertices I E set ofunordered pairs ofelements ofV call edges 1 Graph G V E is a simple graph iff I E is a set of distinct edges 1 Graph G V E is a multigraph iff I E is a multiset nota set ie edges are not necessarily distinct NV lVV V a Terminology El Is the Konigsberg graph a simple graph or a multigraph El Do you want your communication network to be a simple graph 0 Vertices a b c d a o Edges db C Terminology El A multigraph graph G V E is a pseudograph iff I E is a multiset with edges ofform u ufor some u E V I Edge u u is a loop 1 A directed graph G V E M I V nonempty set of vertices I E set of ordered pairs of elements ofV call edges El A directed graph G V E is a directed multigraph iff I E is a multiset where loop edges are permitted NV M V V m Terminology El Directed Acyclic Graph DAG is I Agraph I that is directed I and has no cycles El DAGs are pretty common and important NV M V V M Terminology El Two vertices u and v in an undirected graph are adjacent if there is an edge e of form u v or v u in I Edge e is incident to u and v I Edge e connects u and v I Vertices u and v are the endpoints ofedge e i The degree of a vertex v in an undirected graph is the number of edges incident to it I degv degree of vertex v El A vertex v is isolated iff degv 0 El A vertex v is pendant iff degv 1 WV M V V 2 Handshaking Theorem El Theorem I lfG V E be an undirected graph with n vertices and e edges then 2e ZVEv degv El Proof I Every edge contributes 2 to the sum ofdegrees I Every edge is incident to 2 vertices a Oddness Theorem El Theorem I Every undirected graph has an even number ofvertices of odd degree El Proof I Sum of degv is always even 2e Handshaking Thm I Sum of degv of even degree vertices is even I Therefore sum of odd degree vertices mustalso be even I An odd number ofodd numbers produces an odd sum I Therefore there must be even number ofodd numbers to produce an even sum km W V m 4 o n 4 e 7 d b degv 3 3 3 5 o Sumdegs142xe Terminology El If u v is an edge in directed graph G V E then I u is adjacentto v and v is adjacent from u I u is the initialvertex ofedge u v I v is the terminalvertex of edge u v a o a adjacent to b d d b 0 3 initial vertex of a b o b is the terminal vertex of a b C Terminology El The indegree of a vertex v in a directed graph is the number of edges with v as their terminal vertex I deg v indegree ofvertex v El The outdegree of a vertex v in a directed graph is the number of edges with v as their initial vertex I degv outdegree ofvertex v km W V m a Degree Theorem El Theorem I If G V E be a directed graph with n vertices and e edges then e Eva degm ZN mm 1 Proof I Every edge counts 1 to the in degree of some vertex I Every edge counts 1 to the outdegree of some vertex km W V m 7 Complete Graphs El An undirected graph G V E with n vertices and e edges is complete iff I There is an edge between every pair ofdistinct vertices El A complete graph on n vertices is denoted Kn o 0 IE Every Node Is Connected To Every Other Node Mn m E Complete Graphs ii Theorem I A complete graph G V E with n vertices and e edges has nn12 edges ii Proof by induction I Base case n 1 edges 0 I Induction case a Assume cornpiete graph With n vertices has ririri2 edges n Then edges or cornpiete graph With ni vertices is ririri2 h because nis node connected to othern nodes With n edges ririri2 n nin2 OED an in c m 19 Cycle Graphs i A graph G V E with n vertices and n edges is a cycle graph if V is of the form v v2 V where I v VM is an edge in E for1 gi lt n I vn v is an edge in E an in c M 2m Bipartite Graphs i A simple graph G V E is bipartite iff I V can be partitioned into disjoint nonempty sets V and V2 such that a v v L V2 a Forariy edge e Ll v in v One mid and v is in v arid aneuruandwsinv2 ii Separate observation Cycle graphs With an even numberof edges are bipartite an in c m 2i Connectivity i A walk connecting vertices u to v of a graph G V E is a sequence of n edges e1 e2 er such that Ie1 u x for somex in V Ien y v for some y in V IForall i 1 ltilt n i Let e a b and eM 2 cl ua bcanddare in V uvandbc an in c m 22 Connectivity i A path is a walk with no repeated edge in A simple path is a path with no repeated vertex i A circuit or cycle is a path connecting u to u i A simple circuit is a circuit with no vertex repeated except the first and last an in c m 23 Connectivity i A graph is connected if there is a path between every pair of distinct vertices of the graph an in c m 24 Connectivity El Theorem I There is simple path between every pa vertices ofa connected undirected graph El Proof by contradiction I Suppose there is no simple path between a pair of nodes u and v in a connected undirected graph I By de nition there is a path between u and v I No simple path so there is a repeated vertex r I Then path has a cycle I Modify path to remove cycle path becomes simple I Hence there is a simple path from u to v contradiction VrV V V V 25 Connectivity El A graph that is not connected is union of two or more connected subgraphs I The disjoint subgraphs are its connected components El A directed graph G V E is strongly connected if there is path from a to b and b to a for all distinct vertices a and b in V El An Eulerpath for graph G V E is a simple path containing every edge in E El An Euler circuitfor graph G V E is a simple circuit containing every edge in E VrV V V V za Subgraphs El Graph H W F is a subgraph of G V E iff I W is a subset ofV I F is a subset of E Graph Subgraph Subgraph VrV V V V 27 Adjacency Matrix El The adjacency matrixA of graph G V E is a 01 n X n matrix where I Ai k 1 ifv vK is an edge in G Ai k o if v vK a b c d a b Am0111 R D 1010 eStructure U 1100 C U 1000 VrV V V V 2a Isomorphism El Graphs G1 V E and G2 V2 E2 are isomorphic iff there is a bijection f from V to V2 that preserves adjacency I u and v are adjacent if V1 ifffu and fv are adjacent in V2 in Bijection injection and surjection 2 onetOOne and onto v39 quot 39 c a xxf r x Fun Fact El LetA be the adjacency matrix for graph G V E El Let Al A El Le tAw Ak A El Theorem A39i m number ofdifferent paths using r edges from v to vm El Proof I Le to interested student VrV V V V cm Hamiltonian Cycle I A simple circuit is a Hamiltonian cycle ifthe number of edges in the circuit is n where n is the number of vertices in the associated graph I Fastest known algorithm for determining whether a graph has a Hamiltonian cycle takes exponential time with respect to the number of vertices a J 4 I a 4 Graph ThermZEUS Juhri Knight 3i Universit of Virginia Weighted Graphs El A graph G V E is a weighted graph if there exists a function do such du v is the weight of edge u v in G I Sometimes refer to du v as the length of edge u v or the direct distance from u to v I The length ofa path e1 e2 ek is the sum of de1 de2 dek I The weight of a subgraph H W F of weighted graph G V E is the sum of the edge weights in I Why would weight be useful Graph ThermZEUS Juhri Knight 32 Ui iivei sit of Virginia Travelling Salesman Problem i Given a number of cities and the costs of traveling from any city to any other city what is the leastcost roundtrip route that visits each city exactly once and then returns to the starting city I Really important problem for I UPS Federal Express USPS I Any transport delivery system I Cost distance because more fuel is used GraphTthn a W inhn Kninhii 33 Universit oHirginia Easy GraphTthn rm rim inhn Kninhii 34 Universit of Virginia Hard 5 El From hit WWW eocities comharve hima e obecl ra i740 if GraphTthn a W inhn Kninhii 35 Universit oHirginia Almost lm sible Analysis More AnalySIs u Rerhhge Hamiltunlan path a path if a EunnEEtEd graph thatvlslts eaeh y rtex Exactly ghee Hamilluman cycle a Hamilluman path that ends where it s1aned u The trayehhg Salesman prubl rh isthustu hhg the least Eig Hamiltuman path cycle h a EunnEEtEd Weighted graph El This problem is NPcom lete Meaning there is hp hhuvyh Efficient sulutlun Justtu try eyery pussible path El But there are ways to get a somewhat ef cient solution Heuristic n The size at the sulutlun spaee is mm m ansil san ow algumhm ltju trnight hptpe the must errreeht El What39s the usually least expensive way to get between two U cities pmzums Etmts Ahg isthat Significantly sluWErthan the best aigurrthrh7 Unwevs Wm mm Warm The Record Spanning Tree n http eh Wikigedia urgWikiTraveling Salesman El In April 2006 a computer cluster computed a path of 85900 cities visited in 136 CPU years El Suppose you are going to build a transport system Prubably 3 E rhu Wall time fmties V ii We aircurridurs euhheetrhg cities 85mm a B1 mmm El Trains buses or aircraft between cItIes El Assume you can compute 1 million paths each n Wh39Ch quotquotks do you many 5939 ahhut use a cumplete graph second eah ehahge at hheetruh pulnts That Wuuldtake 3 D4 T mmwyearsi El Want to mInImIze number of links used They used acceleratiuntechniques ubymusly El Any solutIon Is a tre Unwevs Mqumu mm atwmimz Spanning Tree Spanning Tree ning tree ofa graph G is a subgraph of G that contains everyverlex ofG and is a tree El Any connected graph has a spanning tree El Anytwo spanning trees ofa graph have the same number of nodes El Construct a spanning tree tart ith the graph Remuye ah Edge rrprh eaeh eye What remains has the same set TEE he at yemees but is a Wth m wow i w l E U I w mm atwmimz Spanning Tree 0 Graph Spanning Trees yw My y 43 Minimal Spanning Tree El Spanning trees are simple El But suppose edges have weights I Cost associated with the edge I Miles for a transport link for example El Spanning trees each have a different total weight El Minimalweigh Spanning Tree Spanning tree with the minimal total weight My My y 44 Minimum Spanning Trees El Given an undirected graph GVE find a graph G V E such that I E is a subset of E I IE I M 1 I G is connected I Zcujs minimal uVEE G is a minimal spanning tree Applications wiring a house cable TV lines power grids Internet connections My My y 45 Generic Minimum Spanning Tree Algorithm KnovmVertices H while KnovmVertices does not form a spanning tree loop nd edg uv that is safe for KnovmVertices Knoan 39 es eKnovmVertices U uv end loop My My y 46 Prim s algorithm Idea Grow a tree by adding an edge from the known vertices to the unknown vertices Pick the edge with the smallest weight known G My M y y 47 Prim s Algorithm for MST El Pick one node as the root El Incrementally add edges that connect a new vertex to the tree 1 Pick the edge uv where I u is in the tree v is not AND I where the edge weight is the smallest ofall edges ot where u is in the tree and v is n My My y 45

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.