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?
(c) What are the angles between the vectors if α = 0.01 and β = 0.5?
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.