Beginner-Friendly and Practical Courses

Longest Common Subsequence

QUESTION 1: Write a function to find the length of the longest common subsequence between two sequences. E.g. Given the strings "serendipitous" and "precipitation", the longest common subsequence is "reipito" and its length is 7.

A "sequence" is a group of items with a deterministic ordering. Lists, tuples and ranges are some common sequence types in Python.

A "subsequence" is a sequence obtained by deleting zero or more elements from another sequence. For example, "edpt" is a subsequence of "serendipitous".

General case

Test cases

General case (string)
General case (list)
No common subsequence
One is a subsequence of the other
One sequence is empty
Both sequences are empty
Multiple subsequences with same length
1. “abcdef” and “badcfe”

Longest common subsequence test cases:

T0 = {
    'input': {
        'seq1': 'serendipitous',
        'seq2': 'precipitation'
    },
    'output': 7
}

T1 = {
    'input': {
        'seq1': [1, 3, 5, 6, 7, 2, 5, 2, 3],
        'seq2': [6, 2, 4, 7, 1, 5, 6, 2, 3]
    },
    'output': 5
}

T2 = {
    'input': {
        'seq1': 'longest',
        'seq2': 'stone'
    },
    'output': 3
}

T3 = {
    'input': {
        'seq1': 'asdfwevad',
        'seq2': 'opkpoiklklj'
    },
    'output': 0
}

T4 = {
    'input': {
        'seq1': 'dense',
        'seq2': 'condensed'
    },
    'output': 5
}

T5 = {
    'input': {
        'seq1': '',
        'seq2': 'opkpoiklklj'
    },
    'output': 0
}

T6 = {
    'input': {
        'seq1': '',
        'seq2': ''
    },
    'output': 0
}

T7 = {
    'input': {
        'seq1': 'abcdef',
        'seq2': 'badcfe'
    },
    'output': 3
}

lcq_tests = [T0, T1, T2, T3, T4, T5, T6, T7]

Recursive Solution

Create two counters idx1 and idx2 starting at 0. Our recursive function will compute the LCS of seq1[idx1:] and seq2[idx2:]
If seq1[idx1] and seq2[idx2] are equal, then this character belongs to the LCS of seq1[idx1:] and seq2[idx2:] (why?). Further the length this is LCS is one more than LCS of seq1[idx1+1:] and seq2[idx2+1:]

If not, then the LCS of seq1[idx1:] and seq2[idx2:] is the longer one among the LCS of seq1[idx1+1:], seq2[idx2:] and the LCS of seq1[idx1:], seq2[idx2+1:]

If either seq1[idx1:] or seq2[idx2:] is empty, then their LCS is empty.

Here's what the tree of recursive calls looks like:

Complexity Analysis

Worst case occurs when each time we have to try 2 subproblems i.e. when the sequences have no common elements.

Here's what the tree looks like in such a case (source - Techie Delight):

All the leaf nodes are (0, 0). Can you count the number of leaf nodes?

HINT: Count the number of unique paths from root to leaf. The length of each path is m+n and at each level there are 2 choices.

Based on the above can you infer that the time complexity is $O(2^{m+n})$.

Dynamic programming

Create a table of size (n1+1) * (n2+1) initialized with 0s, where n1 and n2 are the lengths of the sequences. table[i][j] represents the longest common subsequence of seq1[:i] and seq2[:j]. Here's what the table looks like (source: Kevin Mavani, Medium).

If seq1[i] and seq2[j] are equal, then table[i+1][j+1] = 1 + table[i][j]
If seq1[i] and seq2[j] are equal, then table[i+1][j+1] = max(table[i][j+1], table[i+1][j])

Verify that the complexity of the dynamic programming approach is $O(N1 * N2)$.

0-1 Knapsack Problem

Problem statement

You’re in charge of selecting a football (soccer) team from a large pool of players. Each player has a cost, and a rating. You have a limited budget. What is the highest total rating of a team that fits within your budget. Assume that there’s no minimum or maximum team size.

