diff options
Diffstat (limited to 'notes.md')
| -rw-r--r-- | notes.md | 79 |
1 files changed, 79 insertions, 0 deletions
@@ -80,3 +80,82 @@ By using an algorithm whose running time grows more slowly, even with a poor compiler, computer B runes more than 17 times faster than computer A! As the problem size increases, so does the relative advantage of merge sort. + + +1.2-1: Give an example of an application that requires algorithmic content at +the application level, and discuss the function of the algorithms involved. + + A fuzzy finder like `fzf`. This type of program needs to perform string + similarity analysis over any input provided and provide results as the + person types letters to reduce the total size of eligible results. + +1.2-2: Suppose we are comparing implementations of insertion sort and merge sort +on the same machine. For inputs of size `n`, insertion sort runs in `8n^2` +steps, while merge sort runs in `64nlg(n)` steps. For which values of `n` does +insertion sort beat merge sort? + + + The following program produces a result of '44'. + + ```golang + func main() { + fmt.Println("n,isort,msort") + + for n := 2.0; n < 1000.0; n++ { + isort := 8 * math.Pow(n, 2) + msort := 64 * (n * math.Log2(n)) + + fmt.Printf("%v,%v,%v\n", n, isort, msort) + if isort > msort { + break + } + } + } + ``` + + ``csv + n,isort,msort + 2,32,128 + 3,72,304.312800138462 + 4,128,512 + 5,200,743.0169903639559 + 6,288,992.6256002769239 + 7,392,1257.6950050818066 + 8,512,1536 + 9,648,1825.876800830772 + 10,800,2126.033980727912 + 11,968,2435.439859520657 + 12,1152,2753.251200553848 + 13,1352,3078.7658454933885 + 14,1568,3411.390010163613 + 15,1800,3750.614971784178 + 16,2048,4096 + 17,2312,4447.159571280369 + 18,2592,4803.753601661543 + 19,2888,5165.4798563474 + 20,3200,5532.067961455824 + 21,3528,5903.274616214654 + 22,3872,6278.879719041314 + 23,4232,6658.683199315923 + 24,4608,7042.502401107696 + 25,5000,7430.169903639559 + 26,5408,7821.531690986777 + 27,5832,8216.445603738473 + 28,6272,8614.780020327225 + 29,6728,9016.412726956773 + 30,7200,9421.229943568356 + 31,7688,9829.12547980756 + 32,8192,10240 + 33,8712,10653.760380085054 + 34,9248,11070.319142560738 + 35,9800,11489.593957956724 + 36,10368,11911.507203323086 + 37,10952,12335.985569809354 + 38,11552,12762.9597126948 + 39,12168,13192.363938280172 + 40,12800,13624.135922911648 + 41,13448,14058.216460117852 + 42,14112,14494.549232429308 + 43,14792,14933.080604940173 + 44,15488,15373.759438082629 + ``` |