Q$1(20$ points$).$

Let $G=(V,E)$ be a connected, undirected graph with real number edge weights. Also assume that all edge weights are distinct.

a$.(5$ pts$)$ Does the min$-$weight edge of $G$ have to be on Minimum Spanning Tree $($MST$)$ of $G?$

b$.(5$ pts$)$ Can the max$-$weight edge of $G$ belong to MST$?$

c$.(5$ pts$)$ Adding the same positive value to every edge of $G$ can change MST or not?

d$.(5$ pts$)$ Adding the same positive value to every edge of $G$ can change shortest path between two vertices or not?

For all question above, do not leave your answer as YES or NO$.$ Discuss the situation with examples $($by drawing simple graphs$).$ If you can, prove your answer by contradiction or counter$-$examples. For some questions, answer may change at different conditions. If so$,$ please discuss the answer separately for all different cases.

Q$2(30$ points$).$

Remember the rod cutting problem, the following is an instance of it:

$\backslash$table$[[$length $i,1,2,3,4,5,6,7,8,9,10],[$price $p_i,1,4,8,9,10,17,18,22,22,30]]$

a$.(15$ pts$)$ Define the density of a rod of length $i$ to be pli, that is$,$ value per inch. A greedy strategy for cutting a rod of length $n$ cuts first the piece with the highest density.

b$.(15$ pts$)$ Show by a counterexample $($at least for one $n)$ that this greedy strategy does not always determine an optimal way to cut rods.

Q$3(50$ points$).$

a$)(35$ pts$)$ Build an AVL tree after successively inserting the keys: $91,33,64,75,27,13,73,60,89,87,20,9,12,25,26,79,74,5.$ Show and explain every iteration.

b$)(15$ pts$)$ Traverse the tree you build in$-$order, pre$-$order, and post$-$order.