function [ D1, D2, td ] = Aufgabe1(X)
%Aufgabe1 - compute distance matrix.
%
%usage
%  [D1, D2, td] = Aufgabe1(X)
%
%input
%  X : (d,n)-matrix of column vectors.
%
%output
%  D1 : (n,n)-matrix of L_2 distances, computed by for-loop.
%  D2 : (n,n)-matrix of L_2 distances, computed by matrix algebra.
%  td : run-time difference between computation of D1 and D2
%
%description
%  Aufgabe1 computes the pairwise L_2 distances between the column vectors
%  of X using two different algorithms: D1 by explicit for-loops, D2 by matrix
%  algebra. td reports the difference in runtime between the two implementations, where
%  td is positive, if the first method (D1) took longer than the second. 
%
%author
%  buenau@cs.tu-berlin.de

[d, n] = size(X);

% Speicher für Distanzmatrizen reservieren. 
D1 = zeros(n, n);
D2 = zeros(n, n);

% Timer starten. 
tic; 

% Distanzmatrix mit for-Schleifen berechnen. 
for j = 2:n
    for i = 1:j-1  % Nur obere Dreiecksmatrix berechnen, da die Distanzmatrix symmetrisch ist.
        D1(i, j) = sqrt( sum ( ( X(:,i) - X(:,j) ) .^ 2 ) );
    end
end
D1 = D1 + D1';  % Untere Dreiecksmatrix hinzufügen. 

% Timer stoppen. 
time_D1 = toc; 

% Timer starten. 
tic;

% Distanzmatrix ohne for-Schleifen berechnen. 
xx = sum(X .^ 2, 1);    % (1, n)-Vektor der quadratischen Terme x'*x. 
xy = X'*X;              % (n, n)-Matrix der gemischten Terme x'*y.
D2 = sqrt(repmat(xx, [n 1]) - 2*xy + repmat(xx', [1 n]));

% Timer stoppen. 
time_D2 = toc; 

% Zeitdifferenz errechnen. 
td = time_D1 - time_D2;
