Solved

Posted on 2004-10-01

1. Assume you have an input stream '1 2 3 4 5 6' reading from left to right. By using (1) a queue and (2) a deque, which of the following rearrangements can be obtained for output, reading from left-to-right?

a) 1 2 3 4 5 6 b) 2 4 3 6 5 1 c) 1 5 2 4 3 6

d) 4 2 1 3 5 6 e) 1 2 6 4 5 3 f) 5 2 6 3 4 1

2. Compute log2 1000 if all you know is log2 10. Show your work and justify why it is correct.

3. Show how logs "turn" multiplication into addition, division into subtraction, and exponentiation into multiplication.

4. A fully populated binary tree has all nodes (vertices) present. Assuming a tree with one node has height 1, what is the height of a fully populated tree with n nodes? A well-behaved binary tree may not have all levels fully populated, but all leaves in the tree will be on the same or on adjacent levels. What is the height of a well-behaved binary tree with n nodes? (hint: use the floor or ceil function from the math library.)

a) 1 2 3 4 5 6 b) 2 4 3 6 5 1 c) 1 5 2 4 3 6

d) 4 2 1 3 5 6 e) 1 2 6 4 5 3 f) 5 2 6 3 4 1

2. Compute log2 1000 if all you know is log2 10. Show your work and justify why it is correct.

3. Show how logs "turn" multiplication into addition, division into subtraction, and exponentiation into multiplication.

4. A fully populated binary tree has all nodes (vertices) present. Assuming a tree with one node has height 1, what is the height of a fully populated tree with n nodes? A well-behaved binary tree may not have all levels fully populated, but all leaves in the tree will be on the same or on adjacent levels. What is the height of a well-behaved binary tree with n nodes? (hint: use the floor or ceil function from the math library.)

4 Comments

ahaa! Got one...

2. All should be looked up in a table of numbers. Work is shown in existence of table. It is correct, because computes that use tables take less time, doing simple lookups, than depending on use of formula using other criteria.

Just remember, being right does not help in life, and that includes getting a grade. It only helps you do do better in your own way. I doubt a grader would ever care for a SunBowian response.

(1) What sequence of enqueue and dequeue operations can you perform with a queue where the items arrive in the given order? The order of dequeuing operations is the order of items in the output.

Consider the same thing with the deque BUT remember that a deque can service entries at either end. Can you come up with a sequence of arrivals and services (from either end) to come up with each/any of the patterns?

(You might also want to think about what output orders you could generate with a stack...the answers are all three related.)

(2) and (3) are intimately related. Start by writing down the definition of log and thinking about it. Show us some work you have done and we can help.

(4) This one is fun. Draw some full trees to get the first answer (you are looking for patterns). Then think about how few nodes would fit in a well-behaved tree of height k (I know, backwards...think about it, though). Then look for the equation relating the two (nodes and heights) and remember the hint to use floor and ceil.

Show us the progress you are making on this homework and we would be happy to make comments.

-bcl

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Title | # Comments | Views | Activity |
---|---|---|---|

Revenue table | 8 | 88 | |

Access question - internal training | 9 | 60 | |

Dual bridge protection | 18 | 87 | |

Most Consistent Performer | 4 | 20 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**20** Experts available now in Live!