COMPSCI 1MD3 Lecture Notes - Lecture 8: Dynamic Programming, Exponential Growth, Firstclass
9 Apr 2018
School
Department
Course
Professor
Document Summary
Dynamic programming - remembers intermediate solutions to save on recursion. Infinite recursion occurs when there is a missing base case, or the base case accidently gets bypassed, and does not terminate. Runtime complexity - number of basic operations that algorithm will perform for a certain set of inputs. Runtime: number of seconds the implementation ran for on a particular computer with a particular input. Memory complexity - what is the approximate number of entries that the algorithm will read/write for a certain number of inputs. Ram the implementation used on a particular computer with a particular output. Exponential growth of runtime on a computer is not desirable. Memoization is when intermediate results are saved, and then used later to avoid recursion. May be used to check if a particular element is in the sequence. Unstructured /linear search- not sorted, searching through the sequence, its runtime is a linear function of the list size.
