futjikato/gist:942dd8aa099e93e21d38

## gistfile1.html
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>L&ouml;sungsblatt Vorlage</title>
<!-- morris graph lib -->
<link rel="stylesheet" href="http://cdnjs.cloudflare.com/ajax/libs/morris.js/0.5.1/morris.css">
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.9.0/jquery.min.js"></script>
<script src="http://cdnjs.cloudflare.com/ajax/libs/raphael/2.1.0/raphael-min.js"></script>
<script src="http://cdnjs.cloudflare.com/ajax/libs/morris.js/0.5.1/morris.min.js"></script>
<!-- LaTeX-style equations -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});
</script>
<script type="text/javascript"
  src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<!-- tests -->
<script>
  function assert(value, desc) {
    var li = document.createElement("li");
    li.style.color = value ? "green" : "red";
    li.appendChild(document.createTextNode(desc));
    var list = document.getElementById("results");
    if (!list) {
      list = document.createElement("div");
      document.body.appendChild(list);
    }
    list.appendChild(li);
  }

  /**
  * Measures the runtime for a given function.
  *
  * fn         {function} Algorithm function to be measured. First parameter is the `done` callback that should be called on termination.
  * iterations {int}      How often the function should be called
  * res        {function} Function called with the resulting runtime in ms.
  *
  * Example
  * ```javascript
  *  measureRt(function(i, done) {
  *    setTimeout(done, 1)
  *  }, 10, function(rt) {
  *    console.log('runtime:', rt);
  *  });
  * ```
  */
  function measureRt(fn, iterations, res) {
    for(var i = 0 ; i < iterations ; i++) {
      var t1 = performance.now();

      fn(i, function() {
        var t2 = performance.now();

        var rt = t2 - t1;
        res(i, rt);
      });
    }
  }
</script>
</head>
<body>
<h1 id="title">L&ouml;sungsblatt Vorlage - Moritz Spindelhirn</h1>

Vorlage zur L&ouml;sung des ersten Aufgabenblatts.
<ul>
<li>
Die erste &Uuml;berschrift soll Ihre Namen enthalten.
</li>
<li>
Die Korrektheit Ihrer Implementierung muss durch sinnvolle Tests abgesichert sein.
</li>
<li>
&Uuml;berlegen Sie sich sinnvolle Eingaben und Wiederholungen f&uuml;r die Experimente.
</li>
</ul>

<h2>
Aufgabe 1
</h2>
<p>
Gegeben seien ein Startpunkt $x \in \mathbb{N}$ und ein Zielpunkt $y \in \mathbb{N}$ auf einer Geraden,
sowie ein Schrittma&szlig; $d \in \mathbb{N}$. Gesucht ist die Anzahl der Schritte
$steps(x, y, d) \in \mathbb{N}$, die ben&ouml;tigt werden, um einen Punkt zu erreichen, dessen Wert
gr&ouml;&szlig;er als $y$ ist.
</p>
<p>
Beispiel: Bei der Eingabe $x = 15$, $y = 80$, $d = 30$ sind drei Schritte n&ouml;tig.
</p>
<ol>
<li>
In Abh&auml;gigkeit von welchem Wert bestimmen Sie Laufzeit und Speicherplatzbedarf?
</li>
<li>
Welchen Zeit- und welchen Platzaufwand hat eine naive Implementierung?
</li>
<li>
Implementieren Sie die Methode $steps(x,y,d)$, welche die gesuchte Anzahl der Schritte in Zeitaufwand $O(1)$ und  Platzaufwand $O(1)$ berechnet.
</li>
</ol>
<h2>
Antwort 1
</h2>
<ol>
<li>
Für die native implementierung ist die Laufzeit vom Ergbenis.
</li>
<li>
O((x-y)/d)
</li>
</ol>
<h3>
Implementierung
</h3>
<!-- In diesem Element wird der Inhalt des scripts mit der ID ad-1-1-results angezeigt -->
<pre id="ad-1-1-source"></pre>
<h3>
Testergebnisse
</h3>
<div id="ad-1-1-results"></div>
<!-- Code und Tests hier hin -->
<script id="ad-1-1-code">
  /**
   * Native implementierung
   */
  function steps(x,y,d) {
    var runs = 0;
    while(x < y) {
      x += d;
      runs++;
    }

    return runs;
  }

  /**
   * O(1)
   * Implementation mit konstanter Laufzeit
   */
   function kSteps(x, y, d) {
     return Math.ceil((y-x) / d);
   }

  // Tests
  assert(typeof(steps) === 'function', "function 'steps' not implemented");
  assert(steps(15, 80, 30) === 3, 'Bei der Eingabe x=15, y=80, d=30 sind drei Schritte nötig.');
  assert(kSteps(15, 80, 30) === 3, 'Bei der Eingabe x=15, y=80, d=30 sind drei Schritte nötig.');
</script>
<!-- dieser Code zeigt die Implementierung und die Tests an -->
<script>
$('pre#ad-1-1-source').html($('#ad-1-1-code').html())
</script>

<!-- Aufgabe 2 -->
<h2>
Aufgabe 2
</h2>
Implementieren Sie Funktionen zur Berechnung der Fibonacci Zahlen.
<ul>
  <li>Bestimmen Sie experimentell den Zeitaufwand von fib und stellen Sie das Ergebnis gra-
    phisch dar. Geben Sie die gemessene Laufzeitklasse möglichst präzise in der O-Notation
    an.</li>
  <li>Erläutern Sie, ob und wie sich Ihre Implementierung f ib2 und f ib3 im Platzaufwand
    unterscheiden.</li>
</ul>
<h2>
Antwort 2
</h2>
<ol>
<li>
O(n^2)
</li>
<li>
<p>fib2 Hat einen Platzaufwand von O(n), da jede Fibunacci Zahl von 2 bis n gespeichert wird.</p>
<p>fib3 hat einen konstanten Platzaufwand da auch in der tiefesten Stelle der rekursion nur 2 Variablen belegt werden.<br>
Nach beim aufsteigen der rekursion wird eine der Zahlen nur umgespeichert und eine Zahl durch eine neue ersetzt. Der alte Wert
der Variable muss nicht gespeichert werden.</p>
</li>
</ol>
<h3>
Implementierung
</h3>
<!-- In diesem Element wird der Inhalt des scripts mit der ID ad-1-2-code angezeigt -->
<pre id="ad-1-2-source"></pre>
<h3>
Testergebnisse
</h3>
<div id="ad-1-2-results"></div>
<!-- Code und Tests hier hin -->
<script id="ad-1-2-code">
  var ad_1_2_1_data = [],
      ad_1_2_2_data = [],
      ad_1_2_1_runs = 40,
      ad_1_2_2_runs = 300;
  for(var i = 0 ; i < ad_1_2_1_runs ; i++) {
    ad_1_2_1_data.push({label:i});
  }
  for(var i = 0 ; i < ad_1_2_2_runs ; i++) {
    ad_1_2_2_data.push({label:i});
  }

  // Code
  /**
   * Rekursive implementierung ohne Caching
   */
  function fib(i) {
    if(i <= 2) {
      return 1;
    }

    return fib(i-1) + fib(i-2);
  }

  // Experiment
  measureRt(function(i, done) {
    fib(i);
    done();
  }, ad_1_2_1_runs, function(i, runtime) {
    ad_1_2_1_data[i].fib = runtime
  });

  /**
   * Linear cached
   */
  var cache = {};
  function fib2(i) {
    if(i <= 2) {
      return 1;
    }

    if(cache.hasOwnProperty(i)) {
      return cache[i];
    }

    // fib2(i-1) hat linearen aufwand
    // fib2 insgesamt linear da fib2(i-2) gecached ist und somit eine konstante laufzeit hat
    var res = fib2(i-1) + fib2(i-2);
    cache[i] = res;

    return res;
  }

  // Experiment
  measureRt(function(i, done) {
    fib2(i);
    done();
  }, ad_1_2_2_runs, function(i, runtime) {
    ad_1_2_2_data[i].fib2 = runtime
  });

  /**
   * Linear ohne Cache
   */
  function fib3(i) {
    if(i <= 1) {
      return [1, 0];
    }
    if(i == 2) {
      return [1, 1];
    }

    var ary = fib3(i-1),
        last = ary[0];

    var res = ary[0] + ary[1];

    return [res, last];
  }

  // Experiment
  measureRt(function(i, done) {
    fib3(i);
    done();
  }, ad_1_2_2_runs, function(i, runtime) {
    ad_1_2_2_data[i].fib3 = runtime
  });

  /**
   * Linear als iterative implemntation
   */
  function fib4(i) {
    var nm2 = 0,
    nm1 = 1,
    ergebnis = 1;

    for(var r = 2 ; r <= i ; r++) {
      ergebnis = nm2 + nm1;
      nm2 = nm1;
      nm1 = ergebnis;
    }

    return ergebnis;
  }

  // Experiment
  measureRt(function(i, done) {
    fib4(i);
    done();
  }, ad_1_2_2_runs, function(i, runtime) {
    ad_1_2_2_data[i].fib4 = runtime
  });

  // Tests
  assert(fib(40) === 102334155, "fib1 Fehler bei Anfrage für 40");
  assert(fib2(40) === 102334155, "fib2 Fehler bei Anfrage für 40");
  assert(fib3(40)[0] === 102334155, "fib3 Fehler bei Anfrage für 40");
  assert(fib4(40) === 102334155, "fib4 Fehler bei Anfrage für 40");
