eneskaya/gist:284e6b854d36b95b5d85

## gistfile1.html
<!DOCTYPE html>
<html>
	<head>
		<title>ADP4 - Aufgabe 2</title>
		<!-- morris graph lib -->
		<meta http-equiv="content-type" content="text/html; charset=utf-8">
		<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 ? "blue" : "red";
				li.appendChild(document.createTextNode(desc));
				var list = document.getElementById("results");
				if (!list) {
					list = document.createElement("div");
					document.body.appendChild(list);
				}
				list.appendChild(li);
			}
		</script>
	</head>
	<body>
		<h1 id="title">Algorithmen und Datenstrukturen</h1>
		<h3>Praktikum 4 - Lars Nielsen, Patrick Nagorski, Niklas Gerwens</h3>
		<hr />
		<h2>Aufgabe 2</h2>
		<p>
			Gegeben sei eine Sequenz $S$ von ganzen Zahlen. Zu berechnen ist ein Index $i$ f&uuml;r
			den gilt, dass die Summe der Elemente links gleich der Summe der Elemente rechts von
			$i$ ist: $\sum\nolimits_{0 \leq j < i} S[j] = \sum\nolimits_{i < k < |S|} S[k]$ <br />
			Der R&uuml;ckgabewert $-1$ zeigt an, dass es keinen solchen Index gibt. Die Implementierung soll
			in $O(|S|)$ laufen und h&ouml;chstens $O(|S|)$ zus&auml;tzlichen Speicherbedarf haben.
		</p>
		<h3>Implementierung</h3>
		<!-- In diesem Element wird der Inhalt des scripts mit der ID ad-4-2-results angezeigt -->
		<pre id="ad-4-2-source"></pre>
		<h3>Testergebnisse</h3>
		<div id="ad-4-2-results"></div>
		<script id="ad-4-2-code">
			var counter_4_2 = 0;

			function mittelpunkt(seq) {

				counter_4_2 = 0;

				if(seq.length < 3) {
					return -1;
				}

				var left_sum = seq[0];

				var right_sum = 0;

				for (var j = 2; j < seq.length; j++) {
					right_sum += seq[j];
					counter_4_2++;
				}

				var i = 1;


				while (i < seq.length - 2) {

					left_sum += seq[i];

					right_sum -= seq[i+1];

					i++;

					if (left_sum == right_sum) {
						return i;
					}

					counter_4_2++;
				}

				if (left_sum == right_sum) {
					return i;
				}

				return -1;
			}

			// Tests
			assert(mittelpunkt([6, 5, 6]) === 1, "mittelpunkt([6, 5, 6]) = 1");
			assert(mittelpunkt([6, 6]) === -1, "mittelpunkt([6, 6]) = -1");
			assert(mittelpunkt([2, 3, 4, 5]) === 2, "mittelpunkt([2, 3, 4, 5]) = 2");
			assert(mittelpunkt([2, 3, 8, 4, 2, 8, 3]) === 3, "mittelpunkt([2, 3, 8, 4, 2, 8, 3]) = 3");
			assert(mittelpunkt([6, 2, 4, 1, 1, 3, 2, 6]) === 3, "mittelpunkt([6, 2, 4, 1, 1, 3, 2, 6]) = 3");
			assert(mittelpunkt([6, 2, 4, 1, 3, 2, 6]) === -1, "mittelpunkt([6, 2, 4, 1, 3, 2, 6]) = -1");
			assert(mittelpunkt([]) === -1, "Bei einer leeren Sequenz wird -1 zurückgegeben.");

			// Experimente
			var seq = [];
			var ad_4_2_data = [];
			for (var i = 1; i < 101; i++) {
				seq.push(Math.floor(Math.random()*21)-10);
				mittelpunkt(seq);
				ad_4_2_data.push({experiment: seq.length, value: counter_4_2});
			};
		</script>
		<!-- dieser Code zeigt die Implementierung und die Tests an -->
		<script>$('pre#ad-4-2-source').html($('#ad-4-2-code').html())</script>

		<h3>Experimente</h3>
		<h4>Laufzeiten</h4>
		<p>
			Die Grafik zeigt das Laufzeitverhalten, welches $O(|S|)$ betr&auml;gt.
			Die Ausschl&auml;ge nach unten repr&auml;sentieren Arrays, bei denen
			ein Mittelpunkt gefunden wurden konnte. Dies ist f&uuml;r die Worst-
			Case-Betrachtung nicht relevant, da wir in dem Fall direkt den Index
			zur&uuml;ckgeben. Interessanter sind dagegen die linear steigend
			abgebildeten Worst-Case-Szenarien (es konnte kein Index gefunden werden).
		</p>
		<div id="ad-4-2-counter" style="height: 250px;"></div>
		<script>
			new Morris.Line({
				element: 'ad-4-2-counter', // ID of the element in which to draw the chart.
				parseTime: false, // do values relate to dates (time)?
				data: ad_4_2_data, // Chart data records -- each entry in this array corresponds to a point on the chart.
				xkey: 'experiment', // The name of the data record attribute that contains x-values.
				ykeys: ['value'], // A list of names of data record attributes that contain y-values.
				labels: ['Laufzeit'] // Labels for the ykeys -- will be displayed when you hover over the chart.
			});
		</script>
		<hr />
		<div>
			<p>
				<a href="index.html">Zur&uuml;ck</a> |
				<a href="adp4_1.html">Aufgabe 1</a> |
				Aufgabe 2 |
				<a href="adp4_3.html">Aufgabe 3</a> |
				<a href="adp4_4.html">Aufgabe 4</a>
			</p>
		</div>
	</body>
