Foundations of Algorithms Workshop 11 === ###### tags: `comp10002` `workshop` `c` --- 1. MergeSort 2. Subset sum 3. Adjacent subarray sum 4. Heaps 6. ASSIGNMENT --- #### Mergesort ``` msort(A) n <- len(A) if n > 1 then merge(msort(A[:n/2]), msort(A[n/2:])) done ``` --- #### Mergesort How many times do we call msort? What complexity can we merge two sorted arrays in? What is the overall big O complexity of merge sort? --- #### Subsetsum Given a set of elements and a target k, does some subset of the original set sum to k? --- #### Subsetsum We need to consider every possible subset! How do we do that? --- #### Subsetsum ```cpp int subsetsum(int* vi, int n, int k) { if (k == 0) return 1; if (n == 0) return 0; return subsetsum(vi, n-1, k-vi[n-1]) || subsetsum(vi, n-1, k); } ``` --- #### Max subarray sum What is the maximum sum if we take some contiguous sub-array? --- #### Max subarray sum We need to consider every possible sub-array! how do we do that? --- #### Max subarray sum ```cpp for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { // subarray from [i..j] } } ``` --- #### Heaps ```cpp delete_min() // O(logn) decrease_key()// O(logn) insert()// O(logn) peek()// O(1) ``` --- #### Heaps The invariant: Every element in the heap, must satisfy that successor(x) < x. Meaning that the parent is always smaller than the children. --- #### Assignment Separate breakout room for code sharing purposes.