Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

1. On the east coast of the U.S. there are many toll roads such as the Pennsylvania Turnpike and the Garden State Expressway. When you enter the toll road you get handed a ticket with your entrance location marked on it. Then when you exit the toll road you pay an amount based on where you entered and exited. To be precise, each segment (from exit i to exit i+1) has a cost Ci,i+1 and the cost of entering at exit j and exiting at exit k (for j < k) is equal to k-1i=j Ci,i+1. If the road has n exits then it has n-1 segments which can be represented in a one dimensional array, C[1,....,n-1], where C[i] holds the cost to travel from exit i to exit i + 1. Clearly, if you have the array C you can determine the cost of traveling from exit j to exit k by computing k-1i=j Ci,i+1 which will take O(k-j) time.

Show how to build a data structure that will allow you to determine the cost of traveling from exit j to exit k on the toll road in O(1) time. A fair answer creates a data structure that has O(n2) elements. A better answer creates a data structure that has O(n) elements.

Be sure to justify the correctness of your solution and analyze the running time required to build your data structure.

2. A binary tree is full if all of its nodes have either zero or two children. Let Bn denote the number of full binary trees with n nodes.
(a) Draw all full binary trees with 3, 5, and 7 nodes and determine the exact values of B3,B5,B7.

(b) Why did I leave out trees with an even number of nodes?

(c) For odd n devise a recurrence relation for Bn and bound its value in terms of n.

3. A one pass auction is an auction in which each bid must be immediately and irrevocably accepted or refused. Specifically, a one pass auction works as follows:

• A seller announces the availability of an item

• n buyers agree to bid on the item and are presented to the seller in random order.

• When buyer i appears he must make a bid bi > 0 without any knowledge of the bids thus far.

• The seller must decide immediately whether to accept or reject buyer i's bid. If the seller accepts then all future buyers are turned away. If the seller rejects then buyer i leaves and his bid is withdrawn.

Obviously the seller would like to maximize her profit but since she doesn't know what future bids will be and she can't accept a bid she has already rejected she will never be able to formulate an algorithm that ensures that she accepts the highest bid. She must turn to a probabilistic algorithm. Consider the following two phase algorithm that a seller may follow:

1) Reject the first n/10 bids but keep track of the largest bid seen. Call that bid B*.

2) In the remaining bids accept the first bid that surpasses B* (if none surpass B* then accept the very last bid).

Investigate this algorithm and try to answer the following problems:

(a) Using the given algorithm what is the probability that the seller accepts the highest bid?

(b) Can you come up with a better probabilistic algorithm for a one pass auction? Justify why it is better.

(c) In general, how do you determine whether one algorithm is better than another for this type of auction?

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91926

Have any Question? 


Related Questions in Computer Engineering

Could palm beach county be vulnerable to a future adea

Could Palm Beach County be vulnerable to a future ADEA lawsuit using a "disparate impact" theory? If so, who would have the ultimate burden in such a case and what would the burden be? What critical Supreme Court rulings ...

What are the short term and long term consequences of

What are the short term and long term consequences of designing a system with contract-to-logic coupling? What are the effects on the service itself and what are the effects on the overall service inventory when this occ ...

Which us federal agency has taken control of the overall

Which U.S. federal agency has taken control of the overall National Infrastructure Protection mission?

If your computer only has one network card installed

If your computer only has one network card installed explain how your virtual machine is able to share that card with your host operating system.

Implementing network awareness explain exactly what happens

Implementing network awareness. Explain exactly what happens in the network (what messages are sent and when) during the execution of the distributed lexical scoping example given in section 11.4. Base your explanation o ...

In relation to the elaboration likelihood model professor

In relation to the Elaboration Likelihood Model, Professor Kahn discussed the peripheral cues that people use to accept or reject messages. Which of the following is NOT one of the peripheral cues that she mentioned?

A what is a surrogate keyb where does the value of a

a. What is a surrogate key? b. Where does the value of a surrogate key come from? c. When would you use a surrogate key? d. What is a foreign key? e. The term domestic key is not used. If it were used, however, what do y ...

Give three additional commonly used statistical measures

Give three additional commonly used statistical measures that are not already illustrated in this chapter for the characterization of data dispersion. Discuss how they can be computed efficiently in large databases.

Two divers start at the surface and establish the following

Two divers start at the surface and establish the following coordinate system: x is to the west, y is to the north, and z is down. Diver 1 swims 60 ft east, then 25 ft south, and then dives 30 ft. At the same time, diver ...

How can the national institute of standards and technology

How can the National Institute of Standards and Technology (NIST), help your company create a "best practices" cybersecurity policy? Your discussion should touch upon both the positive and the negative aspects of a well- ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate