====== Lösungsvorschlag ======

==== Aufgabe 1 (Wissensfragen) ====
**a)**
  * Bei 3 Arbeitspaketen wird ein Speedup von 1.8 gemessen.
  * Auch "bei 2 Arbeitspaketen wird ein Speedup von 1.5 gemessen." ist richtig.
<note tip>
s(n) = 54 s und p(n) = 2 * 6 + 18 s = 30 s => Sp(n) = 54 / 30
</note>

**b)**
  * Das Schalten von Transitionen ist atomar.
  * Keine Belegung des Petri-Netzes ist im Erreichbarkeitsgraph doppelt vorhanden.

**c)**
  * 1. & 4. 


==== Aufgabe 2 (Longest Common Subsequence) ====

<code java>
public char[] lcs() throws Exception {
	for (int i = 0; i < threads; i++) { // Anfang der for-Schleife #1
		final int threadId = i;
		queues[threadId] = new LinkedBlockingQueue<Object>();
		// TODO: 1
		int step = (columns - 1) / threads;
		final int start = 1 + i * step;
		final int end = (i == threads - 1) ? columns - 1 : start + step;

		Thread t = new Thread() { public void run() { try {
			for (int row = 1; row < rows; row++) {
				// TODO: 2
				if (threadId > 0) {
					queues[threadId - 1].take();
				}
				for (int c = start; c < end; c++) { // fuelle Zeile des Blocks
					table[row][c] = calcValue(row, c);
				}
				queues[threadId].put(READY);
			}
		} catch (InterruptedException e) {}}};
		t.start();
	} // Ende der for-Schleife #1
	// TODO: 3
	for (int i = 1; i < rows; ++i) {
		queues[threads - 1].take();
	}
	return readMatrix();
}
</code>

==== Aufgabe 3 (Fehlersuche) ====
**a)**
Stichwortartige Problembeschreibung:
Klasse Error1 hat eigene Kopie von finished im Cache und bekommt möglicherweise die globale Änderung nicht mit.

Beheben Sie den Fehler:
<code java>static volatile boolean finished = false;</code>

**b)**
Stichwortartige Problembeschreibung:
Da if-Abfrage nicht synchronisiert, wird latch möglicherweise zweimal dekrementiert und Haupt-Thread schläft ewig.

Beheben Sie den Fehler:
<code java>synchronized(Error2.class) { /* if-Abfrage */ }</code>

**c)**
Stichwortartige Problembeschreibung:
In foo() wird run-Methode direkt aufgerufen!

Beheben Sie den Fehler:

Zeile 15:
<code java>thread2.start();</code>

==== Aufgabe 4 (Monte-Carlo-Simulation) ====

<code java>
import java.util.Random;
import java.util.concurrent.*;
public class MonteCarlo {
	
	public static double pi(int tasks, int globalCnt) throws Exception {
		ExecutorService exec = Executors.newFixedThreadPool(tasks);
		Future<Integer>[] hitArray = new Future[tasks];
		// TODO: 1
		for(int i = 0; i < tasks; i++){ 
   			hitArray[i] = exec.submit(new MonteCarloTask(i, tasks, globalCnt));
		}
		int hits = 0;
		// TODO: 2
		for (int i = 0; i < tasks; i ++){
    		hits += hitArray[i].get();
		}
		exec.shutdown();
		return (((double) hits) / globalCnt) * 4;
	} // Ende pi
	
	static class MonteCarloTask implements Callable<Integer> {
		private Random rnd;
		private int id;
		private int tasks;
		private int globalCnt;
		
		public MonteCarloTask(int id, int tasks, int globalCnt) {
			this.id = id; // des Task-Objekts und des 1. simulierten Punktes
			this.tasks = tasks;
			this.globalCnt = globalCnt;
			this.rnd = new Random();
		}
		
		private double nextDouble() {
			return rnd.nextDouble();
		}
		
		public Integer call() {
			int mySum = 0;
			// TODO: 3
			for (int i = id; i < globelCnt; i += tasks){
			    double x = nextDouble();
			    double y = nextDouble();
			    x = x * x;
			    y = y * y;
    			if(x + y <= 1) mySum++;
			}
			return mySum;
		} // Ende call
	} // Ende class MonteCarloTask
} // Ende class MonteCarlo
</code>

==== Aufgabe 5 (gerichteter Graph) ====

**a)**
<code>
def isInPar: (V, List[V]) => Boolean = (v, vs) =>
    // .toList. optional
    vs.par.filter(_ == v).toList.nonEmpty
</code>

**b)**
<code>
def find: (V, G) => List[V] = (v, g) =>
    for (x <- g; if( isIn(v, x.out)) ) yield x.v
</code>
Alternativ:
<code>
def find: (V, G) => List[V] = (x, a) =>
    a.filter { a2 => isIn(x)(a2.out) }.map { a2 => a2.out }
</code>

==== Aufgabe 6 (Lauflängenkodierung) ====

**a)**
<code>
def encodeHead: Stream[Char] => ((Char, Int), Stream[Char]) = cs => {
    val h = cs.head
    ((h, cs.takeWhile(_ == h).length), cs.dropWhile( _ == h))
}
</code>

**b)**
<code>
def encode: Stream[Char] => Stream[(Char, Int)] = cs =>
	if (cs.isEmpty) Stream.empty
	else encodeHead(cs)._1#:: encode(encodeHead(cs)._2)
</code>
**c)**
<code>
def decode: List[(Char, Int)] => List[Char] = cs =>
	cs.foldRight( List[Char]() ) ( (e, ls) => List.fill(e._2)(e._1) ::: ls)
</code>