Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
algorithms [2020/05/24 21:35]
127.0.0.1 external edit
algorithms [2020/07/09 18:20] (current)
paul
Line 216: Line 216:
  
 ===== Divide and conquer ===== ===== Divide and conquer =====
 +
 +https://​leetcode.com/​explore/​learn/​card/​recursion-ii/​470/​divide-and-conquer/​2897/​
  
 Many algorithms are recursive, they call themselves recursively to deal with closely related sub-problems. ​ Many algorithms are recursive, they call themselves recursively to deal with closely related sub-problems. ​
Line 232: Line 234:
     * **master method** provides bounds for recurrences of the form $T(n) = aT(n/b) + f(n)$ where $a \geq 1,\ b\ > \ 1$ and $f(n)$ is a given function.     * **master method** provides bounds for recurrences of the form $T(n) = aT(n/b) + f(n)$ where $a \geq 1,\ b\ > \ 1$ and $f(n)$ is a given function.
  
-==== Sliding Window ====+{{:​pasted:​20200708-194123.png?​400}} 
 + 
 +==== Binary Search Tree Validation ==== 
 + 
 +Validating a binary search tree can be solved with a divide and conquer approach. We check each node against an upper and lower bound. We then recurs and check both children. 
 + 
 +{{:​pasted:​20200709-181958.png?​400}} 
 + 
 +==== Maximum subarray ==== 
 + 
 +The maximum subarray problem can be solved using divide and conquer. 
 + 
 +By breaking up the input array into two subarrays of $n/2$ length as follows: 
 +  * A[low..mid] 
 +  * A[mid+1..high] 
 +   
 +The maximum subarray A[i..j] can only be located in one of 3 places; in the 
 +first one, crossing the middle, or the end. To solve this equation we must find 
 +the maximum subarray in each of those 3 places and simply pick the biggest one. 
 + 
 +**Find-Max-Crossing-Subarray Algorithm** 
 + 
 +===== Sliding Window ​=====
  
 An approach for scanning through data is to use a sliding window technique. An approach for scanning through data is to use a sliding window technique.
Line 260: Line 284:
 9.         i++, j-- 9.         i++, j--
 10. return max 10. return max
-</​code>​ +</​code> ​
- +
- +
-==== Maximum subarray ==== +
- +
-The maximum subarray problem can be solved using divide and conquer. +
- +
-By breaking up the input array into two subarrays of $n/2$ length as follows: +
-  * A[low..mid] +
-  * A[mid+1..high] +
-   +
-The maximum subarray A[i..j] can only be located in one of 3 places; in the +
-first one, crossing the middle, or the end. To solve this equation we must find +
-the maximum subarray in each of those 3 places and simply pick the biggest one. +
- +
-**Find-Max-Crossing-Subarray Algorithm** +
-  ​+
  
 ===== Growth of Functions ===== ===== Growth of Functions =====
  • algorithms.1590356111.txt.gz
  • Last modified: 2020/05/24 21:35
  • by 127.0.0.1