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

Verify that eulers theorem holds in zm m 69 for all

Verify that Euler's Theorem holds in Zm, m = 6,9, for all elements a for which gcd(a,m) = 1. Also verify that the theorem does not hold for elements a for which gcd(a,m) ≠ 1. For the affine cipher in Chapter 1 the multip ...

1 why should salts be chosen at random2 does using

1. Why should salts be chosen at random? 2. Does using passwords with salts make attacking a specific account more difficult than using passwords without salts? Explain why or why not. 3. Show that a system using an EKE ...

1 study and suggest the best ways to defend the national

1. Study and suggest the best ways to defend the national critical infrastructure from potential attackers. 2. We indicated in the text that the best ways to manage security threats is to do an extensive risk assessment ...

1 indicate dependences and their type2 assume there is no

1. Indicate dependences and their type. 2. Assume there is no forwarding in this pipelined processor. Indicate hazards and add nop instructions to eliminate them. 3. Assume there is full forwarding. Indicate hazards and ...

Q1 what are the three techniques to improve performance of

Q.1 What are the three techniques to improve performance of CPU? Q.2 Describe how a cache memory is organized? Q.3 What are the three different approaches are commonly used to enhance the performance of memory? Q.4 Narra ...

Assign state numbers to the states of the finite-state

Assign state numbers to the states of the finite-state machine you constructed for Exercise B.37 and write a set of logic equations for each of the outputs, including the next-state bits. Exercise B.37 A friend would lik ...

1 what are circuit-level firewalls how are they different

1. What are circuit-level firewalls? How are they different from network-level firewalls? 2. Discuss the limitations of firewalls. How do modern firewalls differ from the old ones in dealing with these limitations? 3. Ho ...

1 explain why you think your design meets the needs of

1. Explain why you think your design meets the needs of ElectroMyCycle. 2. List the major user communities for your design. 3. List the major data stores and the user communities for each data store. 4. Identify major ne ...

1 suppose a notifier sends e-mail to the system

1. Suppose a notifier sends e-mail to the system administrator when a successful compromise of that system is detected. What are the drawbacks of this approach? How would you notify the appropriate user? 2. Describe a se ...

1 compare a piconet and a scatternet in the bluetooth

1. Compare a piconet and a scatternet in the Bluetooth architecture. 2. Can a piconet have more than eight stations? Explain. 3. What is the actual bandwidth used for communication in a Bluetooth network? 4. What is the ...

  • 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

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro