COMP 250 Lecture Notes - Lecture 19: Loop Invariant, Quicksort, Pseudocode
14 Mar 2017
School
Department
Course
Professor
Document Summary
How methods take input, return values, and are called, what happens when recursive algorithms are written in and executed, and notion of object-oriented programming. Writing recursive algorithm, completing pseudocode to make it work. To write a recursive algorithm: find how problem can be broken up in one or more smaller problems of the same nature, remember a base case. Better running times occur when these smaller problems are of the same size. Understanding their running times: fibonacci, binarysearch, power, integer multiplications. Know how there are multiple versions; one has better runtime than the other and why this occurs. Which one has which runtime: mergesort (including merge, quicksort (including partition) To prove that a proposition p(n) holds for all n a: base case: proves that p(a) holds, induction step on n: induction hypothesis, assume p(n) holds, prove that. May be asked to complete a proof, or to argue for a certain case.