</html>
	<!DOCTYPE html>
	<html>
	<head>
	<title>ADP4 - Aufgabe 2</title>
	<!-- morris graph lib -->
	<meta http-equiv="content-type" content="text/html; charset=utf-8">
	<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 ? "blue" : "red";
	li.appendChild(document.createTextNode(desc));
	var list = document.getElementById("results");
	if (!list) {
	list = document.createElement("div");
	document.body.appendChild(list);
	}
	list.appendChild(li);
	}
	</script>
	</head>
	<body>
	<h1 id="title">Algorithmen und Datenstrukturen</h1>
	<h3>Praktikum 4 - Lars Nielsen, Patrick Nagorski, Niklas Gerwens</h3>
	<hr />
	<h2>Aufgabe 2</h2>
	<p>
	Gegeben sei eine Sequenz $S$ von ganzen Zahlen. Zu berechnen ist ein Index $i$ für
	den gilt, dass die Summe der Elemente links gleich der Summe der Elemente rechts von
	$i$ ist: $\sum\nolimits_{0 \leq j < i} S[j] = \sum\nolimits_{i < k < \|S\|} S[k]$ <br />
	Der Rückgabewert $-1$ zeigt an, dass es keinen solchen Index gibt. Die Implementierung soll
	in $O(\|S\|)$ laufen und höchstens $O(\|S\|)$ zusätzlichen Speicherbedarf haben.
	</p>
	<h3>Implementierung</h3>
	<!-- In diesem Element wird der Inhalt des scripts mit der ID ad-4-2-results angezeigt -->
	<pre id="ad-4-2-source"></pre>
	<h3>Testergebnisse</h3>
	<div id="ad-4-2-results"></div>
	<script id="ad-4-2-code">
	var counter_4_2 = 0;

	function mittelpunkt(seq) {

	counter_4_2 = 0;

	if(seq.length < 3) {
	return -1;
	}

	var left_sum = seq[0];

	var right_sum = 0;

	for (var j = 2; j < seq.length; j++) {
	right_sum += seq[j];
	counter_4_2++;
	}

	var i = 1;


	while (i < seq.length - 2) {

	left_sum += seq[i];

	right_sum -= seq[i+1];

	i++;

	if (left_sum == right_sum) {
	return i;
	}

	counter_4_2++;
	}

	if (left_sum == right_sum) {
	return i;
	}

	return -1;
	}

	// Tests
	assert(mittelpunkt([6, 5, 6]) === 1, "mittelpunkt([6, 5, 6]) = 1");
	assert(mittelpunkt([6, 6]) === -1, "mittelpunkt([6, 6]) = -1");
	assert(mittelpunkt([2, 3, 4, 5]) === 2, "mittelpunkt([2, 3, 4, 5]) = 2");
	assert(mittelpunkt([2, 3, 8, 4, 2, 8, 3]) === 3, "mittelpunkt([2, 3, 8, 4, 2, 8, 3]) = 3");
	assert(mittelpunkt([6, 2, 4, 1, 1, 3, 2, 6]) === 3, "mittelpunkt([6, 2, 4, 1, 1, 3, 2, 6]) = 3");
	assert(mittelpunkt([6, 2, 4, 1, 3, 2, 6]) === -1, "mittelpunkt([6, 2, 4, 1, 3, 2, 6]) = -1");
	assert(mittelpunkt([]) === -1, "Bei einer leeren Sequenz wird -1 zurückgegeben.");

	// Experimente
	var seq = [];
	var ad_4_2_data = [];
	for (var i = 1; i < 101; i++) {
	seq.push(Math.floor(Math.random()*21)-10);
	mittelpunkt(seq);
	ad_4_2_data.push({experiment: seq.length, value: counter_4_2});
	};
	</script>
	<!-- dieser Code zeigt die Implementierung und die Tests an -->
	<script>$('pre#ad-4-2-source').html($('#ad-4-2-code').html())</script>

	<h3>Experimente</h3>
	<h4>Laufzeiten</h4>
	<p>
	Die Grafik zeigt das Laufzeitverhalten, welches $O(\|S\|)$ beträgt.
	Die Ausschläge nach unten repräsentieren Arrays, bei denen
	ein Mittelpunkt gefunden wurden konnte. Dies ist für die Worst-
	Case-Betrachtung nicht relevant, da wir in dem Fall direkt den Index
	zurückgeben. Interessanter sind dagegen die linear steigend
	abgebildeten Worst-Case-Szenarien (es konnte kein Index gefunden werden).
	</p>
	<div id="ad-4-2-counter" style="height: 250px;"></div>
	<script>
	new Morris.Line({
	element: 'ad-4-2-counter', // ID of the element in which to draw the chart.
	parseTime: false, // do values relate to dates (time)?
	data: ad_4_2_data, // Chart data records -- each entry in this array corresponds to a point on the chart.
	xkey: 'experiment', // The name of the data record attribute that contains x-values.
	ykeys: ['value'], // A list of names of data record attributes that contain y-values.
	labels: ['Laufzeit'] // Labels for the ykeys -- will be displayed when you hover over the chart.
	});
	</script>
	<hr />
	<div>
	<p>
	<a href="index.html">Zurück</a> \|
	<a href="adp4_1.html">Aufgabe 1</a> \|
	Aufgabe 2 \|
	<a href="adp4_3.html">Aufgabe 3</a> \|
	<a href="adp4_4.html">Aufgabe 4</a>
	</p>
	</div>
	</body>
	</html>