Directions: Complete the following exercises from your textbook.

1. What is a tree?  Is a PERT diagram always a tree?  Explain.

2. For each of the following graphs, determine if each is a tree and explain your answer.

a.

b.

3. What is a spanning tree?  Give an example.

4. Explain the breadth-first search spanning tree algorithm, and then apply it to the following graph:

5. Use Prim's algorithm to find the minimal spanning tree for the graph in the previous problem.

6. How do you know if a graph is a binary tree?

7. Explain the preorder traversal algorithm.

8. Explain the binary search tree search algorithm.

9. Evaluate the following:

a. C(7, 2)

b. C(12, 7)

c. (x + y)⁷

d. the coefficient of x⁷y² in the expansion of (2x - y)⁹

10. How many words must be chosen in order to assure that at least two begin with the same letter?

11. How many different 4-digit numbers can be formed using 5, 6, 7, and 8 without repetition?

12. How many distributions of 14 different books are possible if Carlos is to receive 5 books, Jamie 4 books, and Robert 2 books?

13. Define probability.

14. Determine the probability of the following:

a. If three dice are rolled, that all will be odd.

b. If two coins are flipped, that they both will land the same.

15. In a particular dormitory, there are 350 college freshmen.  Of these, 312 are taking an English course and 108 are taking a mathematics course.  If 95 of these freshman are taking courses in both English and mathematics, how many are taking neither?

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

a. s_n= -s_n-1 - n² for n >= 1, s₀ = 3

s₁₌ -s₀ - 1= -4

s₂₌ -s_{1 -4 = 0}

s_{3 = -}s_{2 -9 = - 9}

s₄ = -s₃- 16 = -17

s_{5 =} -s_{4 -25 = - 18}

b. s_n = 5s_n-1 - 3s_n-2 for n >= 2, s₀ = -1, s₁ = -2

s2 = 5s1 - 3s0 = -10 +3 = -7

s3 = 5s2 - 3s1 = -29

s4= 5s3 - 3s2 = -145 + 21 = -124

s5 = 5s4 - 3s3 = -533

17. An investor begins to save in 1990 with $500.  Each year, the savings increases 10% over the year before, and then an investor contributes another $100.  Write a recurrence relation and initial conditions on the s_n, the amount of savings n years after 1990.  Use this relation to determine the amount saved by 1994.

18. Explain the method of iteration.

19. Use the method of iteration to find a formula expressing sn as a function of n for the given recurrence relation:

s_n= -s_n-1 + 10, s₀ = -4

S(0) = -4

S(1) = -S(0) + 10 = 4 + 10 = 14

S(2) = -S(1) + 10 = -14 + 10 = -4 = S(0)

S(3) = -S(2) + 10 = 4 + 10 = 14 = S(1)

S(n) = { -4 if n is even.

          { 14 if n is odd.

20. What are finite state machines?  Is a computer a finite state machine?  Explain.

21. Draw a transition diagram for the finite state machine with the given state table:

22. Draw a transition diagram for the finite state machine with the given state table below, with A being both the initial and accepting state.

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

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

25. Draw the transition diagram for the finite state machine with output whose state and output tables is: