Discrete Struc CECS 228
Popular in Course
Popular in Computer Science and Engineering
This 16 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 Staff in Fall. Since its upload, it has received 105 views. For similar materials see /class/218758/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
DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H Rosen Chapter 4 Counting Enumeration the counting of objects with certain properties is an important concept involved in solving a large number of problems For example counting is used to determine whether there are enough telephone numbers IP addresses or automobile license plate numbers to meet demand It is also used in studying the complexity of algorithms as well as the probability of events 41 Basic Counting Principles The sum rule If a first task can be done in n1 ways and a second task in n2 ways and if only one of these tasks can be done but not both then there are n1 n2 ways to do either task Phrased in terms of sets If a first task is to choose an element from set S and a second task is to choose an element from set T and S and T are two disjoint finite sets then the number of ways to choose an element from either set is S U T S T The product rule Suppose that a procedure can be broken down into two tasks If there are n1 ways to do the first task and n2 ways to do the second after the first task has been done then there are 1 111 12 ways to complete the procedure Phrased in terms of sets If a task to choose an element from set S is followed by a second task to choose an element from set and T where both S and T are finite sets then the number of ways to choose the pair of elements isSxTST The inclusionexclusion principle Suppose there are two tasks that can be done in ml and n2 ways respectively and the two tasks can be done at the same time in n3 ways Then the number of ways to do one of the two tasks is n1 In n3 Phrased in terms of sets If a first task is to choose an element from set S and a second task is to choose an element from set T and S and T are two finite sets that may not be disjoint then the number of ways to choose anelementfromeithersetis SUTSTSnT 42 The Pigeonhole Principle The pigeonhole principle If k l or more objects are placed into k boxes then there is at least one box containing two or more of the objects The generalized pigeonhole principle If N objects are placed into k boxes then there is at least one box containing at least l Nk l objects Exercises in 42 43 Permutation and Combinations A permutation of a set of distinct objects is an ordered arrangement of these objects An rpermutation is an ordered arrangement of r elements of a set The number of rpermutations of a set with n distinct elements is Pnr n n1 n2 nr l An rcombination of elements of a set is an unordered selection of r elements from the set Thus an rcombination is simply a subset of a set with r elements The number of rcombinations of a set with n elements where n is a positive integer and r an integer with 0 S r S n is Cn r n rnr Three wellknown identities for rcombinations O Let n and r be nonnegative integers with r S n Then Cn r Cn nr O Let n and r be positive integers with r S n Then Cnlr Cnrl Cnr This identity is known as the Pascal s identity and is the basis of Pascal s triangle O Let n be a positive integer Then Zrdo Cn r 2 The binomial theorem Let x and y be variables and let n be a positive integer Then x y Zrdom 7072 X J Exercises in 43 DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H Rosen Chapter 7 Relations 71 73 amp part of 72 Relations their representation and Their Properties A binary relation from a set A to a set B is a subset of A x B which can be represented by a set of ordered pairs a zeroone matrix or a directed graph digraph see also Section 73 A relation can be used to express a onetomany relationship between the elements of sets A and B 6g student and classes taken while a function represents a relation where exactly one element of B is related to each element of A eg student and age A relation on a set A is a relation from A to A Annary relation onn sets A1 A2 An is a subset ofA1 x A2 x x An The sets A1 A2 An are called the domains of the relation and n is called its degree Application in databases O The projection Pi1 i2 im maps the n tuple al a2 an to the mtuple ai1 ai2 aim where m S n See Tables 3 and 4 for example O The join operation is used to combine two tables into one when these tables share some identical fields It is often used in airline ights databases and class schedules databases See Tables 5 6 and 7 for example Properties of relations O R is re exive if a a e R for each element a e A O R is symmetric if b a e R whenever a b e R for a b e A O R is antisymmetric if a b e R and b a e R only ifa b for a b e A O R is transitive if whenever a b e R and b c e R then a c e R for a b c e A The composite of relations R and S denoted by S R is the relation consisting of ordered pairs a c where a e A c e C and b e B such that a b e R and b c e S The powers R n l 2 are defined recursively as R1 R and R 1 Rn R Exercises 75 Equivalence Relations A relation on a set A is called an equivalence relation if it is re exive symmetric and transitive Some examples of equivalence relations I Grouping of students according to certain criteria I Congruence modulo m Given a relation R on a set A Then the set of all elements b e A such that b R a is called the equivalence class of a denoted by aR An element b e aR is called a representative of this equivalence class An equivalence relation on a set A partitions A into equivalence classes which are disjoint and nonempty subsets of A Exercises in 75 76 Partial Ordering A relation R on a set A is called a partial ordering or partial order if it is re exive antisymmetric and transitive A R is called a partially ordered set or poset Some examples of posets 39 Z 2 39 Z I Two elements a and b of a poset A lt are comparable if either a lt b or b lt a They are incomparable if a lt b and b lt a If A lt is a poset and every two elements of A are comparable then A is called a totally ordered or linearly ordered set and lt is called a total order or a linear order A totally ordered set is also called a chain E g Z 2 is totally ordered A lexicographic ordering is a partial ordering defined on a Cartesian product of n posets as follows One n tuple is less than a second ntuple if the entry of the first n tuple in the first position where the two ntuples disagree is less than the entry in that position in the second ntuple A poset may be represented by a digraph A Hasse diagram is a digraph that represents a poset with the following changes Removal of all the loops 2 Removal of all transitive edges 3 Repositioning of the digraph so that each edge has its initial vertex below its terminal vertex 4 Removal of all the arrows on the directed edges A total ordering lt is said to be compatible with the partial ordering R if a lt b whenever a R b Topological sorting constructs a compatible total ordering from a partial ordering i Topological Sorting Algorithm procedure topological sort S finite poset While S 7393 Q begin ak a minimal element of S such an element must exist by Lemma 1 S IZS ak k k 1 end a1 a2 an is a compatible total ordering ofS D Exercises in 76 Examples 2106 Compound Propositions and its application Translation into Logical Expression Q How can this English sentence be translated into logical expression Access is granted whenever the user has paid the subscription fee and enters a valid password Hint part the sentence assign propositional variables and then determine logical connectives Compound Propositions and its application System Specifications Q Are these system specifications consistent The system is in multiuser state if and only if it is operating normally If the system is operating normally the kernel is functioning The kernel is not functioning or the system is in interrupt mode If the system is not in multiuser state then it is in interrupt mode The system is not in interrupt mode Hint Do the same steps as in the previous example and then find if all the logical statements can be true at the same time DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H Rosen Chapter 2 The Fundamentals Algorithms and the Integers 21 Algorithms An algorithm is a definite procedure for solving a problem using a finite number of steps Common properties of algorithms 0 Input An algorithm has input values from a specified set Output From each set of input the algorithm produces output values from a specified set De niteness The steps of an algorithm must be defined precisely Correctness An algorithm should produce the correct output after a finite number of steps for any input Finiteness An algorithm should produce the desired output after a nite number of steps for any input in the set Effectiveness Each step of an algorithm must be executable exactly and in a nite amount of time Generality The procedure should be applicable for all problems of the desired form not just for a particular set of input values A problem that aims to find a solution that either minimizes or maximizes the values of some parameter is an optimization problem An algorithm for solving an optimization problem that makes what seems to be the best choice at each step is called a greedy algorithm Examples of Algorithms Algorithm 1 p 122 Finding the Maximum Element in a Finite Sequence Algorithm 2 p 123 The Linear Search Algorithm Algorithm 3 p 124 The Binary Search Algorithm Algorithm 4 p 126 The Bubble Sort Algorithm 5 p 127 The Insertion Sort Algorithm 6 p 128 Greedy ChangeMaking Algorithm Exercises in 21 22 The Growth of Functions The growth of functions is often described using the bigO notation defined as Given f g A gt R where A may be the set of integers or the set of real numbers we say fx is Ogx if El constants C and k such that lfx S C gx whenever x gt k This is sometimes written as fx Ogx though the two functions are not really equal 0 A function fx is said to be bigTheta of gx denoted by gx if and only if fx is Ogx and gx is Ofx In this case we also say fx is of order gx 0 fx is oforder xquot iefx xquot iffx anxquot an1 xquot391 a0 Where a0 an1 an are real numbers with an 7393 0 Exercises 22 23 Complexity of Algorithms There are two important aspects of the computational complexity of an algorithm Time complexity measures the efficiency in terms of the time used by a computer to solve a problem using the algorithm when input values are of a specified size This is usually expressed in terms of the number of basic operations comparisons arithmetic operations etc rather than the actual computer time used Space complexity measures the amount of computer memory required to solve a problem using the algorithm when input values are of a specified size This is usually tied in with the particular data structures used to implement the algorithm Worstcase analysis identifies how many operations an algorithm requires to guarantee that it will produce a solution with input of a specified size Averagecase analysis finds the average number of operations used to solve the problem over all inputs of a given size Examples 0 Algorithm for finding the maximum element in a set n comparisons 0 Linear search algorithm n comparisons o Binary search algorithm log n comparisons Commonly used terminology for complexity of algorithms Table l p148 Comparison of commonly referenced time complexities Table 2 p150 Exercises in 23 24 The Integers and Division Some basic de nitions 0 Given integers a and b with a 7k 0 Suppose El integer c st b ac we say that a divides b denoted by a b and that a is afactor of b and b a multiple ofa A positive integer p gt 1 is called prime if the only positive factors of p are l and p A positive integer gt 1 that is not prime is called composite Every integer a when divided by a positive integer d can be expressed uniquely in terms of a quotient q and a remainder r with 0 S r lt d as a dq r We call d the divisor a the dividend q the quotient and r the remainder Given integers a and b not both zero The greatest common divisor of a and b denoted by gcda b is the largest integer d st d a and d b Two integers a and b are relatively prime if gcda b 1 Given positive integers a and b The least common multiple of a and b denoted by lcma b is the smallest positive integer d st a d and b d Given two integers a and b and a positive integer m Then a is congruent to b modulo m denoted by a E b mod m ifm a b Important theorems in integer arithmetic 0 Every positive integer can be written uniquely as the product of primes Know as the Fundamental Theorem of Arithmetic o If n is a composite integer then n has a prime divisor S l n Let a be an integer and d a positive integer Then there are unique integers q and r with 0 S r lt d st a dq r Known as the Division Algorithm Note this is really a theorem NOT an algorithm despite its name The Euclidean Algorithm that finds the gcd of two given integers was developed based on this theorem and a well known lemma that says quotGiven a bq r where a b q amp r are integers Then gcda b gcdb rquot ALGORITHM l The Eucidean Algorithm p130 procedure gcdab positive integers xa yb While y 7393 0 begin r x mody xy r end gcdab is x Let a and b be positive integers Then ab gcda b lcma b Let a and b be integers and m a positive integer Then a E b mod m iff El integer k st a b km Let a b c d be integers and m a positive integer If a E b mod m and c E d mod m then aCE b dmodmandaCE bdmodm Applications of congruences p AO J Hashing functions A hashing function h assigns memory location hk to the record that has k as its key e g hk E k mod m where m is the table size Pseudorandom numbers Numbers generated by some systematic methods that have the properties of randomly chosen numbers are called pseudorandom numbers eg the linear congruential method will generate a sequence x0 x1 xn successively using x M axn 0 mod m where m is called the modulus a the multiplier c the increment and x0 the seed with 23altm OScltm and 0 xoltm Cryptology The study of secret messages e g The shift czpher p pk mod 26 will shift each letter in a text by k thereby making the text unreadable at least for untrained eyes RSA encryptiondecryption a public key cryptosystem a Translate each letter in a plain text into an integer and group them into blocks to form larger integers b Transform each of the large integerM the original message into an integer C the encrypted message using the function C M mod n where n pq is the product of two large primes p and q and e is relatively prime to plql c Find the inverse d of e mod plql d Decipher each encrypted integer C into M using the function C d M mod pq Exercises in 24 DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H Rosen Chapter 9 Trees 91 Introduction A tree is a connected undirected graph with no simple circuits cycles An undirected graph is a tree iff there is a unique simple path between any two of its vertices A rooted tree is a directed graph constructed from a tree with one vertex designated as a root and each edge directed away from the root In a rooted tree T let u v be a directed edge in T then u is the parent of v and v the child of u39 vertices with the same parents are called siblings the ancestors of a vertex v other than the root are the vertices in the path from the root to v the descendants of a vertex v are those vertices that have v as an ancestor a leaf is a vertex with no children vertices that have children are called internal vertices39 a vertex v together with its descendants and all edges incident to these descendants form a subtree A rooted tree where every internal vertex has S in children is called an mary tree39 it is a binary tree ifm 2 The level of a vertex v in a rooted tree is the length of the unique path from the root to v The height of a rooted tree is the maximum of the levels of vertices A rooted mary tree of height h is called balanced if all leaves are at levels h or hl In an ordered rooted tree the children of each internal vertex are ordered If a vertex has two children the first child is called the left child and the second child is called the right child The tree rooted at the left child is called the left subtree and that rooted at the right child is called the right subtree Trees may be used to model I Saturated hydrocarbons I Organizations I File directories I Interconnection networks for parallel processing Properties of trees I A tree with n vertices has exactly n l edges I A full mary tree with i internal vertices contains n mi 1 vertices I A full mary tree with u n vertices has i n lm internal vertices and l m ln lm leaves a i internal vertices has n m i 1 vertices and l m li 1 leaves a 1 leaves has n ml lm l vertices and i l lm l internal vertices I There are at most mh leaves in an mary tree of height h I If an mary tree of height h has 1 leaves then h 2 l logm l If the mary tree is full and balanced then h l logm l Exercises in 91 92 Applications of Trees Binary search tree an ordered rooted binary tree in which each vertex is labeled with a key that is both larger than the keys of all vertices in its left subtree and smaller than the keys of all vertices in its right subtree O Binary Search Tree Algorithm see Algorithm 1 in 82 Decision tree A rooted tree in which each internal vertex corresponds to a decision with a subtree at these vertices for each possible outcomes of the decision O Example Finding Counterfeit Coin Pre x codes codes based on an encoding scheme where bit strings of different lengths are used to encode letters with the property that the bit string for a letter does not occur as the prefix of any other letter The objective is to save in the overall memory and reduce transmittal time for the coded data O Huffman Coding Algorithm Construct a binary tree recursively given weights wls wzs mg wn as follows 1 Create a tree with subtree rooted at the 2 smallest weights Their combined weights become the weights of the root of this subtree which will be used with the remaining weights for the construction of other branches 2 Repeat step 1 until all weights are combined 3 The 2 branches of each internal vertex are labeled 0 and 1 Each letter gets the path of labels as obtained in the binary tree Exercises in 92 93 Tree Traversal o Preorder traversal results in depthfirst search or backtracking 1 Visit the root 2 Visit the left subtree using preorder 3 Visit the right subtree using preorder 0 Inorder traversal 1 Visit the left subtree using inorder 2 Visit the root 3 Visit the right subtree using inorder o Postorder traversal results in the Reversed Polish Notation when used for algebraic expressions 1 Visit the left subtree using postorder 2 Visit the right subtree using postorder 3 Visit the root Exercises in 93 94 amp 95 Spanning Trees and Minimum Spanning Trees 0 Given a simple graph G a spanning tree of G is a subgraph of G that is a tree containing every vertex of G o A simple graph is connected iff it has a spanning tree 0 A spanning tree for a connected simple graph using I Depth rst search also called backtracking this procedure forms a rooted tree and the underlying undirected graph is a spanning tree Jp A he U 6 Arbitrarily choose a vertex of the graph as the root Form a path starting at this vertex by successively adding edges where each new edge is incident with the last vertex in the path and a vertex not already in the path Continue adding edges to this path as long as possible If the path goes through all vertices of the graph the tree consisting of this path is a spanning tree Otherwise more edges must be added by moving back to the next to last vertex in the path Form a new path starting from this vertex passing through vertices that were not already visited If this cannot be done move back another vertex in the path and try again Repeat this procedure of forming new paths that are as long as possible until no more edges can be added I Breadth rst search this procedure forms a rooted tree and the underlying undirected graph is a spanning tree i J U 4 Arbitrarily choose a vertex of the graph as a root and add all edges incident to this vertex The new vertices added at this stage become the vertices at level 1 in the spanning tree Arbitrarily order them For each vertex at level I visited in order add each edge incident to this vertex to the tree as long as it does not produce a simple circuit Arbitrarily order the children of each vertex at level 1 This produces the vertices at level 2 in the tree Follow the same procedure until all the vertices in the tree have been added 0 A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges I Prim s algorithm constructs a minimum spanning tree from a given connected weighted graph I Prim s algorithm is an example of a greedy algorithm which makes an optimal choice at each of its steps Exercises in 94 and 95 DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H Rosen Chapter 1 The Foundations Logic and Proof Sets and Functions Teaching Goals This course is designed to enable you to understand problems and problem specification in computer science field to design solutions using the knowledge of this course Learning Objectives Chapter 1 Upon successful completion of this chapter you will be able to Model statements and systems using propositional and predicate logic Translate between English sentences and propositionalpredicate logic Determine the consistency of a set of logical statements Solve puzzles from a set of given statements De ne a set and perform set operations Find the Cartesian product of sets and the power set of a given set Represent a set in computer programs and the corresponding operations Recognize wellknown set identities and determine the relationship between two sets equal subset etc Identify when a relationship between two sets represents a function Find the domain and range of a function and determine whether or not it is 11 onto or both Find composite and inverse functions Use special functions including the oor and ceiling functions 11 Logic A proposition is a statement that is either true or false but not both p q r s We confine our attention to declarative sentences to which it is meaningful to assign one and only one of the truth values true or false Assumptions about propositions are 0 Assumption 1 The Law of Excluded Middle For every proposition p either p is true or p is false Assumption 2 The Law of Contradiction For every proposition p it is not the case that p is both true and false Propositional logic is the area of logic that deals with propositions A truth table displays the relationships between the truth values of propositions Logical operators Negation ofp p not p Conjunction of p and q Disjunction of p and q Exclusive or of p and q Implication Biconditional Propositions that are related to an implication p gt q Converse of an implication p gt q Contrapositive of an implication p gt q Inverse of an implication p gt q Compound propositions may be formed using various logical operators Generally accepted precedence of the logical operators from highest to lowest System speci cations are a series of statements that spell out the requirements of the system in question The specifications are said to be consistent if there is an assignment of truth values to the variables in the expressions that makes all the expressions true A Boolean variable is one whose value is either true or false Computer bit operations correspond to logical operations of Boolean variables Bitwise operations are bit operations extended to bit strings Exercises in 11 l 3 7 9131718 21 22 27 28 31 32 33 34 35 41 43 45 47 49 51 53 57 59 12 Propositional Equivalences A compound proposition that is always true is a tautology A compound proposition that is always false is a contradiction A compound proposition that is neither a tautology nor a contradiction is a contingency Compound propositions that always have the same truth value are called logically equivalent denoted by E Example Some well known logical equivalences See Table 5 on p 24 of the textbook Equivalences Name p A T E p Identity laws vaEp p v T E T Domination laws p A F E F p v p E p ldempotent laws P P E P p E p Double negation law p v q E q v p Commutative laws P q E q P p v q v r E p v q v r Associative laws pAqAr E pAqAr p v q A r E p v q A p v r Distributive laws PAqr EpC1Vpr p A q E p v q De Morgan s laws p v q E p A q Logical equivalences involving implications See Table 6 on p 24 of the textbook Logical Equivalences Involving Implications p gtq E Epvq p gtq E Eq Hp pvq E Ep gtq pAq E Ep gtEq Ep gtq E pAEq p gtqAp gtr E p gtqAr perAqer E pvq gtr p gtqvp gtr E p gtqu pervqer E pAq gtr Logical equivalences involving implications See Table 7 on p 24 of the textbook Logical Equivalences Involving Biconditionals qu E p gtqAq gtp qu E EpHEq qu E pAqvEpAEq Ep9q E pHEq Exercises in 12 7 9 ll 15 20 23 25 34 37 41 43 49
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'