CS 240 Midterm 2 Review: Iterative & Recursive Concepts

what induction does loop invariance use?

regular induction

what induction does structural induction use?

strong induction (assume base case to k is all true (0≤ j ≤ k) and use middle term to prove k+1)

what induction does recursive induction use?

what induction does iterative induction use?

converse vs contrapositive vs inverse if regular proposition is p->q

-converse: q- > p

-contra: -q- > -p

-inverse: -p -> -q

proving loop invariants:

-P(n): nth time the loop is tested, loop invariants hold

-base case: P(1) - when loop is tested for first time (doesnt do anythng in the loop yet tho), check invariant holds for values inputted/program specifications

-induction: assume kth step is true, prove k+1 step is true.

iterative program correctness:

-base case: prove each loop invariant is valid for the first iteration, using the program output

-partial correctness: use the loop invariants to prove the output is correct (look at what makes the program terminate and inequalities to see what to sub into output to make the output correct

-termination: look when the loop exits, and explain that due to an unchanging variable, the loop is not infinite and will terminate

-induction base case: show p(1) holds by showing each loop invariant is valid and holds by looking at input

-induction: write each invariant in terms of k and then relate it to the k+1 step by following through the loop and replacing k in it or nsubbing k in somewhere

-* if there is an if statement, there is likely multiple cases

base case 0 or base case 1

- base case 0: n = number of # loop iterations

- base case 1: nth time in loop

structural induction

-base case: P(0) holds as 0 applications of consturctor rule - only use foundation rule

-induction: assume p(j) holds for 0

recursion program correctness

-partial correctness includes base case and recursive call:

--base case: correct result returned for non-recursive case

--recursive case: show valid input is given to call and then show it returns correct ouput in terms of ouput and assumes termination

-termination: uses induction-base case

recurrence relations

-initial terms are till the last value of items joins the relation

-A6 is made up of ... try each item value so probs like 3 ways. A6 - each item value = one intiial term that can be added up for the general relartion

-induction: p(n) is the proposed solution which is the 2^n + or 1 something pattern. between the M(n) values, base case is p(1) and check that A1 value = proposed solution plugin 1 value. Sub k into proposed solution to get P(k), take P(k+1) = reccurence relation and sub P(k) for M(k) and try to get that into proposed solution form

asymptotic analysis: big theta, big 0, big omega

-Big theta 0xcrossedout(g(n)): has a c ≤ f(n)/g(n) ≤ d

-Big oh O(g(n)) f(n)/g(n) ≤ d (limit of this cant be infinity)

-Big omega O(Ohmsymbol(g(n)) can be c ≤ f(n)/g(n) (limit of this cant be 0