- You are given a set V consisting of n integers. The task is to report all n products of the n distinct (n − 1)-cardinality subsets of V . Your algorithm should run in linear time and it should not use division.
pending
Exercise 2 (20 points):
Some years ago, greek video-club chain Seven had the following offer to their customers: every time a customer rented a DVD, he was given a random coupon with the title of the Academy awards (Oscars) winner movie written on it. The first person to gather the coupons with all the unique winner-movie titles won a 10-day vacation on a Caribbean island. If at that time, there were 75 unique such titles, and these titles were uniformly assigned to coupons, find the expected number of DVDs one had to rent in order to gather all of them.
....
.
.
Exercise 3 (20 points):
Assume two d-dimensional real vectors x and y. And denote by xi (yi) the value in the i-th coordinate of x (y). Prove or disprove the following statements:
1. Distance function =\(L_1\left(x,y\right)=\sum_{i=1}^d\left|x_{i-}y_i\right|\) is a metric. (5 points)
A distance function that satisfies all the below properties is called a metric
- non-negativity, \(d\left(x,y\right)\ge0\)
- isolation, \(d\left(x,y\right)=0\ \Leftrightarrow\ x=y\)
- symmetry, \(d\left(x,y\right)=d\left(y,x\right)\)
- triangle inequality ,\(d\left(x,z\right)\le d\left(x,y\right)+d\left(y,z\right)\)
Proof:
i. non-negativity:-
\(Consider\ D\left(x,y\right)\ge0\ \forall\ x,y\ \epsilon\ R\) --------------------- equation 1
\(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
\(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|-x_i+y_i\right|\)
\(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|-1\right|\left|x_i-y_i\right|\) (because \(\left|x-y\right|=\ \ \left|-1\right|\cdot\left|y-x\right|\))
\(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
Using Equation 1 we can say that \(\ D\left(-x,-y\right)\ge0\)
Alternate Proof: The formula consists of a sum of a modulus (|x-y|)which would always be positive for all values of x and y because modulus of a number is always positive.
ii. Isolation
\(d\left(x,y\right)=0\ \Leftrightarrow\ x=y\)
\(Given\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
Considering x=y
\(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-x_i\right|\) (because x=y)
\(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|0\right|=0\)
iii. Symmetry
\(d\left(x,y\right)=d\left(y,x\right)\)
\(D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
\(D\left(y,x\right)=\sum_{i=1}^d\left|y_i-x_i\right|\)
if \(x-y\ge0\) then \(y-x\le0\) | if \(x-y\le0\) then \(y-x\ge0\)
\(\Rightarrow\left|x-y\right|=x-y\) and \(\Rightarrow\left|y-x\right|=x-y\) | \(\Rightarrow\left|x-y\right|=y-x\) and \(\Rightarrow\left|y-x\right|=y-x\)
\(\Rightarrow\sum_{i=1}^d\left|x_i-y_i\right|=\sum_{i=1}^d\left|y_i-x_i\right|\) | \(\Rightarrow\sum_{i=1}^d\left|x_i-y_i\right|=\sum_{i=1}^d\left|y_i-x_i\right|\)
Therefore,
\(D\left(x,y\right)=D\left(y,x\right)\)
iv. triangle inequality ,
\(d\left(x,z\right)\le d\left(x,y\right)+d\left(y,z\right)\)
To Prove: \(\left|x-z\right|\le\left|x-y\right|+\left|y-z\right|\)