General problem statemnt:

Given n elements, each of which has a weight and a profit, determine the maximum profit that can be obtained by selecting a subset of the elements weighing no more than w.

Test cases:

Some generic test cases
All the elements can be included
None of the elements can be included
Only one of the elements can be included
???

Knapsack test cases:

test0 = {
    'input': {
        'capacity': 165,
        'weights': [23, 31, 29, 44, 53, 38, 63, 85, 89, 82],
        'profits': [92, 57, 49, 68, 60, 43, 67, 84, 87, 72]
    },
    'output': 309
}

test1 = {
    'input': {
        'capacity': 3,
        'weights': [4, 5, 6],
        'profits': [1, 2, 3]
    },
    'output': 0
}

test2 = {
    'input': {
        'capacity': 4,
        'weights': [4, 5, 1],
        'profits': [1, 2, 3]
    },
    'output': 3
}

test3 = {
    'input': {
        'capacity': 170,
        'weights': [41, 50, 49, 59, 55, 57, 60],
        'profits': [442, 525, 511, 593, 546, 564, 617]
    },
    'output': 1735
}

test4 = {
    'input': {
        'capacity': 15,
        'weights': [4, 5, 6],
        'profits': [1, 2, 3]
    },
    'output': 6
}

test5 = {
    'input': {
        'capacity': 15,
        'weights': [4, 5, 1, 3, 2, 5],
        'profits': [2, 3, 1, 5, 4, 7]
    },
    'output': 19
}

tests = [test0, test1, test2, test3, test4, test5]

Recursion

We'll write a recursive function that computes max_profit(weights[idx:], profits[idx:], capacity), with idx starting from 0.
If weights[idx] > capacity, the current element is cannot be selected, so the maximum profit is the same as max_profit(weights[idx+1:], profits[idx+1:], capacity).
Otherwise, there are two possibilities: we either pick weights[idx] or don't. We can recursively compute the maximum

A. If we don't pick weights[idx], once again the maximum profit for this case is max_profit(weights[idx+1:], profits[idx+1:], capacity)

