Find the first pair by testing a key

Assignment Help Computer Engineering

Reference no: EM133186575

Question: Suppose you have n pairs of matching locks and keys. Unfortunately, the keys get mixed up. So our goal is to restore consistency.

(a) Imagine the following algorithm, which works in all situations:

First, we find the first pair by testing a key for at most n - 1 locks. Then we remove this pair and repeat the process. How many trials does this algorithm require?

(b) Suppose that both the keys and the keyholes are all different sizes. We further assume that we can detect these differences visually. Propose an algorithm that does not require a lock-to-key attempt to find the match.

Justify your answer and indicate whether the algorithm has any external costs beyond the lock-to-key attempts.

Reference no: EM133186575

Questions Cloud

Marginal product as workers at boeing : Explain whether workers at Airbus have the same marginal product as workers at Boeing?

What is importance of production function : What is the importance of the production function in determining how much input is required to produce a given output?

Making decisions regarding public expenditures : How will this analysis be used for making decisions regarding public expenditures?

Create simple versions of the location and gamemap classes : Create simple versions of the Location and GameMap classes from the previous task. To be clear about the (small) distinction

Find the first pair by testing a key : Find the first pair by testing a key for at most n - 1 locks. Then we remove this pair and repeat the process. How many trials does this algorithm require

Design a classifier that can identify : Design a classifier that can identify which of the two factories produced a given defective PPE. Let the components of the PPE be available and measurable

What are the final clusters : what are the final clusters and which is a better grouping in terms of within-cluster variance? Justify your answer

Estimate the i/o cost of the best possible solution : Consider a file of customer data that consists of 200,000 records, spread over 5000 disk blocks. There is a secondary index on the key attribut

Generate ideas for smart traffic management system : How to represent your thoughts, for example, you may explain them in words or depict them. The primary need is that the idea be clear

User Account

All Pages