</script>
<!-- dieser Code zeigt die Implementierung und die Tests an -->
<script>
$('pre#ad-1-2-source').html($('#ad-1-2-code').html())
</script>

<h3>
Experimente
</h3>

<div id="ad-1-2-1-experiments" style="height: 250px;"></div>
<script>
new Morris.Line({
  // ID of the element in which to draw the chart.
  element: 'ad-1-2-1-experiments',
  // do values relate to dates (time)?
  parseTime: false,
  // Chart data records -- each entry in this array corresponds to a point on
  // the chart.
  data: ad_1_2_1_data,
  // The name of the data record attribute that contains x-values.
  xkey: 'label',
  // A list of names of data record attributes that contain y-values.
  ykeys: ['fib'],
  // Labels for the ykeys -- will be displayed when you hover over the
  // chart.
  labels: ['fib','fib2','fib3','fib4']
});
</script>
<div id="ad-1-2-2-experiments" style="height: 250px;"></div>
<script>
new Morris.Line({
  // ID of the element in which to draw the chart.
  element: 'ad-1-2-2-experiments',
  // do values relate to dates (time)?
  parseTime: false,
  // Chart data records -- each entry in this array corresponds to a point on
  // the chart.
  data: ad_1_2_2_data,
  // The name of the data record attribute that contains x-values.
  xkey: 'label',
  // A list of names of data record attributes that contain y-values.
  ykeys: ['fib2','fib3','fib4'],
  // Labels for the ykeys -- will be displayed when you hover over the
  // chart.
  labels: ['fib','fib2','fib3','fib4']
});
</script>

<!-- Aufgabe 3 -->
<h2>
  Aufgabe 3
</h2>
Verkettete und Sequentielle Listen.
<h2>
  Antwort 3
</h2>
<ol>
  <li>
    TODO
  </li>
</ol>
<h3>
  Implementierung
</h3>
<!-- In diesem Element wird der Inhalt des scripts mit der ID ad-1-3-code angezeigt -->
<pre id="ad-1-3-source"></pre>
<h3>
  Testergebnisse
</h3>
<div id="ad-1-3-results"></div>
<!-- Code und Tests hier hin -->
<script id="ad-1-3-code">
var ad_1_3_data = [];

// Code
/**
 * Eintrag in verketteter Liste
 */
function LinkedListEntry(value) {
  this.value = value;
  this.next = undefined;
}

/**
 * Verkettete Liste
 */
