Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java
===================================================================
--- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java	(revision 1558)
+++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/MatrixEntry.java	(revision 1558)
@@ -0,0 +1,27 @@
+package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms;
+
+public class MatrixEntry {
+	private float score;
+	private MatrixEntry previous;
+	
+	public MatrixEntry(float score, MatrixEntry previous)	{
+		this.score = score;
+		this.previous = previous;
+	}
+	
+	public MatrixEntry() {
+	}
+
+	public float getScore() {
+		return score;
+	}
+	public void setScore(float score) {
+		this.score = score;
+	}
+	public MatrixEntry getPrevious() {
+		return previous;
+	}
+	public void setPrevious(MatrixEntry previous) {
+		this.previous = previous;
+	}
+}
Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java
===================================================================
--- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java	(revision 1557)
+++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java	(revision 1558)
@@ -25,4 +25,12 @@
 		this.signature = signature;
 	}
+	
+	public void printSequence()
+	{	
+		for (int i = 0; i < sequence.length; i++) {
+			System.out.format("%4d", sequence[i]);
+		}
+		System.out.println();
+	}
 
 }
Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java
===================================================================
--- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java	(revision 1557)
+++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java	(revision 1558)
@@ -162,5 +162,5 @@
 	 * Get the maximum value in the score matrix.
 	 */
