CLRS in C++ .zip

2 Getting Started -------------------------------------------------------- ##Ex2.1-1 ```cpp algorithm begin: {31,[41],59,26,41,58} (index = 1) -> {31,41,[59],26,41,58} (index = 2) -> {[26],31,41,59,41,58} (index = 3) -> {26,31,41,[41],59,58} (index = 4) -> {26,31,41,41,[58],59} (index = 5) end ``` ##Ex2.1-2 [Insertion Sort](src/insertion_sort.hpp) | [Test](test/test_insertion_sort.cpp) * A functor for comparison can be passed in to specify order direction, such as `std::greater<T>` or `std::less<T>` ##Ex2.1-3 * Pseudocode: ```cpp Linear-Search(arr, val) 1 for i = 0 to arr.length - 1 2 if val == arr[i] 3 return i 4 return Nil ``` * Loop invariant: ```cpp At the start of each iteration of the for loop, no item preceeding arr[i] is equal to val. ``` * Proof: ```cpp I: i = 0 -> nothing preceeds index 0 -> trivially, no item preceeding index 0 is equal to val. -> I holds. M: suppose it holds for i = 0 to k. For i = k + 1, to continue the loop, arr[k + 1] must be unequal to val. -> after this iteration the loop invariant holds for i = k + 1. -> M holds. T: the termination conditions are either that i is equal to arr.length or that the item equal to val is found. -> for the first case, all items preceeding index arr.lengh, aka the entire array at this moment, are unequal to val, so Nil is returned; for the second case, the index that points to the value equal to val will be returned. -> both case return results as desired. -> T holds. I and M and T -> this algorithm is correct. ``` ##Ex2.1-4 [Implementation](src/add_binary_numbers.hpp) | [Test](test/test_add_binary_numbers.cpp) * Problem description: ```cpp Input: two arrays lhs and rhs which store two n-bit binary numbers respectively Output: one array that stores an n+1-bit binary number, such that it is equal to the sum of lhs and rhs ``` * Pseudocode: ```cpp Add-Binary-Numbers(lhs, rhs) 1 def sum as an array with sum.length = lhs.lengh + 1 2 def carry = 0 3 for i = lhs.lengh - 1 to 0 4 sum[i + 1] = (carry + lhs[i] + rhs[i]) % 2 5 carry = (carry + lhs[i] + rhs[i]) / 2 6 sum[0] = carry 7 return sum ``` ##Ex2.2-1 ```cpp \theta(n^3) ``` ##Ex2.2-2 [Selection Sort](src/selection_sort.hpp) | [Test](test/test_selection_sort.cpp) * Pseudocode: ```cpp Selection-Sort(arr) 1 for i = 0 to arr.length - 2 <- c1 x (n - 1) 2 def index_for_min = arr[i] <- c2 x (n - 2) 3 for j = i to arr.length - 1 <- c3 x (n - 2) x n / 2 4 if arr[min] > arr[j] <- c4 x (n - 2) x (n / 2 - 1) 5 index_for_min = j <- time belongs to range [0, c5 x (n - 2) x (n / 2 - 1)] 6 swap arr[i] and arr[min] <- c6 x (n - 2) x (n / 2 - 1) 7 return arr <- c7 ``` * Loop invariant: ```cpp At the start of each iteration of the for loop, all items in range [0, i) are less than any item in range [i, length - 1); Also items in range [0, i) have been sorted. ``` * With n = arr.length, when i == n - 1 , only one item left in range[n - 1, n). If this algorithm runs n times, what it does in the last run will always be swap (arr[arr.length - 1], arr[arr.length - 1]). Hence, n - 1 times is enogh. * Time complexity: ```cpp For best case, time complexity for line 5 equals to 0. Total time required : \theta(n^2) For worst case, time complexity for line 5 equals to c5 x (n - 2) x (n / 2 - 1). Total time required : \theta(n^2) ``` ##Ex2.2-3 * n/2 elements need to be checked on average. * For worst case, n elements need to be checked. * For average-case, `theta(n/2) -> theta(n)` * For worst case, `theta(n)` ##Ex2.2-4 Not sure about this question.Perhaps a precheck can be carried out to see if the input is desired already. ##Ex2.3-1 ```cpp {3, 9, 26, 38, 41, 49, 52, 57} {3, 26, 41, 52} {9, 38, 49, 57} {3, 41} {26, 52} {38, 57} {9, 49} {3} {41} {52} {26} {38} {57} {9} {49} ``` ##Ex2.3-2 [Merge Sort](src/merge_sort.hpp) | [Test](test/test_merge_sort.cpp) ##Ex2.3-3 ```cpp basis: n = 1 -> LHS = 2 and RHS = 2 x lg(2) = 2 x 1 = 2 -> LHS == RHS induction: suppose: the equaltion is correct for n = 2^k, where k > 1. -> T(2^k) = 2^k x lg(2^k) = (2^k) x k -- eq2 for n = k + 1: LHS = 2T(2^(k+1)/2) + 2^(k+1) = 2T(2^k) + 2^(k+1) using eq2: = 2k(2^k) + 2^(k+1) = k(2^(k+1)) + 2^(k+1) = (2^(k+1)) x (k+1) RHS = (2^(k+1)) x lg(2^(k+1)) = (2^(k+1)) x (k+1) LHS = RHS -> This equation is correct. ``` ##Ex2.3-4 * Pseudocode: ```cpp Insertion-Sort-by-Recursion(arr) if arr.length < 2 //theta(1) return arr //theta(1) else //theta(1) arr = Insertion-Sort-by-Recursion(arr[:-1]) + arr[-1] //T(n - 1) + theta(1) def key = arr[-1] //theta(1) def curr = arr.length - 1 //theta(1) for (curr = arr.length - 1 to 1) and (arr[curr] > key) //O(n - 1) arr[curr + 1] = arr[curr] //O(n - 2) arr[curr + 1] = key //theta(1) return arr //theta(1) ``` * Recurrence: ```cpp T(n) = theta(1) , if n = 1 = T(n - 1) + O(n) , if n > 1 ``` ##Ex2.3-5 * Pseudocode: ```cpp Binary-Search-by-Recursion(arr, val) low = 0 high = arr.length - 1 while low <= high //T(n/2) mid = (low + high)/2 if arr[mid] > val high = mid - 1 else if arr[mid] < val low = mid + 1 else return mid return Nil ``` * Proof for time complexity ```cpp From the pseudocode -> T(n) = T(n/2) + theta(1) -> T(n) = theta(lg(n)) ``` ##Ex2.3-6 * No. lines 5 - 7 from Insertion-Sort are doing two things: Firstly, it finds the correct position to insert; Secondly, it pushes elements with greater value backwards. For an arrry, binary search can't improve the pushing part, For a linked list, binary seach can't handle the first task. ##Ex2.3-7 * Pseudocode ```python #Combine sorting and binary search together. Are-There-Two-Elements-That-Have-Sum-As-Specified(set, sum) set.sort() #O(n lg n) for curr = 0 to set.length - 1 #O(n) if Nil != binary_search(arr = set[curr:], val = sum - set[curr]) #O(n lg n) return true return false ``` ##Problem 2-1 Merge-Sort + Insertion-Sort * a. Time complexity for sorting n/k sublists with insertion sort: ```cpp (n/k) x theta(k^2) = theta(nk) ``` * b. Time complexity for merging all sublists ```cpp As shown in Figure 2.5: it takes theta(n) to merge each level in recursion tree. total height of the recursion is theta(lg(n)) merging start from the first level to lg(k): theta(n(lg(n) - lg(k))) = theta(n(lg(n/k))) Hence, it takes T(n) = theta(n(lg(n/k))) to merge the sublists. ``` * c. k = lg(n) is the largest value that meets requirement. ```cpp T(n) = theta(n + n x lg(n)) , if k = 1 This is exact merge sort with no optimization. T(n) = theta(n x lg(n) + n x lg(n / lg(n))), if k = lg(n) Since n is supposed to be greater than 2, the first term n x lg(n) is the significant part. Anything greater than lg(n) will make the first term greater than theta(n x lg(n)) and the second term is always postive. Hence the largest value is k = lg(n) ``` * d. The desired value can be found by testing values from range [1, lg(n)]. ##Problem 2-2 Bubble-Sort * a. One more thing need to prove is that no item in A has been deleted nor item added into A'.In another word, A' must be a permutation of A. * b. Loop invariant and its proof for lines 2-4 ```cpp Loop invariant: Prior to each iteration of the for loop, A[j] = min(s) , where set s = { x | x <- A[j, A.length] } . Proof I: Prior to the first iteration -> j