java-oop-exam-dynamicprogramming

Java OOP exam task (FernUniversität in Hagen, 2025) – implementation of the Shortest Common Supersequence (SCS) using dynamic programming and memoization. The exercise belongs to FernUniversität in Hagen, but the solution code was written by me (Michael Kain) and achieved full marks in the programming section.

#OOP2025 – Task 5: Dynamische Programmierung (FernUniversität in Hagen)

This repository contains my Java solution for the fifth OOP2025 exam task from the FernUniversität in Hagen.
The goal was to implement a Dynamic Programming algorithm to find the Shortest Common Supersequence (SCS) between two strings.
The task demonstrates core principles of memoization and efficient problem solving using recursion and tabulation.

---

#Task Screenshot

This screenshot shows the original dynamic programming task from the FernUniversität in Hagen (Course 63016).
The task itself belongs to the FernUniversität in Hagen, but the code implementation is entirely my own (Michael Kain).
It received full marks as part of the final OOP2025 practical assessment.

---

#Evaluation Screenshot

Official evaluation sheet confirming full points in all five OOP programming tasks.
Included for reference and transparency.

---

#Java Implementation

import java.util.Arrays;

/**
 * FernUniversität in Hagen – OOP2025 Task 5: Dynamic Programming
 * Shortest Common Supersequence (SCS)
 * Solution written by Michael Kain
 */
public class ShortestCommonSupersequence {

    // Calculates the length of the shortest common supersequence using DP (Memoization)
    public static int shortestCommonSuperSequence(String x, String y) {
        int m = x.length();
        int n = y.length();

        int[][] memo = new int[m + 1][n + 1];

        // Fill DP table from bottom-up
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0)
                    memo[i][j] = j;
                else if (j == 0)
                    memo[i][j] = i;
                else if (x.charAt(i - 1) == y.charAt(j - 1))
                    memo[i][j] = 1 + memo[i - 1][j - 1];
                else
                    memo[i][j] = 1 + Math.min(memo[i - 1][j], memo[i][j - 1]);
            }
        }

        return memo[m][n];
    }

    public static void main(String[] args) {
        String x = "ABBBBBABBABBBBBABBBBABBBABBABABBBBAB";
        String y = "CDCCCCDCCCCDCCCBBCDACCDBBBCDACDDABCD";

        int result = shortestCommonSuperSequence(x, y);

        System.out.println("Länge von String x: " + x.length());
        System.out.println("Länge von String y: " + y.length());
        System.out.println("Länge der kürzesten gemeinsamen Obersequenz (SCS): " + result);
    }
}