math vic
Exam 3: Solution
1. Are the following graphs isomorphic? If yes, give the correspondence between the vertices. If not, explain
why not.
They are isomorphic. 1, 6, 3, 8, 2, 5, 4, 7a b c d f e g h is one
possible pairing.
2. For the graph on the first two pages,
a) Find an Eulerian path if possible, or explain why no such path exists.
No path is possible – d,e, and f all have odd degree.
b) Use a breadth-first (depth-first) search to find a spanning tree.
c) I am trying to find the shortest path from vertex a to all of the other edges for the graph on the first page. I
just did the first step and got the following. Complete the first three steps for me.
d) Use Prim’s algorithm to find a minimal spanning tree. List the edges in the order selected. The edge
connecting vertex a to vertex b can be described as [a,b].
[a,d] [a,b] [b,f] [b,c] [e,f]
3. a) Construct a Huffman code for messages that contain only the following letters with the given frequencies.
b) Encode the word ACED with your answer to a). 000011110
c) On average, how many bits per letter will be used for an average message?
0.06 3 0.13 3 0.20 2 0.27 2 0.34 2 2.19 bits/letter
A 0.06
B 0.13
C 0.20
D 0.27
E 0.34
A 000
B 001
C 01
D 10
E 11
4. Use Warshall’s algorithm to find the transitive closure of the relation whose ordered pair representation is
1, 2 , 2, 3 , 3, 4 4, 2
0 1 0 0
0 0 1 0
0 0 0 1
0 1 0 0
Note that the first column is all 0’s. We start with the second row and
second column.
0 1 1 0
0 0 1 0
0 0 0 1
0 1 1 0
Third row-third column.
0 1 1 1
0 0 1 1
0 0 0 1
0 1 1 1
Fourth row-fourth column.
0 1 1 1
0 1 1 1
0 1 1 1
0 1 1 1
5. a) Use the Euclidean algorithm to find gcd 97, 20
97 4 20 17
20 1 17 3
17 5 3 2
3 1 2 1
gcd 97, 20 1
b) Find integers a and b such that 97 20 1a b
3 1 2 1
2 17 5 3 3 1 17 5 3 1 6 3 1 17 1
3 20 1 17 6 20 1 17 1 17 1 6 20 7 17 1
17 97 4 20 6 20 7 97 4 20 1 34 20 7 97 1
97, 34a b
c) Solve the equation 20 95 0 mod 97x
(Your answer should be in the form mod 97x a where 0 97a )
20 95 0 mod 97
20 95 mod 97
20 2 mod 97
34 20 34 2 mod 97
68 mod 97
x
x
x
x
x
d) Find one positive and one negative value of x such that all of the following are simultaneously true.
1mod 3x , 2 mod 7x and 7 mod11x
1mod 3 3 1x x k
3 1 2 mod 7 3 1mod 7 5 mod 7 7 5 3 7 5 1 21 16k k k k l x l l
21 16 7 mod11 9 mod11 9 mod11 11 9 21 11 9 16 231 205l l l l m x m m
0 205m x
1 26m x
Bonus Question: When are the final exams for this class? Wednesday,12/11 at 2:00 PM in G205 and
Thursday, 12/12 at noon in the Forum.