Encoding word using given Huffman code tree, and other tree related problems.

[1] Encode "LEADEN" using the Huffman code tree given in the attachment. [2] What can you say about a vertex in a rooted tree that has no descendants? Please see the attachment for more tree related problems.

Find a minimal spanning tree (MST) for the given graph using Prim's algorithm.

Find a minimal spanning tree for the connected weighted graph, following Prim's algorithm. Please see attached 4.doc for the details on graph and Prim's algorithm for finding a minimal spanning tree.

Encode and decode strings using given Huffman code tree.

Using the Huffman code given in the attached image, (a) encode the string "NEEDLE". (b) decode the bit string "01111001001110".

Find the bad coin out of given 8 coins using only a pan balance.

Eight coins are identical in appearance, but one coin is either heavier or lighter than the others, which all weigh the same. Describe an algorithm that identifies the bad coin in at most three weighings and also determines whether it is heavier or lighter than the others, using only a pan balance.

Solve for coefficient.

When (x-2)^17 is expanded, what is the coefficient of x^12? Be careful, don’t forget about the –2.

Recurrence Relation

A vending machine accepts only pennies and nickels. a) Find a recurrence relation for the number of ways to deposit n cents where the order in which coins are deposited matters. b) What are the initial conditions for the recurrence? c) Use the recurrence to count the number of ways to deposit 12 cents.

Recurrence Relations

Solve the recurrence relation a(n)=3a(n-1)+10a(n-2) with the initial conditions a(0)=0 and a(1)=2. Solve the recurrence relation a(n)=3a(n-1)+10a(n-2) +12 with the initial conditions a(0)=0 and a(1)=2. For a particular solution, try a(n)=C, a constant.

Equivalence Relations

H is the relation on the set of all people given by H = {(a,b)|a and b are the same height}. Is H an equivalence relation? Explain your answer.

Combinations

A committee of size seven is to be selected from a group of ten people. In how many ways can this be done?

Relations : Reflexive, Symmetric and/or Transitive

Determine if the relation R on the set of all people is reflexive, symmetric and/or transitive where (x,y) "E" R if and only if x and y live within one mile of each other. NOTE: I cannot correctly indicate the symbol to show "is a member of" so I have used "E" in it's place.