math vic

Math 11: Exam #3 Name: ______________________________ ID: ___________________________

1.

a) Explain why it is impossible to draw the above figure without lifting your pencil and without retracing any previously drawn line.

b) Take away some edges to make it possible to draw the figure using the rules of a) – remove the fewest possible number.

c) Show how to draw your new figure following the rules of a). The easiest way to show this is to list the order you would traverse the vertices.

2.

a) Too many edges- please throw some away. I want to keep a minimal set so that any two vertices are still connected. Find the tree that does this for me. Use a BFS and draw your tree in the standard way.

b) Same as a), but a DFS.

3. Help! I’m stuck at a and want to get to z. Money is tight, so please tell me how to do this as cheaply as possible. We learned an algorithm in class that solves problems like this. Tell me the path and convince me you understand the algorithm. You won’t get any credit for just telling me the answer.

4. I could easily find a tree that spans this using a BFS or a DFS. The cheapest tree that spans needs another algorithm. Use one of the two we learned in class to find the cheapest tree. Which algorithm are you using? Give me a step-by-step account of your tree building process.

5. We’ve made contact! Surprisingly, the Martian alphabet consists of only 5 letters. Here are the frequencies we’ve found.

a) Because can only send strings of 0’s and 1’s to mars, we need to code our messages as bit strings. An algorithm we learned in class can help devise the most efficient encoding. Use it to build a code so we can talk to the Martians.

b) What’s the code for KXQX?

c) In terms of bits/letter, what’s efficiency of your code?