Skip to content

Instantly share code, notes, and snippets.

@futjikato

futjikato/gist:942dd8aa099e93e21d38

Last active August 29, 2015 14:19
Show Gist options
  • Save futjikato/942dd8aa099e93e21d38 to your computer and use it in GitHub Desktop.
Save futjikato/942dd8aa099e93e21d38 to your computer and use it in GitHub Desktop.
Download ZIP
AD 1
Raw
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment