Repository: keon/algorithms
Pull request #592 (2019-11-10 16:47:20)

simple optimizations for knapsack code
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [ ] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [ ] included tests with it ?
  - [ ] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [X] **if done some changes :**
  - [X] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**



Patch:
diff --git a/PULL_REQUEST_TEMPLATE.md b/PULL_REQUEST_TEMPLATE.md
deleted file mode 100644
index ff98caf..0000000
--- a/PULL_REQUEST_TEMPLATE.md
+++ /dev/null
@@ -1,13 +0,0 @@
-(Put an `X` inside the `[ ]` to denote check mark `[X]`.)
-
-
-- [ ] **If creating a new file :**
-  - [ ] added links to it in the README files ?
-  - [ ] included tests with it ?
-  - [ ] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?
-
-- [ ] **if done some changes :**
-  - [ ] wrote short description in the PR explaining what the changes do ?
-  - [ ] Fixes #[issue number] if related to any issue
-
-- [ ] **other**
diff --git a/algorithms/dp/coin_change.py b/algorithms/dp/coin_change.py
index db14796..e9a83fc 100644
--- a/algorithms/dp/coin_change.py
+++ b/algorithms/dp/coin_change.py
@@ -1,37 +1,28 @@
 """
 Problem
-Given a value N, if we want to make change for N cents, and we have infinite supply of each of 
-S = { S1, S2, .. , Sm} valued //coins, how many ways can we make the change? 
+Given a value n, if we want to make change for N cents, and we have infinite supply of each of 
+coins = {S1, S2, .. , Sm} valued coins, how many ways can we make the change? 
 The order of coins doesn't matter.
-For example, for N = 4 and S = [1, 2, 3], there are four solutions: 
+For example, for n = 4 and coins = [1, 2, 3], there are four solutions: 
 [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3]. 
 So output should be 4. 
 
-For N = 10 and S = [2, 5, 3, 6], there are five solutions: 
+For n = 10 and coins = [2, 5, 3, 6], there are five solutions: 
 [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5] and [5, 5]. 
 So the output should be 5.
+
+Time complexity: O(n * m) where n is the value and m is the number of coins
+Space complexity: O(n)
 """
 
-def count(s, n):
-    # We need n+1 rows as the table is consturcted in bottom up
-    # manner using the base case 0 value case (n = 0)
-    m = len(s)
-    table = [[0 for x in range(m)] for x in range(n+1)]
- 
-    # Fill the enteries for 0 value case (n = 0)
-    for i in range(m):
-        table[0][i] = 1
- 
-    # Fill rest of the table enteries in bottom up manner
-    for i in range(1, n+1):
-        for j in range(m):
-            # Count of solutions including S[j]
-            x = table[i - s[j]][j] if i-s[j] >= 0 else 0
- 
-            # Count of solutions excluding S[j]
-            y = table[i][j-1] if j >= 1 else 0
+def count(coins, n):
+    # initialize dp array and set base case as 1
+    dp = [1] + [0] * n
  
-            # total count
-            table[i][j] = x + y
- 
-    return table[n][m-1]
+    # fill dp in a bottom up manner
+    for coin in coins:
+        for i in range(coin, n+1):
+            dp[i] += dp[i-coin]
+
+    return dp[n]
+
diff --git a/algorithms/dp/knapsack.py b/algorithms/dp/knapsack.py
index 65f7d89..530f939 100644
--- a/algorithms/dp/knapsack.py
+++ b/algorithms/dp/knapsack.py
@@ -12,7 +12,7 @@ the total number of items and m is the knapsack's capacity.
 """
 
 
-class Item(object):
+class Item:
 
     def __init__(self, value, weight):
         self.value = value
@@ -22,11 +22,7 @@ class Item(object):
 def get_maximum_value(items, capacity):
     dp = [0] * (capacity + 1)
     for item in items:
-        dp_tmp = [total_value for total_value in dp]
-        for current_weight in range(capacity + 1):
-            total_weight = current_weight + item.weight
-            if total_weight <= capacity:
-                dp_tmp[total_weight] = max(dp_tmp[total_weight],
-                                           dp[current_weight] + item.value)
-        dp = dp_tmp
-    return max(dp)
+        for cur_weight in reversed(range(item.weight, capacity+1)):
+            dp[cur_weight] = max(dp[cur_weight], item.value + dp[cur_weight - item.weight])
+    return dp[capacity]
+
diff --git a/algorithms/dp/longest_increasing.py b/algorithms/dp/longest_increasing.py
index 7197137..6cae572 100644
--- a/algorithms/dp/longest_increasing.py
+++ b/algorithms/dp/longest_increasing.py
@@ -7,14 +7,23 @@ Input: [10,9,2,5,3,7,101,18]
 Output: 4 
 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
 
-The time complexity is O(n^2).
+Time complexity:
+First algorithm is O(n^2).
+Second algorithm is O(nlogx) where x is the max element in the list
+Third algorithm is O(nlogn)
+
+Space complexity:
+First algorithm is O(n)
+Second algorithm is O(x) where x is the max element in the list
+Third algorithm is O(n)
 """
 
 def longest_increasing_subsequence(sequence):
     """
     Dynamic Programming Algorithm for
     counting the length of longest increasing subsequence
-    type sequence: List[int]
+    type sequence: list[int]
+    rtype: int
     """
     length = len(sequence)
     counts = [1 for _ in range(length)]
