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 [2019/03/31 14:49]
127.0.0.1 external edit
algorithms [2020/07/10 18:16] (current)
Line 157: Line 157:
 4.    if (i/2 < p) 4.    if (i/2 < p)
         // swap the inserted element with its parent         // swap the inserted element with its parent
-5.      A[j] = A[j/2] +5.      A[i] = A[i/2] 
-6.      A[j/2] = p +6.      A[i/2] = p 
-7.      ​j/2+7.      ​i/2
 8.    else 8.    else
 9.      break 9.      break
Line 196: Line 196:
  
 {{ ::​heapsort.png?​direct&​600 |}} {{ ::​heapsort.png?​direct&​600 |}}
 +
 +=== Quicksort ===
 +
 +Quick sort selects a random location within the array called a pivot.
 +
 +Then it creates two lists, one containing all elements smaller than the pivot, and one containing all elements greater than the pivot. ​
 +
 +Then it recursively calls its with each of those two new lists. When the lists end up being only one element long, it all gets merged.
 +
 +{{:​pasted:​20200710-023220.png?​400}}
  
 ==== Priority Queue ==== ==== Priority Queue ====
Line 216: Line 226:
  
 ===== 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 244:
     * **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 ==== 
 +[[https://​www.youtube.com/​watch?​v=yBCzO0FpsVc|Good video here.]] 
 + 
 +{{:​pasted:​20200710-033351.png?​800}} 
 + 
 +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. 
 + 
 +Theres lots of little details in the maxCross function. Especially with dealing with finding the maximum of the subarrays when you have negative numbers. Where you start on the mid line counts. You had to go mid to left and mid+1 to the right. if you go mid-1 to the left you're screwed. 
 + 
 +**Find-Max-Crossing-Subarray Algorithm** 
 + 
 +<code cpp> 
 +int maxCross(vector<​int>&​nums,​ int& l, int &mid, int& r) 
 +
 +    // We don't have to do bounds checks because we know l won't equal r,  
 +    // because that's check for in the caller function. 
 +    // With that knowledge we can set max_l and max_r both to INT_MIN'​s cause 
 +    // I know there is going to be at least one element in each. You can also  
 +    // set to nums[mid] and nums[mid+1] 
 +    int max_l = INT_MIN, max_r = INT_MIN; 
 + 
 +    // find max left 
 +    int sum = 0; 
 +    for(int left = mid; left >= l; left-- ) 
 +    { 
 +        sum += nums[left];​ 
 +        max_l = max(sum, max_l); 
 +    } 
 +    // find max right 
 +    sum = 0; 
 +    for(int right = mid+1; right <= r; right++ ) 
 +    { 
 +        sum += nums[right];​ 
 +        max_r = max(sum, max_r); 
 +    } 
 +    // return the added sum. 
 +    return max_l + max_r; 
 +
 + 
 +int maxSub(vector<​int>&​ nums, int l, int r) 
 +
 +    if(l == r) 
 +        return nums[l]; 
 +    int mid = (l+r) / 2;  
 +    int max_left ​ = maxSub(nums,​ l, mid); 
 +    int max_right = maxSub(nums,​ mid + 1, r); 
 +    int max_cross = maxCross(nums,​ l, mid, r); 
 +    return max(max_left,​ max(max_right,​ max_cross) ); 
 +
 + 
 +int maxSubArray(vector<​int>&​ nums) { 
 +    if(nums.size() == 0) return NULL; 
 +    return maxSub(nums,​ 0, nums.size()-1);​ 
 +
 +</​code>​ 
 + 
 +===== Greedy Algorithms ===== 
 + 
 +A greedy algorithm is used to find optimal soltions - minimum or maximums. 
 +Problems are solved in stages, with each stage choosing the optimal solutions. 
 +If a solution is found, add it to your solutions. 
 + 
 +n = 5 
 + 
 +a = { a<​sub>​1</​sub>,​ a<​sub>​2</​sub>,​ a<​sub>​3</​sub>,​ a<​sub>​4</​sub>,​ a<​sub>​5</​sub>​ } 
 +<​code>​ 
 +1. Algorithm Greedy(a,​n) 
 +2. for i=1 to n do: 
 +3.    x = Select(a) 
 +4.    if Feasible(x) Then: 
 +5.        Solution = Solution + x 
 +</​code>​ 
 + 
 + 
 +===== 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 362:
 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 =====
Line 331: Line 417:
 $$o(g(n)) = \{f(n)\ :\ for\ any\ positive\ constant\ c>0,\ there\ exists\ a\ constant\\\ $$o(g(n)) = \{f(n)\ :\ for\ any\ positive\ constant\ c>0,\ there\ exists\ a\ constant\\\
 n_0>0\ such\ that\ 0\leq f(n)\ < c*g(n)\ for\ all\ n \geq n_0\}.$$ n_0>0\ such\ that\ 0\leq f(n)\ < c*g(n)\ for\ all\ n \geq n_0\}.$$
 +
 +===== Backtracking =====
 +
 +Backtracking is an algorithm that looks at all possible solutions for a problem
 +and evaluates each one.
  
  • algorithms.1554043774.txt.gz
  • Last modified: 2019/03/31 14:49
  • by 127.0.0.1