Prims algorithm state tables and recurrence relations

Question

Assignment:

Q1. Let A = {1, 2, 3, 4}, B = {3, 4, 5}, C = {1}, and D = {x: 3 < x < 10}. Are each of the following true or false?
b. B ⊆ D
c. ∅ ⊆ D

Q2. Calculate the following:
a. P(8, 4)

Q3. Let A = {1, 2, 3, 4}, B = {1, 4, 5}, C = {3, 5, 6}, and the universal set U = {1, 2, 3, 4, 5, 6}.
a. Determine the resulting set: A ∩ (B U C)
 
b. Determine the resulting set: A U C
   
Q4. Determine which of the reflexive, symmetric, and transitive properties are satisfied by the given relation R defined on set S, and state whether R is an equivalence relation on S.
a. S = {1,2,3,4,5,6,7,8} and x R y means that x - y = 0

b. S = {1,2,3,4,5,6,7,8} and x R y means that x > y


Q5. In the following exercise Z denotes the set of integers. Determine if each function g is one-to-one, onto, or both.

Q6. Suppose that a number xn is computed recursively by x₁ = 1, x₂ = 2 and x_n = x_n-1 + x_n-2 + 1 for n ≥ 3. Compute x₁ through x₅.

Q7. Find a Hamiltonian path for the following graph:

Q8. Construct the labeled directed graph for the adjacency matrix:

Q9. Use Prim's algorithm to find a minimum spanning tree for the following graph:

Q10. How many three letter combinations can be formed from the letters defgh if no letter can be used more than once?

Q11. Four employees wear identical coats that are hung on a coat tree in the morning and retrieved in the evening. Assuming each employee chooses a coat at random, what is the probability that they all leave wearing the same coats they wore that morning?


Q12. Out of 250 computer users, 125 use Microsoft products and 56 use Oracle products. 44 use both Microsoft and Oracle products. How many are using products from neither?


Q13. In the following sequences determine s5 if s0, s1, ... sn, ... is a sequence satisfying the given recurrence relation and initial condition.

 Q14. Give the state table for the finite state machine with the given transition diagram:

Q15. In what state would the machine in the previous question end if it started in the initial state and was given the input string abbbb?

Provide complete and step by step solution for the question and show calculations and use formulas.