-	private double getMaxScore() {
+	public double getMaxScore() {
 		double maxScore = 0;
 
@@ -184,4 +184,6 @@
 	}
 
+	
+	
 	/**
 	 * TODO: Iterative Version!!! Output the local alignments ending in the (i,
@@ -272,5 +274,4 @@
 			}
 		}
-		// Note: empty alignments are not printed.
 	}
 
Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java
===================================================================
--- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java	(revision 1558)
+++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java	(revision 1558)
@@ -0,0 +1,250 @@
+package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import de.ugoe.cs.autoquest.tasktrees.alignment.substitution.SubstitutionMatrix;
+
+public class SmithWatermanRepeated implements Alignment {
+
+	/**
+	 * The first input
+	 */
+	private int[] input1;
+
+	/**
+	 * The second input String
+	 */
+	private int[] input2;
+
+	/**
+	 * The lengths of the input
+	 */
+	private int length1, length2;
+
+	/**
+	 * The score matrix. The true scores should be divided by the normalization
+	 * factor.
+	 */
+	private MatrixEntry[][] matrix;
+
+	
+	
+	private float scoreThreshold;
+
+	/**
+	 * Substitution matrix to calculate scores
+	 */
+	private SubstitutionMatrix submat;
+
+	public SmithWatermanRepeated(int[] input1, int[] input2, SubstitutionMatrix submat,float threshold) {
+		this.input1 = input1;
+		this.input2 = input2;
+		length1 = input1.length;
+		length2 = input2.length;
+		this.submat = submat;
+
+		//System.out.println("Starting SmithWaterman algorithm with a "
+		//		+ submat.getClass() + " Substitution Matrix: " + submat.getClass().getCanonicalName());
+		this.scoreThreshold = threshold;
+		
+		matrix = new MatrixEntry[length1+2][length2+1];
+		
+		for (int i = 0; i <= length1; i++) {
+			for(int j = 0; j< length2; j++) {
+				matrix[i][j] = new MatrixEntry();
+			}
+		}
+	
+
+		buildMatrix();
+	}
+
+	/**
+	 * Compute the similarity score of substitution The position of the first
+	 * character is 1. A position of 0 represents a gap.
+	 * 
+	 * @param i
+	 *            Position of the character in str1
+	 * @param j
+	 *            Position of the character in str2
+	 * @return Cost of substitution of the character in str1 by the one in str2
+	 */
+	private float similarity(int i, int j) {
+		if (i == 0 || j == 0) {
+			// it's a gap 
+			return submat.getGapPenalty();
+		}
+		// System.out.println("Diag letters: " + input1[i-1] + " " +
+		// input2[j-1]);
+		// return (input1[i - 1] == input2[j - 1]) ? MATCH_SCORE :
+		// MISMATCH_SCORE;
+		return submat.getDistance(input1[i - 1], input2[j - 1]);
+	}
+
+	/**
+	 * Build the score matrix using dynamic programming. Note: The indel scores
+	 * must be negative. Otherwise, the part handling the first row and column
+	 * has to be modified.
+	 */
+	private void buildMatrix() {
+		if (submat.getGapPenalty() >= 0) {
+			throw new Error("Indel score must be negative");
+		}
+		
+
+		// base case
+		matrix[0][0].setScore(0);
+		matrix[0][0].setPrevious(null); // starting point
+
+		// the first column
+		for (int j = 1; j < length2; j++) {
+			matrix[0][j].setScore(0);
+			matrix[0][j].setPrevious(matrix[0][j-1]);
+			
+		}
+		
+		
+		
+		for (int i = 1; i <= length1; i++) {
+		
+			// Formula for first row:
+			// F(i,0) = max { F(i-1,0), F(i-1,j)-T  j=1,...,m
+			
+			float firstRowLeftScore = matrix[i-1][0].getScore();
+			float tempMax = matrix[i-1][1].getScore();
+			
+			//position of the maximal score of the previous row
+			int maxRowIndex = 1;
+			
+			for(int j = 2; j < length2;j++) {
+				if(matrix[i-1][j].getScore() > tempMax) {
+					tempMax = matrix[i-1][j].getScore();
+					maxRowIndex = j;
+				}
+			}
+			
+			tempMax -= scoreThreshold;
+			matrix[i][0].setScore(Math.max(firstRowLeftScore, tempMax));
+			
+			
+			for (int j = 1; j < length2; j++) {
+				float diagScore = matrix[i - 1][j - 1].getScore() + similarity(i, j);
+				float upScore = matrix[i][j - 1].getScore() + similarity(0, j);
+				float leftScore = matrix[i - 1][j].getScore() + similarity(i, 0);
+
+				matrix[i][j].setScore(Math.max(diagScore,Math.max(upScore, Math.max(leftScore,matrix[i][0].getScore()))));
+
+				// find the directions that give the maximum scores.
+				// Multiple directions are ignored TODO
+				if (diagScore == matrix[i][j].getScore()) {
+					matrix[i][j].setPrevious(matrix[i-1][j-1]);
+				}
+				if (leftScore == matrix[i][j].getScore()) {
+					matrix[i][j].setPrevious(matrix[i-1][j]);
+				}
+				if (upScore == matrix[i][j].getScore()) {
+					matrix[i][j].setPrevious(matrix[i][j-1]);
+				}
+				if (matrix[i][0].getScore() == matrix[i][j].getScore()) {
+					matrix[i][j].setPrevious(matrix[i-1][maxRowIndex]);
+				}
+			}
+		}
+	}
+
+	/**
+	 * Get the maximum value in the score matrix.
+	 */
+	public double getMaxScore() {
+		double maxScore = 0;
+
+		// skip the first row and column
+		for (int i = 1; i <= length1; i++) {
+			for (int j = 1; j < length2; j++) {
+				if (matrix[i][j].getScore() > maxScore) {
+					maxScore = matrix[i][j].getScore();
+				}
+			}
+		}
+
+		return maxScore;
+	}
+
+	/**
+	 * Get the alignment score between the two input strings.
+	 */
+	public double getAlignmentScore() {
+		return getMaxScore();
+	}
+
+	
+	
+	
+	/**
+	 * given the bottom right corner point trace back the top left conrner. at
+	 * entry: i, j hold bottom right (end of Aligment coords) at return: hold
+	 * top left (start of Alignment coords)
+	 */
+	private int[] traceback(int i, int j) {
+
+		return null;
+	}
+
+	
+	/**
+	 * print the dynmaic programming matrix
+	 */
+	public void printDPMatrix() {
+		System.out.print("          ");
+		for (int i = 1; i <= length1; i++)
+			System.out.format("%5d", input1[i - 1]);
+		System.out.println();
+		for (int j = 0; j < length2; j++) {
+			if (j > 0)
+				System.out.format("%5d ",input2[j - 1]);
+			else{
+				System.out.print("      ");
+			}
+			for (int i = 0; i <= length1; i++) {
+				System.out.format("%4.1f ",matrix[i][j].getScore());
+			}
+			System.out.println();
+		}
+	}
+
+	/**
+	 * Return a set of Matches identified in Dynamic programming matrix. A match
+	 * is a pair of subsequences whose score is higher than the preset
+	 * scoreThreshold
+	 **/
+	public List<Match> getMatches() {
+		ArrayList<Match> matchList = new ArrayList();
+		int fA = 0, fB = 0;
+		// skip the first row and column, find the next maxScore after
+		// prevmaxScore
+		for (int i = 1; i <= length1; i++) {
+			for (int j = 1; j <= length2; j++) {
+				if (matrix[i][j].getScore() > scoreThreshold
+						&& matrix[i][j].getScore() > matrix[i - 1][j - 1].getScore()
+						&& matrix[i][j].getScore() > matrix[i - 1][j].getScore()
+						&& matrix[i][j].getScore() > matrix[i][j - 1].getScore()) {
+					if (i == length1 || j == length2
+							|| matrix[i][j].getScore() > matrix[i + 1][j + 1].getScore()) {
+						// should be lesser than prev maxScore
+						fA = i;
+						fB = j;
+						int[] f = traceback(fA, fB); // sets the x, y to
+														// startAlignment
+														// coordinates
+						System.out.println(f[0] + " " + i + " " + f[1] + " "
+								+ j + " " + matrix[i][j].getScore());
+						// TODO Add matches to matchList
+					}
+				}
+			}
+		}
+		return matchList;
+	}
+
+}
Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/ObjectDistanceSubstitionMatrix.java
===================================================================
--- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/ObjectDistanceSubstitionMatrix.java	(revision 1557)
+++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/ObjectDistanceSubstitionMatrix.java	(revision 1558)
@@ -30,11 +30,11 @@
 	
 	public ObjectDistanceSubstitionMatrix(
-			SymbolMap<ITaskInstance, ITask> uniqueTasks) {
+			SymbolMap<ITaskInstance, ITask> uniqueTasks,float positiveThreshold) {
 		this.uniqueTasks = uniqueTasks;
+		this.positiveThreshold = positiveThreshold;
 		idmapping = new HashMap<Integer, Integer>();
 		matrix = new TriangleMatrix(uniqueTasks.size()+1);
 		gapPenalty = -10;
-		//Todo: Calculate this value (the mean distance between every element) before
-		positiveThreshold =7;
+		
 	}
 