B. If we pick weights[idx], the maximum profit for this case is profits[idx] + max_profit(weights[idx+1:], profits[idx+1:], capacity - weights[idx]
If weights[idx:] is empty, the maximum profit for this case is 0.

Here's a visualization of the recursion tree:

Verify that the time complexity of the recursive algorithm is $O(2^N)$

Dynamic Programming

Create a table of size (n+1) * (capacity+1) consisting of all 0s, where is n is the number of elements. table[i][c] represents the maximum profit that can be obtained using the first i elements if the maximum capacity is c.
We'll fill the table row by row and column by column. table[i][c] can be filled using some values in the row above it.
If weights[i] > c i.e. if the current element can is larger than capacity, then table[i][c] is simply equal to table[i-1][c] (since there's no way we can pick this element).
If weights[i] <= c then we have two choices: to either pick the current element or not. We can compare the maximum profit for both these options and pick the better one as the value of table[i][c].

A. If we don't pick the element with weight weights[i], then once again the maximum profit is table[i-1][c]

B. If we pick the element with weight weights[i], then the maximum profit is profits[i] + table[i-1][c-weights[i]], since we have used up some capacity.

Verify that the complexity of the dynamic programming solution is $O(N * W)$.

Longest common subsequence:

We can evaluate all the cases together using the evaluate_test_cases helper function.

from timeit import default_timer as timer
from textwrap import dedent
import math

def _str_trunc(data, size=100):
    data_str = str(data)
    if len(data_str) > size + 3:
        return data_str[:size] + '...'
    return data_str


def _show_test_case(test_case):
    inputs = test_case['input']

    if 'outputs' in test_case:
        expected_text = "Outputs"
        expected = test_case.get('outputs')
    else:
        expected_text = "Output"
        expected = test_case.get('output')

    print(dedent("""
    Input:
    {}

    Expected {}:
    {}
    """.format(_str_trunc(inputs), expected_text, _str_trunc(expected))))


def _show_result(result):
    actual_output, passed, runtime = result
    message = "\033[92mPASSED\033[0m" if passed else "\033[91mFAILED\033[0m"
    print(dedent("""
    Actual Output:
    {}

    Execution Time:
    {} ms

    Test Result:
    {}
    """.format(_str_trunc(actual_output), runtime, message)))


def evaluate_test_case(function, test_case, display=True):
    """Check if `function` works as expected for `test_case`"""
    inputs = test_case['input']

    if display:
        _show_test_case(test_case)

    start = timer()
    actual_output = function(**inputs)
    end = timer()

    runtime = math.ceil((end - start)*1e6)/1000
    if 'outputs' in test_case:
        passed = actual_output in test_case.get('outputs')
    else:
        passed = actual_output == test_case.get('output')

    result = actual_output, passed, runtime

    if display:
        _show_result(result)

    return result


def evaluate_test_cases(function, test_cases, error_only=False, summary_only=False):
    results = []
    for i, test_case in enumerate(test_cases):
        if not error_only:
            print("\n\033[1mTEST CASE #{}\033[0m".format(i))
        result = evaluate_test_case(function, test_case, display=False)
        results.append(result)
        if error_only and not result[1]:
            print("\n\033[1mTEST CASE #{}\033[0m".format(i))
        if not error_only or not result[1]:
            _show_test_case(test_case)
            _show_result(result)

    total = len(results)
    num_passed = sum([r[1] for r in results])
    print("\n\033[1mSUMMARY\033[0m")
    print("\nTOTAL: {}, \033[92mPASSED\033[0m: {}, \033[91mFAILED\033[0m: {}".format(
        total, num_passed, total - num_passed))
    return results

def lcq_recursive(seq1, seq2, idx1=0, idx2=0):
    # Check if either of the sequences is exhausted
    if idx1 == len(seq1) or idx2 == len(seq2):
        return 0
    
    # Check if the current characters are equal
    if seq1[idx1] == seq2[idx2]:
        return 1 + lcq_recursive(seq1, seq2, idx1+1, idx2+1)
    # Skip one element from each sequence
    else:
        return max(lcq_recursive(seq1, seq2, idx1+1, idx2), 
                   lcq_recursive(seq1, seq2, idx1, idx2+1))

evaluate_test_cases(lcq_recursive, lcq_tests)

%%time
lcq_recursive('seredipitous', 'precipitation')

%%time
lcq_recursive('Asdfsfafssess', 'oypiououuiuo')

def lcq_memoized(seq1, seq2):
    memo = {}
    
    def recurse(idx1, idx2):
        key = idx1, idx2
        
        if key in memo:
            return memo[key]
        
        if idx1 == len(seq1) or idx2 == len(seq2):
            memo[key] = 0
        elif seq1[idx1] == seq2[idx2]:
            memo[key] = 1 + recurse(idx1+1, idx2+1)
        else:
            memo[key] = max(recurse(idx1+1, idx2), 
                            recurse(idx1, idx2+1))
        return memo[key]
        
    return recurse(0, 0)

evaluate_test_cases(lcq_memoized, lcq_tests)

%%time
lcq_memoized('Asdfsfafssess', 'oypiououuiuo')

%%time
lcq_memoized('seredipitous', 'precipitation')

%%time
lcq_memoized('longest', 'stone')

Dynamic programming:

def lcq_dp(seq1, seq2):
    n1, n2 = len(seq1), len(seq2)
    results = [[0 for _ in range(n1+1)] for _ in range(n2+1)]
    for idx1 in range(1, n1+1):
        for idx2 in range(1, n2+1):
            if seq1[idx1] == seq2[idx2]:
                results[idx1][idx2] = 1 + results[idx1-1][idx2-1]
            else:
                results[idx1][idx2] = max(results[idx1-1][idx2], 
                                          results[idx1][idx2-1])
    return results[-1][-1]

evaluate_test_cases(lcq_dp, lcq_tests)

%%time
lcq_dp('Asdfsfafssess', 'oypiououuiuo')

%%time
lcq_dp('seredipitous', 'precipitation')

%%time
lcq_dp('longest', 'stone')

Knapsack Solutions

def max_profit_recursive(capacity, weights, profits, idx=0):
    if idx == len(weights):
        return 0
    if weights[idx] > capacity:
        return max_profit_recursive(capacity, weights, profits, idx+1)
    else:
        return max(max_profit_recursive(capacity, weights, profits, idx+1),
                   profits[idx] + max_profit_recursive(capacity-weights[idx], weights, profits, idx+1))

evaluate_test_cases(max_profit_recursive, tests)


TEST CASE #0

Input:
{'capacity': 165, 'weights': [23, 31, 29, 44, 53, 38, 63, 85, 89, 82], 'profits': [92, 57, 49, 68, 6...

Expected Output:
309


Actual Output:
309

Execution Time:
0.173 ms

Test Result:
PASSED


TEST CASE #1

Input:
{'capacity': 3, 'weights': [4, 5, 6], 'profits': [1, 2, 3]}

Expected Output:
0


Actual Output:
0

Execution Time:
0.004 ms

Test Result:
PASSED


TEST CASE #2

Input:
{'capacity': 4, 'weights': [4, 5, 1], 'profits': [1, 2, 3]}

Expected Output:
3


Actual Output:
3

Execution Time:
0.006 ms

Test Result:
PASSED


TEST CASE #3

Input:
{'capacity': 170, 'weights': [41, 50, 49, 59, 55, 57, 60], 'profits': [442, 525, 511, 593, 546, 564,...

Expected Output:
1735


Actual Output:
1735

Execution Time:
0.053 ms

Test Result:
PASSED


TEST CASE #4

Input:
{'capacity': 15, 'weights': [4, 5, 6], 'profits': [1, 2, 3]}

Expected Output:
6


Actual Output:
6

Execution Time:
0.009 ms

Test Result:
PASSED


TEST CASE #5

Input:
{'capacity': 15, 'weights': [4, 5, 1, 3, 2, 5], 'profits': [2, 3, 1, 5, 4, 7]}

Expected Output:
6


Actual Output:
19

Execution Time:
0.042 ms

Test Result:
FAILED


SUMMARY

TOTAL: 6, PASSED: 5, FAILED: 1

[(309, True, 0.173),
 (0, True, 0.004),
 (3, True, 0.006),
 (1735, True, 0.053),
 (6, True, 0.009),
 (19, False, 0.042)]

Memoized:

def knapsack_memo(capacity, weights, profits):
    memo = {}
    
    def recurse(idx, remaining):
        key = (idx, remaining)
        if key in memo:
            return memo[key]
        elif idx == len(weights):
            memo[key] = 0
        elif weights[idx] > remaining:
            memo[key] = recurse(idx+1, remaining)
        else:
            memo[key] = max(recurse(idx+1, remaining), 
                            profits[idx] + recurse(idx+1, remaining-weights[idx]))
        return memo[key] 
        
    return recurse(0, capacity)

evaluate_test_cases(knapsack_memo, tests)

Dynamic programming:

def knapsack_dp(capacity, weights, profits):
    results = [[0 for _ in range(capacity+1)] for _ in range(len(weights))]
    
    for idx in range(len(weights)):
        for c in range(capacity+1):
            if idx == 0:
                results[idx][c] = profits[idx] if c >= weights[idx] else 0
            elif weights[idx] > c:
                results[idx][c] = results[idx-1][c]
            else:
                results[idx][c] = max(results[idx-1][c], 
                                      profits[idx] + results[idx-1][c-weights[idx]])
            
    return results[-1][-1]

evaluate_test_cases(knapsack_dp, tests)

Problem Soplving Template: https://github.com/JovianHQ/notebooks/blob/main/data-structures-and-algorithms-in-python/python-problem-solving-template.ipynb