CS341 Study Guide - Binary Logarithm, Insertion Sort, Algorithm Engineering
Document Summary
Reading for this lecture: clrs, sections 3. 2, 2. 3. 1. You already know a lot about recursion from your first courses on programming. We will see much more about recursion when we discuss divide-and-conquer, but we"ll provide a few remarks here. Sometimes programming is a useful paradigm for algorithm design, but you have to be careful! It"s easy to get exponential behavior through a poorly-designed algorithm. Recall, for example, the fibonacci numbers, defined by f(0) = 0, f(1) = 1, and f(n) = f(n-1) + f(n-2) for n 2. (reference: clrs, page 56 of 2nd edition or 59 of 3rd. ) It"s easy to write a recursive program to compute these: then return(n) return(fib(n-1)+fib(n-2)) function fib(n) if (n <= 1) else. The problem with this algorithm is that it is woefully inefficient. Let t(n) denote the number of steps needed by fib(n). Then t(0) = 1, t(1) = 1, and t(n) = t(n-1) + t(n-2) + 1.
