X a C def g f(x) v4 v5 v1 v6 v2 v3 v7 a) Does f define an isomorphism between Graph 1 and Graph 2? b ) Define a new function g (with g # f) that defines an isomorphism between Graph 1 and Graph 2. c) Is the graph pictured below in Figure 1 isomorphic to Graph 1 and Graph 2? Explain. Figure 1 Use the Closest Neighbor Algorithm to find the closest neighbor circuit and cost starting at vertex 7 in Figure 2. Algorithm 9.5.1: The Closest Neighbor Algorithm Let G = (V, E, w) be a complete weighted graph with | V| = n. The closest neighbor circuit through G starting at , is (v1, 12, ..., ".) , defined by the steps: 1. Vi = V- {}- 2. For k = 2 ton - 1 a. ve = the closest vertex in Vx-1 to vx-1: w (vx-1, Uk) = min (w (v-1, ") | DE VA-1) In case of a tie for closest, v, may be chosen arbitrarily. b. VA = VA-1 - {vx} 3. Un = the only element of V. The cost of the closest neighbor circuit is E w (vx, VA+1) + w (un, v1)10) Jerry bought eight cans of Pepsi, seven cans of Sprite, three cans of Dr. Pepper, and six cans of Mountain Dew. He wants to bring 10 cans to his pal's house when they watch the basketball game tonight. Assuming the cans are distinguishable, say, with different expiration dates, how many selections can he make if he wants to bring a) Exactly four cans of Pepsi? b) At least four cans of Pepsi? c) At most four cans of Pepsi? d) Exactly three cans of Pepsi, and at most three cans of Sprite? 11) A professor surveyed the 350 students in her class to count how many of them had watched at least one of the three films in the original Star Wars trilogy (Episode IV, V, and VI). This is what she found: 210 had watched Episode IV; 180 had watched Episode V; 110 had watched Episode VI; 100 had watched both Episodes IV and V; 70 had watched both Episodes IV and VI; 90 had watched both Episodes V and VI; 60 had watched all three episodes. How many students did not watch any one of these three films? 12) Five balls are chosen from a bag of eight blue balls, six red balls, and five green balls. How many of these five-ball selections contain exactly five red balls? 13) The number of four-letter words that can be formed from the letters in SASSABY (each letter occurring at most as many times as it occurs in SASSABY) is a) 78 b) 90 c) 108 d) 114 e) 120 Here are some examples: SSSA, AASS, SSBY, AAYS, etc. 14) Consider the following two graphs: G1: V1 = {a, b, c, d, e, f, g), El = {{a, b], {a, d], {b, c), {b, d), {b, e], (b, f], {c, g), {d, e), (e, f], {f, g]]. G2: V2 = {v1, v2, v3, v4, v5, v6, v7}, E2 = {{v1, v4), {v1, v5], {v1, v7], {v2, v3], {v2, v6], {v3, v5], {v3, v7). {v4, v5), {v5, v6], {v5, v7}} Let f: G1 - G2 be a function that takes the vertices of Graph 1 to vertices of Graph 2. The function is given by the following table:Show written solutions for all of the following problems. Unit 1, 3, 5, 7 1) Construct a truth table for the following statement: ((p A -q) Ar) - -(r vp). 2) Simplify the following statement: (p / (pv q)) / (-p / (-q V -p)). Clearly identify any rules used to simplify. 3) Write out a complete proof that if n is an integer, n is even if and only if n is even. 4) Prove that the cube root of 2 is an irrational number. 5) Give as good (i.e., small) a Big-O estimate as possible for each of the following functions. a) (n2 + 3n + 8)(n + 1) b) (3logn + 5n2) (n3 + 3n + 2) 6) List the following functions by increasing order of growth. Here log means logz. Here are the functions: f1 = log(nlogn), f2 = n(log n), f3 = log(n6006), f4 = (logn)2 , fs = n2 logn. 7) What is the total number of additions in the following code? S := 0 for i : = 1 to n S := s * i for j := 1 to n S := s * j + i next j next i 8) Use the Euclidean GCD Algorithm found in the file: Euclidean_GCD_Algorithm.pdf file under Unit 3: Algorithms and Growth Functions to find the GCD of the following pairs of numbers and write each pair as a linear combination. a) god(12, 40) b) god(16, 32) 9) The permutations on {a, b, c, d, e, f, g} are listed in lex (i.e., lexicographical order, alphabetical) order. All permutations X1X2X3X4XX6X7 with X4 = a or x4 = c are kept. All others are discarded. In this reduced list what permutation is just after dagcfeb? a) dbacefg b) dbcaefg c) dbacgfe d) dagcfbe e) dobaefgIN 15 3 17 10 5 Figure 2 16) Apply the Breadth-first Search Algorithm to find a path from 1 to 3 in Figure 3. What would be the final value of V (an example of V is shown in Table 1 below, where Depthset is equal to the number of edges used in the path starting at 1 and ending at k)? Assume that the terminal vertices in edge lists and elements of the depth sets are put into ascending order. Algorithm 9.3.2: Breadth-first Search A broadcasting algorithm for finding a path between vertex i and vertex j of a graph having n vertices. Each item V, of a list V = (Vi, V,, ..., V.), consists of a Boolean field Vi. found and an integer field Vi. from. The sets D1, Da,.... called depth sets, have the property that if & E D., then the shortest path from vertex i to vertex & is of length r. In Step 5, a stack is used to put the vertex list for the path from the vertex i to vertex j in the proper order. That stack is the output of the algorithm. 1. Set the value Vi. found equal to False, k = 1, 2, ..., 2. r= 0 3. Do = {{} 4. while (-V,. found) and (D, # 0) o for each k in Dr: for each edge (k,t): If V. found = = False: Vi. found = True V- from = k or=r+1 5. if Vi. found: o S = EmptyStack o k= j o while Vi. from * i: Push k onto S k = VA. from Push k onto S Push i onto $k 1 2 3 CT Ve. found T T T T T T Vx. from 2 4 6 1 1 4 Depthset 1 4 2 2 3 Table 1 Figure 3 17) Consider the following graph: a) Find a Hamilton path. Can your path be extended to a Hamilton cycle? b) Is the graph bipartite? If so, how many vertices are in each "part"? c) Find a Euler path, if possible. If not, explain why one does not exist