What is the competitive ratio of the greedy algorithm

Assignment Help Other Subject

Reference no: EM131232112

Question 1. Assume you have the following set of preferences of people over seats at a table:

{"John", {Seat1, Seat2, Seat 3},
"Mary",{Seat2, Seat4},
"Bob", {Seat1, Seat3, Seat4},
"Alice", {Seat3, Seat5},
"Cindy", {Seat1, Seat2, Seat3}}

What is the competitive ratio of the greedy algorithm vs. the optimal seating arrangement?

Question 2. Explain in your own words, why is it hard to measure the ClickThrough Rate?

Question 3. Consider the following scenario:

There are three advertisers A, B, and C

A bids on query x, B bids on x and y, and C bids on x, y, and z

All have budgets of $3.

Given the following query stream:

x xx y yy z zz

a) What are the sequences of choices for both the greedy algorithm assuming the worst case scenario and the BALANCE algorithm?

b) What are the competitive ratios for both algorithms in this scenario?

Question 4. Three computers, A, B, and C, have the numerical features listed below:

Feature	A	B	C
Processor Speed	3.06	2.68	2.92
Disk Size	500	320	640
Main-Memory Size	6	4	6

We may imagine these values as defining a vector for each computer; for instance, A's vector is [3.06, 500, 6]. We can compute the cosine distance between any two of the vectors, but if we do not scale the components, then the disk size will dominate and make differences in the other components essentially invisible. Let us use 1 as the scale factor for processor speed, α for the disk size, and β for the main memory size.

(a) In terms of α and β, compute the cosines of the angles between the vectors for each pair of the three computers.

(b) What are the angles between the vectors if α = β = 1?

Question 5. A certain user has rated the three computers of Problem 1 as follows: A: 4 stars, B: 2 stars, C: 5 stars.
(a) Normalize the ratings for this user.
(b) Compute a user profile for the user, with components for processor speed, disk size, and main memory size, based on the data of

Question 6. Given the following utility matrix, representing the ratings, on a 1-5 star scale, of eight items, a through h, by three users A, B, and C:

	a	b	c	d	e	f	g	h
A	4	5		5	1		3	2
B		3	4	3	1	2	1
C	2		1	3		4	5	3

Compute the following from the data of this matrix.

(a) Normalize the matrix by subtracting from each nonblank entry the average value for its user.

(b) Using the normalized matrix from Part (a), compute the cosine distance between each pair of users.

Reference no: EM131232112

Questions Cloud

Who bears cost and who gains benefits of such legislation : Will health and safety legislation mandating workplace and product safety standards reduce the profitability of the regulated firms? Who bears the cost and who gains the benefits of such legislation? .

What competencies were you able to develop in researching : What competencies were you able to develop in researching and writing the course Comprehensive Project? How did you leverage knowledge gained in the intellipath assignments in completing the Comprehensive Project

What logic function is implemented by this circuit : Consider the circuit in Figure. - What logic function is implemented by this circuit? - Are there any potential problems with this circuit?

What evidence can you cite for or against this view : "If more nations become as rich as the United States, the pressures placed on natural systems will quickly become intolerable. Our world cannot sustain such increases in consumption." What evidence can you cite for or against this view?

What is the competitive ratio of the greedy algorithm : Normalize the matrix by subtracting from each nonblank entry the average value for its user - Using the normalized matrix from Part (a), compute the cosine distance between each pair of users.

Create oracle database tables using sql ddl : Explain why the statements fail. Be sure to save your script used to as yournameproject2step2.sql. You can include comments in the SQL script describing why the insert statements failed. Submit your SPOOL file showing that all SQL in your SQL s..

Design an nmos pass transistor logic circuit : Design an NMOS pass transistor logic circuit to perform the given function. - Assume that both the variable and its complement are available as input signals.

What is their policy and it is illegal : Chipotle is under fire for their employee social media policy. What is their policy and it is illegal? There is a growing body of research suggesting that a dog-friendly office could have a real impact on employee well-being and productivity - do y..

What is the logic function implemented by the circuit : Consider the circuit in Figure. - Determine the value of Y for φ. - What is the logic function implemented by the circuit?

User Account

All Pages