@@ -24,3 +33,79 @@ def longest_increasing_subsequence(sequence):
                 counts[i] = max(counts[i], counts[j] + 1)
                 print(counts)
     return max(counts)
+
+def longest_increasing_subsequence_optimized(sequence):
+    """
+    Optimized dynamic programming algorithm for
+    couting the length of the longest increasing subsequence
+    using segment tree data structure to achieve better complexity
+    if max element is larger than 10^5 then use 
+    longest_increasing_subsequence_optimied2() instead
+    type sequence: list[int]
+    rtype: int
+    """
+    mx = max(sequence)
+    tree = [0] * (mx<<2)
+
+    def update(p, l, r, i, v):
+        if l == r:
+            tree[p] = v
+            return
+        mid = (l+r)>>1
+        if i <= mid:
+            update(p<<1, l, mid, i, v)
+        else:
+            update((p<<1)|1, mid+1, r, i, v)
+        tree[p] = max(tree[p<<1], tree[(p<<1)|1])
+
+    def get_max(p, l, r, s, e):
+        if l > e or r < s:
+            return 0
+        if l >= s and r <= e:
+            return tree[p]
+        mid = (l+r)>>1
+        return max(get_max(p<<1, l, mid, s, e), get_max((p<<1)|1, mid+1, r, s, e))
+    ans = 0
+    for x in sequence:
+       cur = get_max(1, 0, mx, 0, x-1)+1
+       ans = max(ans, cur)
+       update(1, 0, mx, x, cur)
+    return ans
+
+def longest_increasing_subsequence_optimized2(sequence):
+    """
+    Optimized dynamic programming algorithm for
+    counting the length of the longest increasing subsequence
+    using segment tree data structure to achieve better complexity
+    type sequence: list[int]
+    rtype: int
+    """
+    n = len(sequence)
+    tree = [0] * (n<<2)
+    sorted_seq = sorted((x, -i) for i, x in enumerate(sequence))
+    def update(p, l, r, i, v):
+        if l ==r:
+            tree[p] = v
+            return
+        mid = (l+r)>>1
+        if i <= mid:
+            update(p<<1, l, mid, i, v)
+        else:
+            update((p<<1)|1, mid+1, r, i, v)
+        tree[p] = max(tree[p<<1], tree[(p<<1)|1])
+
+    def get_max(p, l, r, s, e):
+        if l > e or r < s:
+            return 0
+        if l >= s and r <= e:
+            return tree[p]
+        mid = (l+r)>>1
+        return max(get_max(p<<1, l, mid, s, e), get_max((p<<1)|1, mid+1, r, s, e))
+    ans = 0
+    for x, j in sorted_seq:
+        i = -j
+        cur = get_max(1, 0, n-1, 0, i-1)+1
+        ans = max(ans, cur)
+        update(1, 0, n-1, i, cur)
+    return ans 
+
diff --git a/algorithms/maths/gcd.py b/algorithms/maths/gcd.py
index 1f80fc9..002f4fc 100644
--- a/algorithms/maths/gcd.py
+++ b/algorithms/maths/gcd.py
@@ -10,3 +10,42 @@ def gcd(a, b):
 def lcm(a, b):
     """Computes the lowest common multiple of integers a and b."""
     return a * b / gcd(a, b)
