Solved

# url request to explain below

Posted on 2004-10-01
246 Views
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.)

0
Question by:edelossantos

LVL 33

Assisted Solution

snoyes_jw earned 50 total points
Surely this is homework...  We cannot do homework on this site, though if you show us your work and ask a question, we can help you over a hurdle.
0

LVL 24

Assisted Solution

SunBow earned 150 total points
hmmmmm                                                                                                    <sigh>
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.
0

LVL 11

Accepted Solution

Homework:

(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
0

Author Comment

Excellent, thank you.  I will re-post my work to this question.  Regards. Del
0

## Featured Post

Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …