This page includes demos of some M-files that were created for Stanoyevitch's book Discrete Structures With Contemporary Applications. All text elements below can be copied and pasted onto the MATLAB or FreeMat command window. Anything after the the comment symbol "%" is ignored by MATLAB/FreeMat so this symbol is used to provide additional information on the syntax (and input/output variables) of some programs. More information about a program called programName can sometimes be obtained by typing "help programName" in the MATLAB command window (in FreeMat one should type "type programName"-- this will display all of the lines of programName; the first few lines (begining with % contain the content of the help). The computer implementation material at the end of most sections in the book contains much more detailed information about the programs and the underlying algorithms, as well as helpful ideas for readers who wish to write their own programs in any computing platform. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Except for Chapters 3, 4, and 6, the M-files and code snippets have been tested to work for MATLAB only. But or Chapters 3, 4 and 6, The M-files are of the following three types: 1. Programs whose names do not end in the suffix "_FM" or "Sym." These programs work on both MATLAB and FreeMat. The outputs should be the same on either platform for given admissible sets of inputs. All of these programs are illustrated in FreeMat. FreeMat will sometimes give some additional warning messages on some of these programs; these can be ignored (and we do not print them below). 2. Programs whose names end in "_FM." This means that the corresponding MATLAB program needed some changes to work in FreeMat. All of these programs are illustrated below in FreeMat. When using MATLAB, the "_FM" suffix should be deleted. 3. Programs whose names end in "Sym." This small collection of programs (placed at the end of the list of Chapter 3 programs) correspond to programs that use MATLAB's symbolic functionality. These will not work in FreeMat, and should be used when working with large integers. As a general rule, integer arithmetic in FreeMat (and in non-symbolic MATLAB calculations) works fine as long as the number of digits in any computed integers gets no larger than 15. This means, for example, when multiplying integers in a certain modulus m, the number of digits of m should be at most 7 or 8. This is usually fine for most of the book's illustrations and homework problems; but for larger (and real-life) cryptographic applications symbolic computations are needed. Such applications and issues are discussed in detail in the appendix to Section 3.3 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ NOTE: In the future, more programs will be added to this site, and eventually all of them will be FreeMat Compatible. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Chapter 1: For this chapter (only) we give some notes on MATLAB's built-in set functions. >> %In MATLAB, sets are stored as vectors: >> S = [1 3 5 7 9 11]; T = [3 6 9 12]; >> %The union and intersection operations have natural syntax: >> intersect(S,T) --> 3 9 >> union(S,T) --> 1 3 5 6 7 9 11 12 >> %In sets, as opposed to vectors, duplicated elements are redundant, and >> %will be eliminated when any set operation is applied, for example: >> union([3 1 3], [2 1 2]) --> 1 2 3 >> %notice also that outputs of set functions are sorted. >> %When working with strings rather than numbers, elements need to be enclosed >> %in single quotes, but outputs are single strings: >> A = ['a' 'c' 'f' 'g' 'k']; B = ['b' 'c' 'j' 'k']; >> intersect(A,B) --> ck >> union(A,B) --> abcfgjk >> %The relative complement of on set in another is done with the "setdiff" command: >> setdiff(S,T) --> 1 5 7 11 >> %The "ismember(x,S)" checks whether an element x belongs to a set S; 0 means false (no) >> %and 1 means true (yes) >> AmB = setdiff(A,B) --> afg >> ismember('f',A) --> 1 >> %The command "isempty(S)" determines whether an inputted set (or array) S is empty. >> %It can be used for many purposes, for example to determine whether a set S is a >> %subset of another set T, we can use the command: isempty(setdiff(T,S)). >> %Example: >> C = [1 2 3]; D = [1 3]; >> isempty(setdiff(C,D)) --> 0 >> isempty(setdiff(D,C)) --> 1 >> %The first computation's output (0 = false) shows that setdiff(C,D) is NOT empty, >> %so that C is not a subset of D, the latter computation's output (1 = true) shows >> %that setdiff(D,C) IS empty, so that D is a subset of C. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Chapter 3: --> PrimeFactors(1245684) 2 2 3 11 9437 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> NextPrime(500) 503 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> [q r] = DivAlg(12353, 108) q = 114 r = 41 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> EuclidAlg(6192546, 1057428) 6 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> EulerPhi(19239) 11440 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> EulerPhiInv(22) 23 46 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> Order(2,101) 100 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> FermatTest_FM(841) Inputted number was proved composite using the Fermat test. Here is a corresponding witness: 17 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> MillerRabinTestEnhanced_FM(9783) Inputted integer was proved composite using the Miller-Rabin test. Here is a corresponding witness: 3503 The corresponding exponent paramters for 2^j*m are [j m]=: 0 4891 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Symbolic Programs (MATLAB Only): >> [d x y] = gcdSym(sym(112123123412345123456),sym(98765432123456789)) d = 16 x = 2173884457375910 y = -2467894991780724431 >> p = sym('1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579'); >> q = sym('1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571'); >> n=p*q n = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609 >> FastExpSym(sym(1345),p,sym(112123123412345123456)) ans = 100519652220422356417 >> ModInvSym(ans,sym(112123123412345123456)) 22719251729985081921 >> FermatTestSym(n, 4) Inputted number was proved composite using the Fermat text. Here is a corresponding witness: a = 2814674387357589089278003868506047400465685457879454124904559036952301872688607472049239239141968681458768482813997417403629891346894020264157297275374132587997380905452018216939719257145263072 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Chapter 4: --> bin2int('1001010') 6170 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> baseb2int([8 3 4 0 1], 9) 55000 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> int2bin(6170) 1 1 0 0 0 0 0 0 1 1 0 1 0 --> int2bin(6170, 15) 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> baseb_add([2 1 0 2 2],[1 0 2],3) 2 1 2 0 1 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> baseb_sub([2 1 2 0 1],[1 0 2],3) 2 1 0 2 2 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> baseb_mult([2 1 2 0 1],[1 0 2],3) 1 0 0 1 0 2 0 2 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> EuclidAlgExt(6192546, 1057428) 6 -14621 85624 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> ModInv(10,251) 226 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> ISBN13Checker([9 7 8 1 4 3 9 8 1 7 6 3],6) No Error detected. --> ISBN13Checker([9 7 8 1 4 3 9 8 1 7 6 3],2) Error Detected: The check digit 6 is different from the last digit 2. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> FastExp(2,2011,15) 8 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ A = 7 5 2 0 6 4 8 2 5 --> MatModInv(A,9) 2 3 4 7 5 4 3 4 3 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> HillCrypt('codebluealert',[1 2; 1 3]) ans = ESLPXICGWHMDTG +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> HillDeCrypt('ESLPXICGWHMDTG',[1 2; 1 3]) ans = codebluealertn +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> HillEncodingMatrixGenerator(3) 10 21 1 13 21 10 16 8 11 --> HillEncodingMatrixGenerator(4) 13 3 11 11 5 8 14 5 18 4 17 20 0 24 13 15 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> DiffieHellmanKey(53,2,5,22) %DiffieHellmanKey(p,g,B,a) 29 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> RSAEncrypt(44,49,1517) %RSAEncrypt(P,e,n) 1069 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> RSADecrypt(1069,529,1517) %RSADecrypt(C,d,n) 44 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> [A, C] = ElGamalEncrypt(44,22,5,53,2) %[A, C] = ElGamalEncrypt(P,a,B,p,g) A = 43 C = 4 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> ElGamalDecrypt(43,4,47,53) %ElGamalDecrypt(A,C,b,p) 44 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> [Bestx BestValue] = KnapsackBruteFindAllBest([3 4 6 8 10 12], 28) %[Bestx BestValue] = KnapsackBruteFindAllBest(Weights, s) Bestx = 0 0 1 0 1 1 0 1 1 1 1 0 BestValue = 28 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> KnapsackSuperIncreasing([1 2 4 9 20 48], 27) %KnapsackSuperIncreasing(Weights, s) 1 1 1 0 1 0 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> PrivateWeights = [1 2 4 9 20 48]; --> PublicWeights = mod(38*PrivateWeights,101) PublicWeights = 38 76 51 39 53 6 --> MerkleHellmanEncrypt(PublicWeights, [0 1 1 1 0 1]) %MerkleHellmanEncrypt(PublicWeights, xPlaintext) 172 --> MerkleHellmanDecrypt(PrivateWeights,101, 38, 172) %MerkleHellmanDecrypt(PrivateWeights,m, w, C) 0 1 1 1 0 1 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Chapter 6: +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ --> RandIntGen(0,1,15) 1 1 1 1 0 1 0 0 1 1 0 1 0 1 --> RandIntGen(0,25,15) ans = 7 18 2 10 2 25 11 8 6 24 2 9 15 20 18 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Chapter 7: --> UnOrderedList = RandIntGen(0,25,15) UnOrderedList = 21 23 3 23 16 2 7 14 24 25 4 25 24 12 20 --> LinearSearch(UnOrderedList,15) 0 --> LinearSearch(UnOrderedList,23) 2 --> List = 3:3:27 List = 3 6 9 12 15 18 21 24 27 --> BinarySearch(List,15) 5 --> BubbleSort(UnOrderedList) 2 3 4 7 14 12 16 20 21 23 23 24 24 25 25 --> ListGenerator(20,0,1) 0 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 --> ListGenerator(10,1,5) 1 4 1 3 1 2 4 1 3 5 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Chapter 8: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for y = GraphSequenceRecursive(DegSeq) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DegSeq = 5*ones(1,50); y = GraphSequenceRecursive(DegSeq) %OUTPUT: y = 1 %Means inputted sequence is graphic %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for y = GraphSequenceShowRecursive(DegSeq) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DegSeq = [7 5 3 3 2 2 2 2 2]; y = GraphSequenceShowRecursive(DegSeq) %OUTPUT: %Initial Sequence: (7, 5, 3, 3, 2, 2, 2, 2, 2) %Iteration #1: (i) (4, 2, 2, 1, 1, 1, 1, 2), (ii) (4, 2, 2, 2, 1, 1, 1, 1) %Iteration #2: (i) (1, 1, 1, 0, 1, 1, 1), (ii) (1, 1, 1, 1, 1, 1, 0) %Iteration #3: (i) (0, 1, 1, 1, 1, 0), (ii) (1, 1, 1, 1, 0, 0) %Iteration #4: (i) (0, 1, 1, 0, 0), (ii) (1, 1, 0, 0, 0) %Iteration #5: (i) (0, 0, 0, 0), (ii) (0, 0, 0, 0) %y = 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for AdjMat = EdgeList2AdjMatrix(EdgeList, n) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.1.9(b) EdgeList = [1 2; 1 3; 2 3; 3 4; 3 5; 4 5]; AdjMat = EdgeList2AdjMatrix(EdgeList, 5) %OUTPUT: %AdjMat = % 0 1 1 0 0 % 1 0 1 0 0 % 1 1 0 1 1 % 0 0 1 0 1 % 0 0 1 1 0 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [Out iso] = IsomorphismChecker(A1, A2) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.1.16(b) %Step 1: Input edge lists for two graphs %Order vertices alphabtically, i.e., %For first graph: a <-> 1, b <-> 2, c <-> 3, d <-> 4 %For second: u <-> 1, v <-> 2, w <-> 3, x <-> 4 EdgeList1 = [1 2; 1 3; 2 3; 2 4; 3 4]; EdgeList2 = [1 3; 1 4; 2 3; 2 4; 3 4]; %Step 2: Use previous program to form corresponding adjacency matrix. AdjMat1 = EdgeList2AdjMatrix(EdgeList1, 4) %OUTPUT: %AdjMat1 = % 0 1 1 0 % 1 0 1 1 % 1 1 0 1 % 0 1 1 0 AdjMat2 = EdgeList2AdjMatrix(EdgeList2, 4) %OUTPUT: %AdjMat2 = % 0 0 1 1 % 0 0 1 1 % 1 1 0 1 % 1 1 1 0 %Step 3: Apply Program [Out iso] = IsomorphismChecker(AdjMat1, AdjMat2) %OUTPUT: Out = 1 %iso = 4 1 2 3 %Comments: The first output (=1) means that the two graphs are isomorphic. %The second output give the (vertex permutation for the) isomorphism: % a <-> x, b <-> u, c <-> v, d <-> w. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for ParentList = ChildrenList2ParentList(ChildrenList) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.3.1(b) ChildrenList = [32 14 54; %root vertex should be placed first 4 12 0; 12 0 0; 14 4 27; 20 0 0; 27 20 0 36 0 0; 47 36 52; 52 0 0; 54 47 88; 88 0 0]; ParentList = ChildrenList2ParentList(ChildrenList) %OUTPUT: %ParentList = % 32 0 % 4 14 % 12 4 % 14 32 % 20 27 % 27 14 % 36 47 % 47 54 % 52 47 % 54 32 % 88 54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for DepthList = ParentList2DepthList(ParentList) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.3.2(b) ParentList = [32 0; 4 14; 12 4; 14 32; 20 27; 27 14; 36 47; 47 54; 52 47; 54 32; 88 54]; %OUTPUT: %DepthList = % 32 0 % 4 2 % 12 3 % 14 1 % 20 3 % 27 2 % 36 3 % 47 2 % 52 3 % 54 1 % 88 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for DescendantList = DescendantFinder(ChildrenList, vertex) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.3.3(b) ChildrenList = [32 14 54; %root vertex should be placed first 4 12 0; 12 0 0; 14 4 27; 20 0 0; 27 20 0 36 0 0; 47 36 52; 52 0 0; 54 47 88; 88 0 0]; DescendantList = DescendantFinder(ChildrenList, 32) %OUTPUT: 14 54 4 27 47 88 12 20 36 52 DescendantList = DescendantFinder(ChildrenList, 14) %OUTPUT: 4 27 12 20 DescendantList = DescendantFinder(ChildrenList, 27) %OUTPUT: 20 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for ChildChildrenLists = ChildTrees(ChildrenList) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.3.5(b) ChildrenList = [32 14 54; %root vertex should be placed first 4 12 0; 12 0 0; 14 4 27; 20 0 0; 27 20 0 36 0 0; 47 36 52; 52 0 0; 54 47 88; 88 0 0]; ChildChildrenLists = ChildTrees(ChildrenList) %OUTPUT: %ChildChildrenLists(:,:,1) = % 14 4 27 % 4 12 0 % 27 20 0 % 12 0 0 % 20 0 0 %ChildChildrenLists(:,:,2) = % 54 47 88 % 47 36 52 % 88 0 0 % 36 0 0 % 52 0 0 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for PreOrder = PreOrderAlg(ChildrenList) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.3.6(b) ChildrenList = [32 14 54; %root vertex should be placed first 4 12 0; 12 0 0; 14 4 27; 20 0 0; 27 20 0 36 0 0; 47 36 52; 52 0 0; 54 47 88; 88 0 0]; PreOrder = PreOrderAlg(ChildrenList) %OUTPUT: 32 14 4 12 27 20 54 47 36 52 88 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for InOrder = InOrderAlg(ChildrenList) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.3.7(b) ChildrenList = [32 14 54; %root vertex should be placed first 4 12 0; 12 0 0; 14 4 27; 20 0 0; 27 20 0 36 0 0; 47 36 52; 52 0 0; 54 47 88; 88 0 0]; InOrder = InOrderAlg(ChildrenList) %OUTPUT: 12 4 14 20 27 32 36 47 52 54 88 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for PostOrder = PostOrderAlg(ChildrenList) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 8.3.8(b) ChildrenList = [32 14 54; %root vertex should be placed first 4 12 0; 12 0 0; 14 4 27; 20 0 0; 27 20 0 36 0 0; 47 36 52; 52 0 0; 54 47 88; 88 0 0]; PostOrder = PostOrderAlg(ChildrenList) %OUTPUT: 12 4 20 27 14 36 52 47 88 54 32 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Chapter 9: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for UnusedEdges = UnusedEdgeFinder(EdgeListG, EdgeListT, BdyEdges) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 9.2.1(b) EdgeListG = [1 2; 1 4; 1 5; 1 7; 2 3; 2 5; 2 6; 3 6; 4 7; 5 7; 5 8; 6 7; 6 8]; EdgeListT = [1 2; 1 4; 2 3; 2 6]; BdyEdges = [1 5; 1 7; 2 5; 4 7; 6 7; 6 8]; UnusedEdges = UnusedEdgeFinder(EdgeListG, EdgeListT, BdyEdges) %OUTPUT: %UnusedEdges = % 5 7 % 5 8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [NewBdyEdges UnusedEdges]= BdyEdgesUpdateInd(EdgeListT, BdyEdges, e, UnusedEdges) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 9.2.3(b) EdgeListG = [1 2 1; 1 4 2; 1 5 3; 1 7 4; 2 3 5; 2 5 6; 2 6 7; 3 6 8; 4 7 9; 5 7 10; 5 8 11; 6 7 12; 6 8 13]; EdgeListT = [1 2 1; 1 4 2; 2 3 5; 2 6 7]; BdyEdges = [1 5 3; 1 7 4; 2 5 6; 4 7 9; 6 7 12; 6 8 13]; UnusedEdges = [5 7 10; 5 8 11]; e = [6 7 12]; [NewBdyEdges UnusedEdges]= BdyEdgesUpdateInd(EdgeListT, BdyEdges, e, UnusedEdges) %OUTPUT: %NewBdyEdges = % 1 5 3 % 2 5 6 % 6 8 13 % 5 7 10 %UnusedEdges = % 5 8 11 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [ParentList DiscoveryList] = Prim(EdgeListG, Weights, startV, n) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 9.2.4(b) EdgeListG = [1 2 1; 1 4 2; 1 5 3; 1 7 4; 2 3 5; 2 5 6; 2 6 7; 3 6 8; 4 7 9; 5 7 10; 5 8 11; 6 7 12; 6 8 13]; Weights = [10 2 8 2 8 4 3 6 5 4 4 12 2]; startV = 1; n = 8; [ParentList DiscoveryList] = Prim(EdgeListG, Weights, startV, n) %OUTPUT: %ParentList = % 1 0 % 2 6 % 3 6 % 4 1 % 5 7 % 6 8 % 7 1 % 8 5 %DiscoveryList = % 1 4 7 5 8 6 2 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [ParentList DiscoveryList DistanceList] = Dijkstra(Edges, Wgts, startV, n) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %EFR 9.11 Edges = [1 2 1; 1 4 2; 1 5 3; 2 5 4; 2 6 5; 3 6 6; 3 7 7; 4 5 8; 4 8 9; 5 6 10; 5 8 11; 5 9 12; 6 7 13; 6 9 14; 6 10 15; 8 9 16; 9 10 17] Wgts = [6 12 8 4 3 6 2 5 3 2 4 4 5 2 3 2 10] startV = 1; n = 10; [ParentList DiscoveryList DistanceList] = Dijkstra(Edges, Wgts, startV, n) %OUTPUT: %ParentList = % 1 0 % 2 1 % 3 6 % 4 1 % 5 1 % 6 2 % 7 6 % 8 5 % 9 6 % 10 6 %DiscoveryList = % 1 2 5 6 9 4 8 10 7 3 %DistanceList = % 0 6 8 9 11 12 12 12 14 15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [ParentList DiscoveryList DistanceList] = DijkstraDigraph(Edges, Wgts, startV, n) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %EFR 9.12: Edges = [1 2 1; 1 4 2; 3 1 3; 3 6 4; 4 2 5; 4 3 6; 4 5 7; 4 7 8; 5 2 9; 5 7 10; 5 8 11; 6 4 12; 7 6 13; 7 8 14] Wgts = [12 3 6 3 4 5 2 4 6 2 3 4 2 10] startV = 1; n = 8; [ParentList DiscoveryList DistanceList] = DijkstraDigraph(Edges, Wgts, startV, n) %OUTPUT: %ParentList = % 1 0 % 2 4 % 3 4 % 4 1 % 5 4 % 6 7 % 7 4 % 8 5 %DiscoveryList = % 1 4 5 2 7 3 8 6 %DistanceList = % 0 3 5 7 7 8 8 9 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [ParentList DiscoveryList] = DepthFirstSearch(EdgeListG, startV, n) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 9.2.7(b) EdgeListG = [1 2 1; 1 4 2; 1 5 3; 1 7 4; 2 3 5; 2 5 6; 2 6 7; 3 6 8; 4 7 9; 5 7 10; 5 8 11; 6 7 12; 6 8 13]; [ParentList DiscoveryList] = DepthFirstSearch(EdgeListG, 1, 8) %OUTPUT: %ParentList = % 1 0 % 2 1 % 3 2 % 4 7 % 5 7 % 6 3 % 7 6 % 8 5 %DiscoveryList = 1 2 3 6 7 4 5 8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [ParentList DiscoveryList] = BreadthFirstSearch(EdgeListG, startV, n) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Computer Exercise 9.2.8(b) EdgeListG = [1 2 1; 1 4 2; 1 5 3; 1 7 4; 2 3 5; 2 5 6; 2 6 7; 3 6 8; 4 7 9; 5 7 10; 5 8 11; 6 7 12; 6 8 13]; [ParentList DiscoveryList] = BreadthFirstSearch(EdgeListG, 1, 8) %OUTPUT: %ParentList = % 1 0 % 2 1 % 3 2 % 4 1 % 5 1 % 6 2 % 7 1 % 8 5 %DiscoveryList = 1 2 4 5 7 3 6 8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [W, Points] = TSPRand(n,d) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [W, Points] = TSPRand(5,10) %OUTPUT: %W = % 0 9.9084 6.8925 6.2218 10.2584 % 9.9084 0 3.1393 5.5887 2.1036 % 6.8925 3.1393 0 2.9112 4.2590 % 6.2218 5.5887 2.9112 0 7.0951 % 10.2584 2.1036 4.2590 7.0951 0 %Points = % 0.9694 9.1892 % 9.1080 3.5377 % 7.0133 5.8759 % 7.1778 8.7825 % 8.0198 1.7375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [lowprice, Rts]=TSP_Brute(W) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Exercise 9.2.13: Running Errands TSP %1 = Home, 2 = Bank, 3 = School, 4 = Hardware, 5 = K-Mart, 6 = Grocery W = [0 2 2 3 4 3; 2 0 4 3 4 5; 2 4 0 5 6 5; 3 3 5 0 3 6; 4 4 6 3 0 3; 3 5 5 6 3 0]; [lowprice, Rts]=TSP_Brute(W) %OUTPUT: %lowprice = % 18 %Rts = % 1 6 5 4 2 3 1 % 1 3 6 5 4 2 1 % 1 3 2 4 5 6 1 % 1 2 4 5 6 3 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [Tour weight] = TSPNearNbr(W,start) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Data from Exercise 9.2.13: Running Errands TSP %1 = Home, 2 = Bank, 3 = School, 4 = Hardware, 5 = K-Mart, 6 = Grocery W = [0 2 2 3 4 3; 2 0 4 3 4 5; 2 4 0 5 6 5; 3 3 5 0 3 6; 4 4 6 3 0 3; 3 5 5 6 3 0]; [Tour weight] = TSPNearNbr(W,1) %OUTPUT: %Tour = 1 2 4 5 6 3 1 %weight = 18 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [Tour weight] = TSPNearInsertion(W,start) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Data from Exercise 9.2.13: Running Errands TSP W = [0 2 2 3 4 3; 2 0 4 3 4 5; 2 4 0 5 6 5; 3 3 5 0 3 6; 4 4 6 3 0 3; 3 5 5 6 3 0]; [Tour weight] = TSPNearInsertion(W,1) %OUTPUT: %Tour = 1 3 6 5 4 2 1 %weight = 18 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [Tour weight] = TSPCheapestInsertion(W,start) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Data from Exercise 9.2.13: Running Errands TSP W = [0 2 2 3 4 3; 2 0 4 3 4 5; 2 4 0 5 6 5; 3 3 5 0 3 6; 4 4 6 3 0 3; 3 5 5 6 3 0]; [Tour weight] = TSPCheapestInsertion(W,1) %OUTPUT: %Tour = 1 6 5 4 3 2 1 %weight = 24 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [maxFlow, Flow]= FordFulkerson(Edges,Wgts,Flow) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Illustration of FordFulkerson and FordFulkersonShow program using EFR 9.20: Edges = [1 2; 1 4; 2 3; 3 4; 3 6; 4 5; 5 6]; Wgts = [6 6 4 4 6 4 4]; Flow = [4 0 4 4 0 4 4]; [maxFlow, Flow]= FordFulkerson(Edges,Wgts,Flow) %OUTPUT: %maxFlow = % 8 %Flow = % 4 4 4 0 4 4 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%Demo for [maxFlow, Flow]= FordFulkerson(Edges,Wgts,Flow) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Illustration of FordFulkerson and FordFulkersonShow program using EFR 9.20: [maxFlow, Flow]= FordFulkersonShow(Edges,Wgts,Flow) %OUTPUT: %After iteration #1, we have: %Labels: %Label = % 0 1 Inf % 1 1 2 % 4 -1 4 % 1 1 6 % 0 0 0 % 3 1 4 %Flow: %Flow = % 4 4 4 0 4 4 4 %Value of flow: %maxFlow = % 8 %~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ % %After iteration #2, we have: %Labels: %Label = % 0 1 Inf % 1 1 2 % 0 0 0 % 1 1 2 %Flow: %Flow = % 4 4 4 0 4 4 4 %Value of flow: %maxFlow = % 8 %~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ % %maxFlow = % 8 %Flow = % 4 4 4 0 4 4 4 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Chapter 10: +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++