+
+
+"""
+Given a positive integer x, computes the number of trailing zero of x.
+Example
+Input : 34(100010)
+           ~~~~~^
+Output : 1
+
+Input : 40(101000)
+           ~~~^^^
+Output : 3
+"""
+
+def trailing_zero(x):
+    cnt = 0
+    while x and not x & 1:
+        cnt += 1
+        x >>= 1
+    return cnt
+
+"""
+Given two non-negative integer a and b, 
+computes the greatest common divisor of a and b using bitwise operator.
+"""
+
+def gcd_bit(a, b):
+    tza = trailing_zero(a)
+    tzb = trailing_zero(b)
+    a >>= tza
+    b >>= tzb
+    while b:
+        if a < b: 
+            a, b = b, a
+        a -= b
+        a >>= trailing_zero(a)
+    return a << min(tza, tzb)
+
+
diff --git a/algorithms/search/jump_search.py b/algorithms/search/jump_search.py
index 66f726a..da8d8c3 100644
--- a/algorithms/search/jump_search.py
+++ b/algorithms/search/jump_search.py
@@ -16,7 +16,7 @@ def jump_search(arr,target):
     block_prev = 0
     block= block_size
 
-    # return -1 means that array doesn't contain taget value
+    # return -1 means that array doesn't contain target value
     # find block that contains target value
     
     if arr[n - 1] < target:


Test patch:
diff --git a/tests/test_dp.py b/tests/test_dp.py
index cd1dde2..f02921a 100644
--- a/tests/test_dp.py
+++ b/tests/test_dp.py
@@ -11,6 +11,8 @@ from algorithms.dp import (
     Job, schedule,
     Item, get_maximum_value,
     longest_increasing_subsequence,
+    longest_increasing_subsequence_optimized,
+    longest_increasing_subsequence_optimized2,
     int_divide
 )
 
@@ -135,6 +137,18 @@ class TestLongestIncreasingSubsequence(unittest.TestCase):
         self.assertEqual(5, longest_increasing_subsequence(sequence))
 
 
+class TestLongestIncreasingSubsequenceOptimized(unittest.TestCase):
+    def test_longest_increasing_subsequence_optimized(self):
+        sequence = [1, 101, 10, 2, 3, 100, 4, 6, 2]
+        self.assertEqual(5, longest_increasing_subsequence(sequence))
+
+
+class TestLongestIncreasingSubsequenceOptimized2(unittest.TestCase):
+    def test_longest_increasing_subsequence_optimized2(self):
+        sequence = [1, 101, 10, 2, 3, 100, 4, 6, 2]
+        self.assertEqual(5, longest_increasing_subsequence(sequence))
+
+
 class TestIntDivide(unittest.TestCase):
     def test_int_divide(self):
         self.assertEqual(5, int_divide(4))
diff --git a/tests/test_maths.py b/tests/test_maths.py
index 850cd5d..86b61e0 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -4,7 +4,7 @@ from algorithms.maths import (
     euler_totient,
     extended_gcd,
     factorial, factorial_recur,
-    gcd, lcm,
+    gcd, lcm, trailing_zero, gcd_bit,
     gen_strobogrammatic, strobogrammatic_in_range,
     is_strobogrammatic, is_strobogrammatic2,
     modular_exponential,
@@ -101,6 +101,13 @@ class TestGcd(unittest.TestCase):
     def test_lcm(self):
         self.assertEqual(24, lcm(8, 12))
 
+    def test_trailing_zero(self):
+        self.assertEqual(1, trailing_zero(34))
+        self.assertEqual(3, trailing_zero(40))
+
+    def test_gcd_bit(self):
+        self.assertEqual(4, gcd_bit(8, 12))
+        self.assertEqual(1, gcd(13, 17))
 
 class TestGenerateStroboGrammatic(unittest.TestCase):
     """[summary]
@@ -320,3 +327,4 @@ class TestCosineSimilarity(unittest.TestCase):
 
 if __name__ == "__main__":
     unittest.main()
+