Discrete Struc CECS 328
Popular in Course
Popular in Computer Science and Engineering
This 38 page Class Notes was uploaded by Zackary Cronin on Monday October 5, 2015. The Class Notes belongs to CECS 328 at California State University - Long Beach taught by Todd Ebert in Fall. Since its upload, it has received 14 views. For similar materials see /class/218747/cecs-328-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 15 Dijkstra s Algorithm In the last lecture it was mentioned that graphs represent a type of space7 in which discrete places are connected to one another via edges One basic question that can be asked about this space is How to nd the shortest path from one place to another For Cartesian space we know the answer involves taking a linear path from point A to point B Moreover7 the distance between these points can be obtained using the Pythagorean Theorem For graphs a different method must be used since in general vertices on a graph are not directly connected by a line Let G V7 E7 0 be a network where c E a PU represents the cost of traversing an edge of the graph Then the cost of the path 61 62 em is de ned as cost 221 CEi Moreover7 the distance d between u and 1 is de ned as the cost of the path which minimizes the above sum Example 1 Let G VEc7 where V 07b767d767f and the edges costs are given by E 1l11073he1bd1le4cd1cf27 61767 17 617133 67f72 Draw the graph and determine the distance of each vertex from vertex 1 A Special Case Unweighted Graphs Let G V7 E be a unweighted graph In other words 66 1 for every edge e E E In this case the distance from vertex u to vertex 1 is the length of the shortest simple path that connects u and 1 Thus we can de ne the distance dav between vertex 1 and any other vertex 1 using the following recursive de nition H Basis step daa 0 Moreover7 let Vb a E0 Inductive step suppose Vk C V has been de ned for some k 2 0 If 1 Z Vk but 1 is adjacent to some vertex in Vk then dav k 1 Moreover7 VH1 is de ned as the union of Vk with all such vertices Theorem 1 The recursive de nition above yields the correct distances from a to any other vertex in G Proof Example 2 Let G V7E7d7 where Va7b767d767f797h and the edges given by E 0757a7ct 5707b7d7b767 579 079 07f d7f7 J39 f7h7 9771 Draw the graph and determine the distance of each vertex from vertex 1 using the above recursive de nition vertex minimum parent minimum parent minimum parent distance distance distance a b c d e f E Stage 1 Stage 2 Stage 3 Implementation of shortest path algorithm for the unweigted case 1 Initialize queue Q and add a to Q 2 Repeat until Q is empty dequeue the next vertex u in Q For all vertices 1 that are adjacent to u and have yet to be added to Q7 add 1 to Q7 and note that o dav dau 1 0 the parent of 1 is u 3 For all vertices 1 which were never added to Q7 dav 00 The above algorithm is an example of performing a breadth rst search on a graph In other words7 the vertices of the graph are examined in the order in which they are reached FIFO Example 3 Show the contents of the queue Q during the execution of the algorithm on the graph of Example 2 Dijkstra7s Algorithm For the unweighted case once a vertex i is reached dai is immediately known In the general case however this is not true For example edge ab may have a cost of 5 while edges a c and c b may each have costs of 1 thus making the distance from a to b S 2 lt 5 Hence during each stage we only have estimated distances which may decrease during later rounds However Dijkstra s algmithm which was discovered in the 1950s makes use of the following key observation at any stage the least estimated distance from a vertex i to a is the exact distance This observation leads to Dijkstra7s Algorithm Dijkstra7s Algorithm 1 Stage 0 daa 0 Let Knowo a be the set of known distances after Stage 0 Update the estimated distances for all vertices adjacent to a Proceed to Stage 1 E0 Stage k 2 1 repeat until either all distances are known or all estimated distances are in nite Let i have the least estimated nite distance of all vertices whoses distances are not yet known Let Know L Knowk U Update all estimated distances for vertices adjacent to 1 Proceed to the next stage Theorem 1 Dijkstra7s Algorithm yields the correct distance from a for every vertex Proof Example 4 Demonstrate Dijkstra7s Algorithm for the graph from Example 1 vertex minimum parent minimum parent minimum parent distance distance distance a b c d e f E Stage 1 Stage 2 Stage 3 vertex minimum parent minimum parent minimum parent distance distance distance a b c d e f E Stage 4 Stage 5 Stage 6 Analysis of Dijkstra7s Algorithm In the worst case each edge needs to be examined at most twice On the other hand the vertices must be kept in a heap so that vertex with least estimated distance can be ef ciently deleted However the fact that the priority values ie estimated distances are being dynamically updated makes the heaps we studied earlier this semester inadequate However there do exist heaps namely Fibonacci heaps which allow for the dynamic updating of priorities in such a way that the worst case complexity of building updating and deleting from the heap is OHM log Therefore the worst case complexity is W log Example 5 For the graph G shown below Use Dijkstras Algorithm to nd the distance of each vertex from vertex 1 vertex minimum parent minimum parent minimum parent distance distance distance a b c d e f Stage 1 Stage 2 Stage 3 vertex minimum parent minimum parent minimum parent distance distance distance a b c d e f Stage 4 Stage 5 Stage 6 Lecture 16 Network Flow Problem Some important practical problems involve nding the most optimal way of sending resources through a network As an example7 consider the problem of nding a route through a street network which minimizes the driving time of a commuter In the previous lecture we witnessed how to solve this problem using Dijkstra7s Algorithm7 assuming that we can model the street network as a weighted graph where the weights of each edge represent the estimated driving time needed to traverse that edge street As a second example7 suppose a computer has a packet of information that it must send through a network There may exist many ways to route the information through the network It may even be possible to distribute the information in parallel7 using all the channels at once7 and then reassembling the packet at the nal destination Network Flow Let G V7 E7 0 571 be a directed network7 where c E a PU determines the capacity of each edge7 s E V is the designated source vertex and t E V is the designated sink vertex A ow for the network is a function f E a PU with the following properties 1 For every e E E7 fe S Ce In other words7 the ow through an edge should not exceed the edges capacity 2 For every vertex 1 let Ev equal the set of edges that end at 1 and E111 the set of edges that start at 1 Then for every intermediate vertex 1 E V 7 at we have f6 Z f6 86E U 56E 39u In other words7 the total ow going into a vertex must equal the total ow going out Note that it is assumed that Es E t 0 Example 1 For the directed network below7 give an example of a ow for this network Network Flow Problem Let G V Ec st be a directed network Find a ow f E a R which maximizes f 6 56E s in other words a ow which represents a maximal amount of resources leaving from source 5 To solve the network ow problem for network G V Ec st we adopt the strategy of de ning an initial ow f and then try to increase f in stages To do this we need to de ne the following structure The augmented network NG f with respect to G and f is the network NGf V Ecst where V s and t are are the same as for G and El 0 are de ned as follows 1 El EU Ef where um E Ef if and only if e mu 6 E and fe gt 0 2 for e E E ce 66 7 fe and for e E Ef ce fe ln passing notice that since fe 3 66 the capacity function 0 is properly de ned since all capacities are nonnegative Example 2 For the network G and ow f of Example 1 draw the augmented network N 63 Theorem Let G VEcst be a network7 f a ow for the network7 and NG7 f the augmented network If Af is a ow for NGf7 then f Af is a ow for G where f Af e is de ned as follows 0 If e um E E7 let ET 117ube the reversal of 6 Then f AME f6 N6 AW Proof The above theorem provides for an algorithm for nding the maximum ow for a network MaxFlow Algorithm H Stage 0 begin with the O ow f0 ie fe 07 for every 6 E E E0 Stage k 2 1 repeat until augmented network NGfk does not possess a path from s to t Form the augmented network NGfk and nd a path p from s to t Let fk1 fk 10 9 return fk if NG7 fk does not possess a path from s to t Example 3 Use the maximum ow algorithm to nd a maximum ow for the network in Example 1 Example 3 Continued Example 4 Use the maximum ow algorithm to nd a maximum ow for the following network Assume the source is 0 and the sink is z a a 1 3 Ex 4 1quot if 1quot 50 D x 5 I D 2 x r G a x i 3 xo 2 Example 4 Continued Lecture 9 B Trees Up to now when thinking about complexity we have neglected to consider the time it takes to load information from memory If the memory happens to be secondary such as a tape or disk drive then the memory access time becomes a factor and in fact the majority of elapsed time will be spent reading from secondary memory Thus if we were to insist that a binary search tree have its nodes stored in secondary memory we would hope for a very short tree so that the number of disk accesses would be kept to a minimum B trees are designed to accomplish this A B Tree of order m is an m ary tree with the following properties H F 9 4 U 6 Example 1 What is the order or the following B tree The value of L l l l all data is stored at leaves all internal nodes store at most m 7 1 keys to direct the search in particular W E 1 m 7 1 key 239 represents the smallest key in subtree 239 1 the root is either a leaf or has between 2 and m children all nonroot internal nodes have between and m children all leaves have the same depth and have between and L children for some L which is proportional to the size of the block of secondary memory that can be read on one read note that this de nition coincides with the Drozdek7s de nition of a B tree l H lb l TlIB i l IE1 quot35 l Example 2 A government agency must process 22000000 tax records Moreover each record contains up to 500 bytes of information The data is stored on a disk for which one block holds 4096 bytes If each record key and location key requires at most 32 bytes design a B tree which will allow ef cient searching of the records If each record is to be retrieved twice how much time is saved by using a B tree instead of a typical binary search tree assuming that a disk read requires between 1 rnillisecond Inserting and deleting data from a B Tree Inserting a data item into a B tree can be done in a way similar to binary search trees The exception occurs when a leaf node already has the maximum number of data items In this case one must recursively move up the tree to nd an appropriate branch to locate the new leaf In most cases7 the new leaf can be a sibling of the full leaf7 assuming the parent does not have the maximum allowable leaves If this is the case7 then one must trace further back to nd an available branch Related Trees 0 B trees similar to B trees except that nodes are required to be at least two thirds full7 as opposed to half full Splits are delayed by distributing keys between a node and its sibling Splits create one new node for every two full nodes This has the effect of keeping the nodes of the tree more densely packed7 and thus having fewer nodes Pre x B trees same as B trees but an attempt is made to keep the keys of the internal nodes as small as possible in size so that more keys may be stored7 and hence each node may have more children 0 Bit Trees pre x B trees whose leaf keys data are replaced by distinction bits D bits These bits represent a way of compressing the data7 so that more data pointers may be stored within a single leaf R Trees similar to B trees7 but searching is based upon the spatial location of the object Thus R trees can be used to look up information about spatial objects The search is based on bounding bOCL CS which are the smallest boxes that contain all the objects that belong to a given subtree of the R tree Other types of binary search trees 0 24 trees B trees of order 4 that have been converted to binary search trees by using both horizontal and vertical pointers horizontal pointers are used to break up nodes with more than one key 0 red black trees nodes of the alternate as red and black Every path from a node to a leaf must contain the same number of black nodes Popular because they can be nonrecursively implemented 0 Treaps each data item is pseudo randomly assigned a priority7 which determines its location in the tree 0 k 7 d trees each node has a k 7 tuple of keys from different domains The key used depends on the level of the node Lecture 7 Splay Trees Splay trees represent an alternative to AVL trees A splay tree is simply a binary search tree What makes it different however are its operations in the sense that every time an operation is performed on a node eg nd insert and deletion the node is rotated to the top of the tree via a sequence of rotations Some properties and facts of splay trees include splay tree rotations are intended to spread splay the nodes of the tree so that the tree becomes shorter and wider Thus any node that is accessed and occurs deep in the tree will move to the top and cause the tree to spread splay trees do not require height or balance information and thus are easier to imple ment it can be shown using techniques of amortized analysis that any M consecutive oper ations of a splay tree will require 0Mlog 71 steps where n is the tree size Thus the amortized compleaity of a splay tree is Olog using splay trees nodes that are often accessed will reside close to the tree root thus making splay trees very ef cient in practice rotations are necessary since a very unbalanced tree will have a deep node which if never rotated up will stay deep and cause a sequence of nds on this node to produce an 0a amortized complexity SplayTree Rotations The most natural way to rotate a node up to the root7 is to use single AVL rotations7 but this unfortunately does not work in some cases Example 1 Add nodes 1237 and 4 to an initially empty splay tree use single AVL rotations for splaying See what happens after accessing nodes 123A in that order Note the same results can be achieved for arbitrary n7 showing that single AVL rotations are not suf cient for achieving the desired amortized complexity The following two types of tree rotations turn out to be suf cient for achieving an amortized complexity of Olog We will prove this if we have time to study amortized analysis later in the course For now we should try to convince ourselves that these rotations make every node a winner77 in terms of its modi ed distance from the root zigzag rotation zigzig rotation Example 2 Redo Example 1 using the above splay rotations Example 3 Show the result of inserting 64729785711710 into an initially empty splay tree Deleting a node from a splay tree rotate the node to the root and remove it This will leave trees TL and TR TR can be appended as the Child of the root of TL to TL after the maximum node from TL is rotated to the root Example 4 For the tree obtained in Example 37 delete 10 from the tree Lecture 3 Recursive Algorithms lntuitively a recursive algorithm is one which solves a problem by reducing it to an instance of the same problem but with smaller input Like mathematical induction a recursive algorithm has two components 0 base case the case when a problem cannot be reduced any further In this case the solution to the problem is hard coded into the program 0 inductive case the case when a problem can be reduced to the same problem but of smaller input In this case the program calls itself using the smaller input value as input Example 1 Write a recursive algorithm for linear search Example 2 Write a recursive algorithm for binary search Example 3 Write a recursive algorithm for computing aquot7 assuming that n is a nonnegative integer Similar to a recursive algorithm and mathematical induction7 a recursive function de nition is one which has two components 0 basis step f0 is de ned 0 inductive step fn 1 is de ned in terms of fn7 fn 71f0 Note that a recursive de nition may also be used for sets and other families of objects Example 4 Give a recursive de nition for the function fn n2 Example 5 Give a recursive de nition for the operation 57 which represents the reversal of binary string 5 Trees A rooted tree T is a triple T V Er where V is the set of vertices or nodes of the tree E is a set of ordered pairs of vertices called edges which are of the form um where u is called the parent of 1 and 1 the child of u and r E V is called the root of the tree Moreover the following recursive de nition gives the set of legally de ned trees 0 basis step T r 0 r is a legal tree It consists of one root node and zero edges 0 inductive step Suppose that T1 V1E1r1 Tk VkEkrk are legal trees then if r is a node not occurring in any of the k trees TWUUVkUrE1UUEkUTn1gig n is a legal tree A tree formed Via the inductive step with r root7 and k 10 Each triangle Tl represents a distinct legal tree Tree De nitions Let T V Er be a tree The size of a tree denotes the number of nodes of the tree For 1 E V parentv denotes the unique u E V such that um E E Note that parentr is unde ned but is de ned for every other node For u E V childrenm vuv E leaf any node n for which childrenm Q A node that is neither a leaf nor the root is called an internal node For 1 E V sibling v ulparentvu E E A path P of length k from u to 1 is a sequence of nodes u 110111 1 1 such that either chill1 E E or UHhM E E for every 239 E 0 k 71 For 1 E V dept11 length of the path from r to 1 For 1 E V heigh v length of longest path from 1 to a leaf of T The height of T is de ned as hazy11W T is called m ary iff V1 6 V chz39ldrenQM S m T is called binary iff the property holds for m 2 If T is m ary then it is called full iff every internal node has exactly m children It is called perfect if it is full and every leaf of T has the same depth If T is binary then it is called complete iff the following function f V a N has a range of 12 Vl H basis step fr 1 D inductive step suppose fv has been de ned lf 1 has one child 01 then fc 2f1 lf 1 has a second child 02 then fc 2fv 1 note we may assume that each childreno set is ordered Example 6 Given T V7E7r and 1 6 V7 give recursive de nitions for the sets ancest0rv and descendan v Example 7 Given the tree T shown below7 answer the following 1 What is the size of T 2 Find ancestmfo and descendantd 3 Find dept11 and the height of T 4 Find childrenUJ and siblingsm 5 Give the path from m to n 6 ls T full7 cornplete7 or perfect Tree Theorems 1 A tree of size n has n 7 1 edges 2 Every tree is acyclic and connected 3 A perfect m ary tree of depth k has mk1 7 1 nodes Proofs of parts 1 and 2 Interconnections between math induction recursive algorithms de nitions and trees In some sense these three ideas represent different sides of the same cube The following statements illustrate this properties of recursive algorithms7 or objects such as trees that are de ned recursively can often be proved using mathematical induction when evaluating a recursive algorithm or function7 a computation tree is implicitly formed 0 Trees can be de ned recursively o Recursion represents the most succinct way to write an algorithm that operates on a tree Example 8 The bonacci sequence f07 f1 7f is de ned recursively as 0 basis step f0 07 f1 1 o inductive step fn fn1 fn727 for n 2 2 Show the computation tree associated with computing f4 when using the recursive de nition Recurrence Relations The equation fn fn1fn2 from Example 8 is an example of what is called a recurrence relation Any sequence which satisi es a recurrence relation is called a solution of the recurrence relation Moreover7 many recurrence relations can be solved7 in the sense that a closed form solution to the relation can be found A linear homogeneous recurrence relation of degree k With constant coe icients is a recurrence relation of the form an Clanil i C2an72 i i Ckanikv where 0102 ch are real numbers and ck 31 0 Such a relation has a corresponding characteristic equation rk clrk l Cgrk z ck Solving linear homogeneous recurrence relation of degree k With constant coef cients if the characteristic equation rk clrk l Cgrk z ck has It roots r1773 7 with mulitplicities 77117712 mt respectively7 so that m1 mg mt k then the sequence can is a solution of the recurrence relation an Clanil 02an72 Ckanik if and only if an 0410 1171 arm nml l 0420 2171 azm nm l g 040 awn anmtilnmrlhi where am are constants for 1 S 239 S t and 0 S j 3 ml 7 1 10 Example 9 Find a closed form solution for the Fibonacci sequence using the above result A linear nonhomogeneous recurrence relation of degree k With constant coe i cients is a recurrence relation of the form an Clanil 020n72 Ckanik Fn7 where 0102 ck are real nurnbers7 ck 31 07 and is some function Solving linear nonhomogeneous recurrence relation of degree k With constant coe icients First solve the corresponding hornogeneous relation and add the solution to a particular solution of the nonhornogeneous relation Example 10 The following recursive program can be used for computing the n th Fibonacci number f Give the time complexity of this algorithm int Fibint n if n lt 0 return 0 else ifn 1 return 1 else return Fibn 1 Fibn 2
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'