From 1c6c9657a6432fc1d7069ddf8dd106f7a614fbed Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 25 Dec 2018 11:12:42 -0600
Subject: Longest Subsequence (betwee 2) done!

This one is pretty tricky. I solved it after reading online:
http://www.cs.umd.edu/~meesh/351/mount/lectures/lect25-longest-common-subseq.pdf
https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

To find a good test case that reveals the bug, I tried stress testing
(in commented out code), but the naive but correct algo is so
inefficient that I didn't have enough patience to let it finish. Anyway,
good practice of stress testing anyway.---
 AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java | 52 +++++++++++++++++------
 1 file changed, 40 insertions(+), 12 deletions(-)

(limited to 'AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java')

diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
index bdfa799..83de106 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
@@ -6,30 +6,58 @@ class LCS2Test {
 
     @Test
     void test() {
-        int[] a = {2, 7, 5};
-        int[] b = {2, 5};
-        assertEquals(2, LCS2.lcs2(a,b));
+        int[] a = { 2, 7, 5 };
+        int[] b = { 2, 5 };
+        assertEquals(2, LCS2.lcs2(a, b));
+        assertEquals(2, LCS2.third_lcs2(a, b));
+        assertEquals(2, LCS2.alt_lcs2(a, b, 3, 2));
     }
 
     @Test
     void test1() {
-        int[] a = {7};
-        int[] b = {1, 2, 3, 4};
-        assertEquals(0, LCS2.lcs2(a,b));
+        int[] a = { 7 };
+        int[] b = { 1, 2, 3, 4 };
+        assertEquals(0, LCS2.lcs2(a, b));
+        assertEquals(0, LCS2.third_lcs2(a, b));
+        assertEquals(0, LCS2.alt_lcs2(a, b, 1, 4));
     }
 
     @Test
     void test2() {
-        int[] a = {2, 7, 8, 3};
-        int[] b = {5, 2, 8, 7};
-        assertEquals(2, LCS2.lcs2(a,b));
+        int[] a = { 2, 7, 8, 3 };
+        int[] b = { 5, 2, 8, 7 };
+        assertEquals(2, LCS2.lcs2(a, b));
+        assertEquals(2, LCS2.third_lcs2(a, b));
+        assertEquals(2, LCS2.alt_lcs2(a, b, 4, 4));
     }
 
     @Test
     void test3() {
-        int[] a = {1, 2, 3, 4, 5, 6, 7};
-        int[] b = {1, 2, 8, 4, 5, 6};
-        assertEquals(5, LCS2.lcs2(a,b));
+        int[] a = { 1, 2, 3, 4, 5, 6, 7 };
+        int[] b = { 1, 2, 8, 4, 5, 6 };
+        assertEquals(5, LCS2.lcs2(a, b));
+        assertEquals(5, LCS2.third_lcs2(a, b));
+        assertEquals(5, LCS2.alt_lcs2(a, b, 7, 6));
+    }
+
+    @Test
+    void test4() {
+        int[] a = { 1, 9, 2, 5, 5, 5, 8, 3, 5, 11, 0, 2, 4, 1, 7, 4, 5, 9, 2, 4, 0, 3, 1, 5, 8, 3, 5, 9, 7, 8, 4, 5, 6,
+                7 };
+        int[] b = { 6, 3, 8, 3, 1, 8, 3, 5, 0, 9, 6, 8, 3, 5, 7, 9, 1, 4, 7, 9, 3, 5, 9, 0, 1, 4, 2, 7, 5, 8, 9, 3, 5,
+                6, 1, 6, 3, 1, 6, 7, 3 };
+        assertEquals(16, LCS2.lcs2(a, b));
+        assertEquals(17, LCS2.third_lcs2(a, b));
+//        assertEquals(5, LCS2.alt_lcs2(a, b, a.length, b.length));
+    }
+
+    @Test
+    void test5() {
+        int[] a = { 2, 4, 3, 3 };
+        int[] b = { 1, 4, 3 };
+        assertEquals(2, LCS2.lcs2(a, b));
+        assertEquals(2, LCS2.third_lcs2(a, b));
+//        assertEquals(5, LCS2.alt_lcs2(a, b, a.length, b.length));
     }
 
 }
-- 
cgit v1.2.3