CS341 Study Guide - Analysis Of Algorithms, Merge Sort, Graphing Calculator
Document Summary
Office hours are now available on the course home page. Don"t forget that the first assignment is available (due september 16, 5 pm). Recall from last time: the maximum subrange sum problem. Brute force solution: enumerate all possible subblocks of the array: maxsubrangesum1(x,n); max := 0; for lower := 1 to n do return(max); Each loop is o(n), so the total time is o(n3), and one can also prove that it is (n3). Can we do better? for upper := lower to n do sum := 0 for i := lower to upper do sum := sum+x[i]; if sum > max then max := sum; Yes, if we recognize that the inner loop is doing a lot of recomputation each time: sum := 0; for upper := lower to n do maxsubrangesum2(x,n); max := 0; for lower := 1 to n do return(max); There"s another approach that also produces a (n2) algorithm: namely, first do some precomputation to produce the.