function LinkedList() {
  this.next = undefined;
  this._helpRefCnt = 0;
}
LinkedList.prototype.cons = function(x) {
  var xElem = new LinkedListEntry(x);
  if(typeof this.next !== 'undefined') {
    this._helpRefCnt++;
    xElem.next = this.next;
  }
  this._helpRefCnt++;
  this.next = xElem;
}
LinkedList.prototype.head = function() {
  if(typeof this.next === 'undefined') {
    return undefined;
  }
  return this.next.value;
}
LinkedList.prototype.tail = function() {
  var r = new LinkedList();
  if(this.next === 'undefined') {
    return r;
  }
  this._helpRefCnt++;
  r.head = this.next.next;
  return r;
}
LinkedList.prototype.length = function() {
  this._helpRefCnt++;
  var elem = this.next,
      count = 0;
  while(typeof elem !== 'undefined') {
    count++;
    this._helpRefCnt++;
    elem = elem.next;
  }

  return count;
}
LinkedList.prototype.isempty = function() {
  return typeof this.next === 'undefined';
}
LinkedList.prototype.insert = function(x, n) {
  this._helpRefCnt++;
  var cElem = this.next;
  for(var i = 0 ; i < n ; i++) {
    if(typeof cElem === 'undefined') {
      throw new Error('Index out of range.');
    }
    this._helpRefCnt++;
    cElem = cElem.next;
  }

  var newElem = new LinkedListEntry(x);

  this._helpRefCnt++;
  if(cElem.next !== 'undefined') {
    newElem.next = cElem.next;
  }

  this._helpRefCnt++;
  cElem.next = newElem;
}

/**
 * Sequentielle Liste
 */
function ArrayList() {
  this.data = [];
}
ArrayList.prototype.cons = function(x) {
  var tmp = this.data[0];
  this.data[0] = x;

  var index = 1;
  while(typeof this.data[index] !== 'undefined') {
    var tmp2 = this.data[index];
    this.data[index] = tmp;
    tmp = tmp2;
    index++;
  }

  this.data[index] = tmp;
}
ArrayList.prototype.head = function() {
  return this.data[0];
}
ArrayList.prototype.tail = function() {
  var cpy = this.data;
  var index = 1;
  cpy[0] = cpy[1];
  while(typeof cpy[index] !== 'undefined') {
    cpy[index] = cpy[index+1];
  }

  return cpy;
}
ArrayList.prototype.lngth = function() {
  var l = 0;
  while(this.data[l] !== 'undefined') {
    l++;
  }

  return l;
}
ArrayList.prototype.isempty = function() {
  // hmm .... bei aktueller implementierung nicht wichtig.
  return typeof this.data[0] === 'undefined';
}
ArrayList.prototype.insert = function(x, n) {
  this.data[n] = x;
}

// Experiments
for(i = 0; i < 10; i ++) {
  var lList = new LinkedList();
  lList.cons(i);
}
console.log(lList._helpRefCnt);

// Tests
assert(ad_1_3_data.length === 10, "experiments have collected data");
assert(typeof(steps) === 'function', "function 'steps' not implemented");
</script>
<!-- dieser Code zeigt die Implementierung und die Tests an -->
<script>
  $('pre#ad-1-3-source').html($('#ad-1-3-code').html())
</script>

<h3>
  Experimente
</h3>

<div id="ad-1-3-experiments" style="height: 250px;"></div>
<script>
  new Morris.Line({
    // ID of the element in which to draw the chart.
    element: 'ad-1-3-experiments',
    // do values relate to dates (time)?
    parseTime: false,
    // Chart data records -- each entry in this array corresponds to a point on
    // the chart.
    data: ad_1_3_data,
    // The name of the data record attribute that contains x-values.
    xkey: 'experiment',
    // A list of names of data record attributes that contain y-values.
    ykeys: ['value'],
    // Labels for the ykeys -- will be displayed when you hover over the
    // chart.
    labels: ['Value']
  });
</script>


