math vic

Exam 3: Solution

1. Are the following graphs isomorphic? If yes, give the correspondence between the vertices. If not, explain

why.

The graphs are not isomorphic. The right graph has a circuit of length 3,

the left graph doesn’t.

2. For the graph on the first two pages,

a) Find an Eulerian path if possible, or explain why no such path exists.

There is a path. Resolving ties alphabetically gives

c a b c d e c f e

b) Use a breadth-first search to find a spanning tree.

c) I am trying to find the shortest path from a to all of the other vertices using Djikstra’s Algorithm. I have

already completed the first step. Finish the next two 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].

[b,c] [c,f] [c,d] [e,f] [a,b]

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).

0000101011

c) On average, how many bits per letter will be used for an average message?

0.40(3) 0.60(1) 1.8  bits/letter

A 0.08

B 0.08

C 0.12

D 0.12

E 0.60

A 000

B 001

C 010

D 011

E 1

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,1

The original matrix

0 1 0 0

0 0 1 0

0 0 0 1

1 0 0 0

           

First row, first column

0 1 0 0

0 0 1 0

0 0 0 1

1 1 0 0

           

Second row, second column

0 1 1 0

0 0 1 0

0 0 0 1

1 1 1 0

           

Third row, third column

0 1 1 1

0 0 1 1

0 0 0 1

1 1 1 1

           

Fourth row, fourth column

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

           

5. a) Use the Euclidean algorithm to find  gcd 121, 23

121 5 23 6

23 3 6 5

6 1 5 1

  

  

  

 gcd 121, 23 1

b) Find integers a and b such that 121 23 1a b 

 

 

6 1 5 1

5 23 3 6 6 1 23 3 6 1 4 6 1 23 1

6 121 5 23 4 121 5 23 1 23 1 4 121 21 23 1

  

             

              

4, 21a b  

c) Solve the equation 23 118 0 mod121x  

(Your answer should be in the form mod121x a where 0 121a  )

23 118 mod121

23 3 mod121

21 23 21 3 mod121

63 mod121

58 mod121

x

x

x

x

x

 



    

 



d) Find one positive and one negative value of x such that all of the following are simultaneously true.

3mod 5x  , 5 mod 7x  and 7 mod11x 

3mod 5 5 3x x k   

 5 mod 7 5 3 5 mod 7 6 mod 7 7 6 5 7 6 3 35 33x k k k l x l l              

 35 33 7 mod11 2 7 mod11 9 mod11 11 9 35 11 9 33 385 348l l l l m x m m              

0 348m x  

1 37m 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.