@@ -47,5 +47,8 @@
 	public void generate() {
 		int index = 0;
-		float meandistance = 0;
+		//TODO We need to determine this parameter before generating the matrix..
+		float meandistance = 18;
+		//TODO We need to determine this parameter before generating the matrix..
+		float maxDistance =34;
 		for (Iterator<ITaskInstance> it = uniqueTasks.getSymbols().iterator(); it
 				.hasNext();) {
@@ -87,15 +90,23 @@
 					tempindex2 = idmapping.get(eti2.getTask().getId());
 				}
-				float distance = AlignmentHelpers.distanceBetween(first, second);
-				meandistance += distance;
+				float distance = -1*AlignmentHelpers.distanceBetween(first, second);
+				//meandistance += distance;
 			
-				if (distance > positiveThreshold) {
-					distance = -1*distance;
+				if(distance > maxDistance){
+					maxDistance = distance;
 				}
+				
+				distance += 5;
+				
+				//if (distance < positiveThreshold) {
+				//	distance = -1*distance;
+				//}
+				
 				matrix.set(tempindex1, tempindex2,distance);
 				
 			}
 		}
-		System.out.println(meandistance/(uniqueTasks.size()*uniqueTasks.size()));
+		//System.out.println("ObjectDistanceMatrix: MaxDistance: " + maxDistance);
+		//System.out.println(meandistance/(uniqueTasks.size()*uniqueTasks.size()));
 		//System.out.println(idmapping.toString());
 		//System.out.println(matrix.toString());
@@ -104,9 +115,12 @@
 		
 	}
+	
+	public String toString(){
+		return matrix.toString();
+	}
 
 	@Override
 	public float getDistance(int taskId1, int taskId2) {
 		//System.out.println("Taskid1: " + taskId1 + " Taskid2: " + taskId2 + " Idmapping1: " + idmapping.get(taskId1) + " Idmapping2: " + idmapping.get(taskId2));
-		
 		return matrix.get(idmapping.get(taskId1),idmapping.get(taskId2));
 	}
Index: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/TriangleMatrix.java
===================================================================
--- branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/TriangleMatrix.java	(revision 1557)
+++ branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/substitution/TriangleMatrix.java	(revision 1558)
@@ -33,8 +33,8 @@
 			for(int j = 0; j< size; j++) {
 				if(i<j) {
-					result = result + (this.get(i,j) + " ");
+					result = result + String.format("%+4.1f",this.get(i,j));
 				}
 				else {
-					result = result + ("    ");
+					result = result + ("      ");
 				}
 			}