</body>
</html>
	<!DOCTYPE html>
	<html>
	<head>
	<meta charset="UTF-8">
	<title>Lösungsblatt Vorlage</title>
	<!-- morris graph lib -->
	<link rel="stylesheet" href="http://cdnjs.cloudflare.com/ajax/libs/morris.js/0.5.1/morris.css">
	<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.9.0/jquery.min.js"></script>
	<script src="http://cdnjs.cloudflare.com/ajax/libs/raphael/2.1.0/raphael-min.js"></script>
	<script src="http://cdnjs.cloudflare.com/ajax/libs/morris.js/0.5.1/morris.min.js"></script>
	<!-- LaTeX-style equations -->
	<script type="text/x-mathjax-config">
	MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});
	</script>
	<script type="text/javascript"
	src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
	</script>
	<!-- tests -->
	<script>
	function assert(value, desc) {
	var li = document.createElement("li");
	li.style.color = value ? "green" : "red";
	li.appendChild(document.createTextNode(desc));
	var list = document.getElementById("results");
	if (!list) {
	list = document.createElement("div");
	document.body.appendChild(list);
	}
	list.appendChild(li);
	}

	/**
	* Measures the runtime for a given function.
	*
	* fn {function} Algorithm function to be measured. First parameter is the `done` callback that should be called on termination.
	* iterations {int} How often the function should be called
	* res {function} Function called with the resulting runtime in ms.
	*
	* Example
	* ```javascript
	* measureRt(function(i, done) {
	* setTimeout(done, 1)
	* }, 10, function(rt) {
	* console.log('runtime:', rt);
	* });
	* ```
	*/
	function measureRt(fn, iterations, res) {
	for(var i = 0 ; i < iterations ; i++) {
	var t1 = performance.now();

	fn(i, function() {
	var t2 = performance.now();

	var rt = t2 - t1;
	res(i, rt);
	});
	}
	}
	</script>
	</head>
	<body>
	<h1 id="title">Lösungsblatt Vorlage - Moritz Spindelhirn</h1>

	Vorlage zur Lösung des ersten Aufgabenblatts.
	<ul>
	<li>
	Die erste Überschrift soll Ihre Namen enthalten.
	</li>
	<li>
	Die Korrektheit Ihrer Implementierung muss durch sinnvolle Tests abgesichert sein.
	</li>
	<li>
	Überlegen Sie sich sinnvolle Eingaben und Wiederholungen für die Experimente.
	</li>
	</ul>

	<h2>
	Aufgabe 1
	</h2>
	<p>
	Gegeben seien ein Startpunkt $x \in \mathbb{N}$ und ein Zielpunkt $y \in \mathbb{N}$ auf einer Geraden,
	sowie ein Schrittmaß $d \in \mathbb{N}$. Gesucht ist die Anzahl der Schritte
	$steps(x, y, d) \in \mathbb{N}$, die benötigt werden, um einen Punkt zu erreichen, dessen Wert
	größer als $y$ ist.
	</p>
	<p>
	Beispiel: Bei der Eingabe $x = 15$, $y = 80$, $d = 30$ sind drei Schritte nötig.
	</p>
	<ol>
	<li>
	In Abhägigkeit von welchem Wert bestimmen Sie Laufzeit und Speicherplatzbedarf?
	</li>
	<li>
	Welchen Zeit- und welchen Platzaufwand hat eine naive Implementierung?
	</li>
	<li>
	Implementieren Sie die Methode $steps(x,y,d)$, welche die gesuchte Anzahl der Schritte in Zeitaufwand $O(1)$ und Platzaufwand $O(1)$ berechnet.
	</li>
	</ol>
	<h2>
	Antwort 1
	</h2>
	<ol>
	<li>
	Für die native implementierung ist die Laufzeit vom Ergbenis.
	</li>
	<li>
	O((x-y)/d)
	</li>
	</ol>
	<h3>
	Implementierung
	</h3>
	<!-- In diesem Element wird der Inhalt des scripts mit der ID ad-1-1-results angezeigt -->
	<pre id="ad-1-1-source"></pre>
	<h3>
	Testergebnisse
	</h3>
	<div id="ad-1-1-results"></div>
	<!-- Code und Tests hier hin -->
	<script id="ad-1-1-code">
	/**
	* Native implementierung
	*/
	function steps(x,y,d) {
	var runs = 0;
	while(x < y) {
	x += d;
	runs++;
	}

	return runs;
	}

	/**
	* O(1)
	* Implementation mit konstanter Laufzeit
	*/
	function kSteps(x, y, d) {
	return Math.ceil((y-x) / d);
	}

	// Tests
	assert(typeof(steps) === 'function', "function 'steps' not implemented");
	assert(steps(15, 80, 30) === 3, 'Bei der Eingabe x=15, y=80, d=30 sind drei Schritte nötig.');
	assert(kSteps(15, 80, 30) === 3, 'Bei der Eingabe x=15, y=80, d=30 sind drei Schritte nötig.');
	</script>
	<!-- dieser Code zeigt die Implementierung und die Tests an -->
	<script>
	$('pre#ad-1-1-source').html($('#ad-1-1-code').html())
	</script>

	<!-- Aufgabe 2 -->
	<h2>
	Aufgabe 2
	</h2>
	Implementieren Sie Funktionen zur Berechnung der Fibonacci Zahlen.
	<ul>
	<li>Bestimmen Sie experimentell den Zeitaufwand von fib und stellen Sie das Ergebnis gra-
	phisch dar. Geben Sie die gemessene Laufzeitklasse möglichst präzise in der O-Notation
	an.</li>
	<li>Erläutern Sie, ob und wie sich Ihre Implementierung f ib2 und f ib3 im Platzaufwand
	unterscheiden.</li>
	</ul>
	<h2>
	Antwort 2
	</h2>
	<ol>
	<li>
	O(n^2)
	</li>
	<li>
	<p>fib2 Hat einen Platzaufwand von O(n), da jede Fibunacci Zahl von 2 bis n gespeichert wird.</p>
	<p>fib3 hat einen konstanten Platzaufwand da auch in der tiefesten Stelle der rekursion nur 2 Variablen belegt werden.<br>
	Nach beim aufsteigen der rekursion wird eine der Zahlen nur umgespeichert und eine Zahl durch eine neue ersetzt. Der alte Wert
	der Variable muss nicht gespeichert werden.</p>
	</li>
	</ol>
	<h3>
	Implementierung
	</h3>
	<!-- In diesem Element wird der Inhalt des scripts mit der ID ad-1-2-code angezeigt -->
	<pre id="ad-1-2-source"></pre>
	<h3>
	Testergebnisse
	</h3>
	<div id="ad-1-2-results"></div>
	<!-- Code und Tests hier hin -->
	<script id="ad-1-2-code">
	var ad_1_2_1_data = [],
	ad_1_2_2_data = [],
	ad_1_2_1_runs = 40,
	ad_1_2_2_runs = 300;
	for(var i = 0 ; i < ad_1_2_1_runs ; i++) {
	ad_1_2_1_data.push({label:i});
	}
	for(var i = 0 ; i < ad_1_2_2_runs ; i++) {
	ad_1_2_2_data.push({label:i});
	}

	// Code
	/**
	* Rekursive implementierung ohne Caching
	*/
	function fib(i) {
	if(i <= 2) {
	return 1;
	}

	return fib(i-1) + fib(i-2);
	}

	// Experiment
	measureRt(function(i, done) {
	fib(i);
	done();
	}, ad_1_2_1_runs, function(i, runtime) {
	ad_1_2_1_data[i].fib = runtime
	});

	/**
	* Linear cached
	*/
	var cache = {};
	function fib2(i) {
	if(i <= 2) {
	return 1;
	}

	if(cache.hasOwnProperty(i)) {
	return cache[i];
	}

	// fib2(i-1) hat linearen aufwand
	// fib2 insgesamt linear da fib2(i-2) gecached ist und somit eine konstante laufzeit hat
	var res = fib2(i-1) + fib2(i-2);
	cache[i] = res;

	return res;
	}

	// Experiment
	measureRt(function(i, done) {
	fib2(i);
	done();
	}, ad_1_2_2_runs, function(i, runtime) {
	ad_1_2_2_data[i].fib2 = runtime
	});

	/**
	* Linear ohne Cache
	*/
	function fib3(i) {
	if(i <= 1) {
	return [1, 0];
	}
	if(i == 2) {
	return [1, 1];
	}

	var ary = fib3(i-1),
	last = ary[0];

	var res = ary[0] + ary[1];

	return [res, last];
	}

	// Experiment
	measureRt(function(i, done) {
	fib3(i);
	done();
	}, ad_1_2_2_runs, function(i, runtime) {
	ad_1_2_2_data[i].fib3 = runtime
	});

	/**
	* Linear als iterative implemntation
	*/
	function fib4(i) {
	var nm2 = 0,
	nm1 = 1,
	ergebnis = 1;

	for(var r = 2 ; r <= i ; r++) {
	ergebnis = nm2 + nm1;
	nm2 = nm1;
	nm1 = ergebnis;
	}

	return ergebnis;
	}

	// Experiment
	measureRt(function(i, done) {
	fib4(i);
	done();
	}, ad_1_2_2_runs, function(i, runtime) {
	ad_1_2_2_data[i].fib4 = runtime
	});

	// Tests
	assert(fib(40) === 102334155, "fib1 Fehler bei Anfrage für 40");
	assert(fib2(40) === 102334155, "fib2 Fehler bei Anfrage für 40");
	assert(fib3(40)[0] === 102334155, "fib3 Fehler bei Anfrage für 40");
	assert(fib4(40) === 102334155, "fib4 Fehler bei Anfrage für 40");
	</script>
	<!-- dieser Code zeigt die Implementierung und die Tests an -->
	<script>
	$('pre#ad-1-2-source').html($('#ad-1-2-code').html())
	</script>

	<h3>
	Experimente
	</h3>

	<div id="ad-1-2-1-experiments" style="height: 250px;"></div>
	<script>
	new Morris.Line({
	// ID of the element in which to draw the chart.
	element: 'ad-1-2-1-experiments',
	// do values relate to dates (time)?
	parseTime: false,
	// Chart data records -- each entry in this array corresponds to a point on
	// the chart.
	data: ad_1_2_1_data,
	// The name of the data record attribute that contains x-values.
	xkey: 'label',
	// A list of names of data record attributes that contain y-values.
	ykeys: ['fib'],
	// Labels for the ykeys -- will be displayed when you hover over the
	// chart.
	labels: ['fib','fib2','fib3','fib4']
	});
	</script>
	<div id="ad-1-2-2-experiments" style="height: 250px;"></div>
	<script>
	new Morris.Line({
	// ID of the element in which to draw the chart.
	element: 'ad-1-2-2-experiments',
	// do values relate to dates (time)?
	parseTime: false,
	// Chart data records -- each entry in this array corresponds to a point on
	// the chart.
	data: ad_1_2_2_data,
	// The name of the data record attribute that contains x-values.
	xkey: 'label',
	// A list of names of data record attributes that contain y-values.
	ykeys: ['fib2','fib3','fib4'],
	// Labels for the ykeys -- will be displayed when you hover over the
	// chart.
	labels: ['fib','fib2','fib3','fib4']
	});
	</script>

	<!-- Aufgabe 3 -->
	<h2>
	Aufgabe 3
	</h2>
	Verkettete und Sequentielle Listen.
	<h2>
	Antwort 3
	</h2>
	<ol>
	<li>
	TODO
	</li>
	</ol>
	<h3>
	Implementierung
	</h3>
	<!-- In diesem Element wird der Inhalt des scripts mit der ID ad-1-3-code angezeigt -->
	<pre id="ad-1-3-source"></pre>
	<h3>
	Testergebnisse
	</h3>
	<div id="ad-1-3-results"></div>
	<!-- Code und Tests hier hin -->
	<script id="ad-1-3-code">
	var ad_1_3_data = [];

	// Code
	/**
	* Eintrag in verketteter Liste
	*/
	function LinkedListEntry(value) {
	this.value = value;
	this.next = undefined;
	}

	/**
	* Verkettete Liste
	*/
	function LinkedList() {
	this.next = undefined;
	this._helpRefCnt = 0;
	}
	LinkedList.prototype.cons = function(x) {
	var xElem = new LinkedListEntry(x);
	if(typeof this.next !== 'undefined') {
	this._helpRefCnt++;
	xElem.next = this.next;
	}
	this._helpRefCnt++;
	this.next = xElem;
	}
	LinkedList.prototype.head = function() {
	if(typeof this.next === 'undefined') {
	return undefined;
	}
	return this.next.value;
	}
	LinkedList.prototype.tail = function() {
	var r = new LinkedList();
	if(this.next === 'undefined') {
	return r;
	}
	this._helpRefCnt++;
	r.head = this.next.next;
	return r;
	}
	LinkedList.prototype.length = function() {
	this._helpRefCnt++;
	var elem = this.next,
	count = 0;
	while(typeof elem !== 'undefined') {
	count++;
	this._helpRefCnt++;
	elem = elem.next;
	}

	return count;
	}
	LinkedList.prototype.isempty = function() {
	return typeof this.next === 'undefined';
	}
	LinkedList.prototype.insert = function(x, n) {
	this._helpRefCnt++;
	var cElem = this.next;
	for(var i = 0 ; i < n ; i++) {
	if(typeof cElem === 'undefined') {
	throw new Error('Index out of range.');
	}
	this._helpRefCnt++;
	cElem = cElem.next;
	}

	var newElem = new LinkedListEntry(x);

	this._helpRefCnt++;
	if(cElem.next !== 'undefined') {
	newElem.next = cElem.next;
	}

	this._helpRefCnt++;
	cElem.next = newElem;
	}

	/**
	* Sequentielle Liste
	*/
	function ArrayList() {
	this.data = [];
	}
	ArrayList.prototype.cons = function(x) {
	var tmp = this.data[0];
	this.data[0] = x;

	var index = 1;
	while(typeof this.data[index] !== 'undefined') {
	var tmp2 = this.data[index];
	this.data[index] = tmp;
	tmp = tmp2;
	index++;
	}

	this.data[index] = tmp;
	}
	ArrayList.prototype.head = function() {
	return this.data[0];
	}
	ArrayList.prototype.tail = function() {
	var cpy = this.data;
	var index = 1;
	cpy[0] = cpy[1];
	while(typeof cpy[index] !== 'undefined') {
	cpy[index] = cpy[index+1];
	}

	return cpy;
	}
	ArrayList.prototype.lngth = function() {
	var l = 0;
	while(this.data[l] !== 'undefined') {
	l++;
	}

	return l;
	}
	ArrayList.prototype.isempty = function() {
	// hmm .... bei aktueller implementierung nicht wichtig.
	return typeof this.data[0] === 'undefined';
	}
	ArrayList.prototype.insert = function(x, n) {
	this.data[n] = x;
	}

	// Experiments
	for(i = 0; i < 10; i ++) {
	var lList = new LinkedList();
	lList.cons(i);
	}
	console.log(lList._helpRefCnt);

	// Tests
	assert(ad_1_3_data.length === 10, "experiments have collected data");
	assert(typeof(steps) === 'function', "function 'steps' not implemented");
	</script>
	<!-- dieser Code zeigt die Implementierung und die Tests an -->
	<script>
	$('pre#ad-1-3-source').html($('#ad-1-3-code').html())
	</script>

	<h3>
	Experimente
	</h3>

	<div id="ad-1-3-experiments" style="height: 250px;"></div>
	<script>
	new Morris.Line({
	// ID of the element in which to draw the chart.
	element: 'ad-1-3-experiments',
	// do values relate to dates (time)?
	parseTime: false,
	// Chart data records -- each entry in this array corresponds to a point on
	// the chart.
	data: ad_1_3_data,
	// The name of the data record attribute that contains x-values.
	xkey: 'experiment',
	// A list of names of data record attributes that contain y-values.
	ykeys: ['value'],
	// Labels for the ykeys -- will be displayed when you hover over the
	// chart.
	labels: ['Value']
	});
	</script>


	</body>
	</html>