Explain the binary search tree search algorithm

Assignment Help Data Structure & Algorithms

Reference no: EM131044027

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.

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:

1977_Spanning Tree.png

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:

	A	B	C
0	B	C	A
1	A	C	B

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.

	A	B
x	B	A
y	A	A
z	B	B

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

1750_Transition Diagram.png

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:

	A	B	A	B
0	A	A	z	X
1	B	B	z	Y

Reference no: EM131044027

Questions Cloud

Ameru community in east africa : What was the name given to the council of elders of the Ameru Community in East Africa?

Find maxima and minima of the function : what is the graph of y=x+(1/x). i can't sketch the graph.because if i use x=0 then y=infinity. and i want to find maxima and minima of the function. here the maxima is less than in minima. but don't understand why this happens? please show me the ..

Etch-a-sketch ethics : Is it possible, as Mr. Killgallon claims, that the Ohio Art Company had no knowledge of labour problems at Kin Ki? Do you think company executives had any knowledge of the working conditions?

Analyze the types of risks that must be managed : Compare options, forwards, futures, and swaps for managing foreign exchange risk exposure. Form an argument for what you believe is the best method for a non-financial firm in managing this exchange rate risk.

Explain the binary search tree search algorithm : How do you know if a graph is a binary tree? Explain the preorder traversal algorithm. Explain the binary search tree search algorithm.

Explain the sources of organizational conflict : Identify and explain the sources of organizational conflict and show how conflict can be functional or dysfunctional when an organizational is going through a change

Does nasa have a learning organization culture : How would you have drafted the email if you were in Rodney Rocha's situation? Is email always the best way to communicate? When is it a good medium and when does it present limitations that introduce risk to the organization?

Explain the different methods of financing healthcare : Present your analysis with supporting information as a 4-page report in a Word document formatted in APA style.Name your document as: LastnameFirstInitial_W1_A3.doc.

Examine different frameworks : Examine different frameworks, models, or roadmaps used to pursue improvement projects. Generic improvement model, Lean, Six Sigma, Business Process Management (BPM), Toyota Production System (TPS), Theory of Constraints (TOC), Rummler-Brache, Proce..

User Account

All Pages