this is an Analysis of Algorithms Assignment. I have a previous Year's assignment solved If you need I can share it here so you will understand how to write the solution.
COMP 2080 Winter 2022 Homework Assignment 2 due Wednesday, February 16, 11:59pm Must be submitted on Crowdmark, not UM Learn Proof questions will be graded for style and clarity of presentation, as well as correctness. Some notation we’ll be using concerning an array A in some parts of this assignment: • The value of A.length correctly represents the number of elements in array A. • The array indices are 0 up to A.length− 1. • The notation A[i] represents the element at index i in A. • For any 0 ≤ x ≤ y ≤ A.length − 1, the subarray notation A[x . . .y] represents an array B of length y− x+ 1 such that: B[i] = A[x+ i] for each i ∈ {0, . . . ,y− x} Some examples: Suppose A= [2, 4,6], then A[0 . . . 0] = [2] and A[1 . . . 2] = [4,6] • For any integers y< x,="" the="" subarray="" notation="" a[x="" .="" .="" .y]="" represents="" an="" empty="" array,="" i.e.,="" it="" contains="" no="" elements.="" 1="" assignment="" questions="" start="" here:="" 1.="" for="" both="" parts="" of="" this="" question,="" consult="" algorithm="" 1.="" your="" answers="" should="" follow="" the="" same="" style="" and="" format="" as="" shown="" in="" the="" algorithm="" correctness="" lectures="" 2,="" 3,="" 4.="" algorithm="" 1="" 1:="" pre:="" (y="=" 11)∧="" (n="" ∈="" {9,="" 16})="" 2:="" x="" ←="" 3="" 3:="" z←="" x="" +="" y="" 4:="" assert:="" 5:="" if="" n="" is="" odd="" then="" 6:="" z←="" z/2="" 7:="" end="" if="" 8:="" post:="" z="=" n−="" 2="" (a)(2="" pts)="" provide="" an="" assert="" statement="" for="" line="" 4.="" you’ll="" need="" to="" do="" some="" planning="" ahead:="" read="" part="" (b)="" to="" help="" guide="" your="" choice="" for="" the="" assert="" statement.="" (b)(6="" pts)="" write="" out="" your="" assert="" statement="" from="" part="" (a)="" again,="" then="" prove="" that="" the="" code="" satisfies="" the="" partial="" correctness="" property.="" in="" particular:="" your="" solution="" should="" consist="" of="" two="" proofs,="" one="" for="" each="" of="" the="" following="" statements:="" (1)="" ((pre="" is="" true="" at="" line="" 1)∧="" (line="" 4="" is="" reached))⇒="" (assert="" is="" true="" when="" line="" 4="" is="" reached)="" (2)="" ((assert="" is="" true="" at="" line="" 4)∧="" (line="" 8="" is="" reached))⇒="" (post="" is="" true="" when="" line="" 8="" is="" reached)="" note:="" if="" you="" are="" having="" trouble="" proving="" either="" of="" the="" two="" statements="" above,="" you="" might="" need="" to="" go="" back="" to="" part="" (a)="" and="" change="" your="" assert="" statement.="" also,="" make="" sure="" your="" proof="" that="" post="" is="" true="" does="" not="" rely="" on="" any="" information="" that="" appears="" before="" line="" 4="" (again,="" you="" might="" need="" to="" adjust="" your="" assert="" statement="" to="" prevent="" this).="" 2="" 2.(6="" pts)="" using="" strong="" induction,="" prove="" that="" the="" following="" recursive="" program="" is="" fully="" correct.="" your="" answer="" should="" follow="" the="" same="" style="" and="" format="" as="" shown="" in="" the="" algorithm="" correctness="" lecture="" 7.="" algorithm="" 2="" int="" findminrec(a)="" 1:="" pre:="" (a="" is="" an="" array="" of="" integers)∧="" (a.length≥="" 1)="" 2:="" if="" a.length="=" 1="" then="" 3:="" returnval←="" a[0]="" 4:="" else="" 5:="" recursemin←="" findminrec(a[1="" .="" .="" .="" (a.length−="" 1)])="" 6:="" if="" a[0]≤="" recursemin="" then="" 7:="" returnval←="" a[0]="" 8:="" else="" 9:="" returnval←="" recursemin="" 10:="" end="" if="" 11:="" end="" if="" 12:="" post:="" (returnval="" is="" the="" minimum="" value="" among="" all="" elements="" in="" a)="" 3="" 3.="" for="" all="" parts="" of="" this="" question,="" consider="" algorithm="" 3="" below.="" you="" should="" assume="" (without="" proof)="" that="" the="" given="" loop="" invariant="" is="" true="" each="" time="" the="" loop="" condition="" is="" checked.="" your="" answers="" should="" follow="" the="" same="" style="" and="" format="" as="" shown="" in="" the="" algorithm="" correctness="" lecture="" 6.="" algorithm="" 3="" 1:="" loopinv:="" (x="" ,="" y="" ∈="" z)∧="" (y="" ≥="" 0)="" 2:="" while="" (x="" ≥="" 2)∧="" (y="" ≤="" 20)="" do="" 3:="" if="" x="" is="" odd="" then="" 4:="" y="" ←="" y="" +="" 1="" 5:="" x="" ←="" x="" +="" 2="" 6:="" else="" 7:="" x="" ←="" x/2="" 8:="" end="" if="" 9:="" end="" while="" (a)(1="" pt)="" write="" an="" expression="" e="" that="" is="" a="" correct="" loop="" measure="" for="" proving="" the="" code="" terminates.="" hint:="" something="" like="" e="x" +="" y="" is="" too="" simple.="" add="" and="" multiply="" by="" some="" constants.="" (b)(3="" pts)="" write="" your="" choice="" of="" e="" from="" part="" (a)="" again,="" then="" write="" a="" proof="" that="" your="" e="" satisfies="" condition="" 1="" of="" being="" a="" loop="" measure:="" the="" value="" of="" e="" decreases="" by="" at="" least="" 1="" between="" every="" two="" consecutive="" checks="" of="" the="" loop="" condition.="" (c)(2="" pts)="" write="" your="" choice="" of="" e="" from="" part="" (a)="" again,="" then="" write="" a="" proof="" that="" your="" e="" satisfies="" condition="" 2="" of="" being="" a="" loop="" measure:="" if="" e="" ≤="" 0,="" then="" the="" loop="" condition="" evaluates="" to="" false.="" 4="" 4.="" for="" both="" parts="" of="" this="" question,="" consult="" algorithm="" 4.="" your="" answers="" should="" follow="" the="" same="" style="" and="" format="" as="" shown="" in="" the="" algorithm="" correctness="" lecture="" 5.="" algorithm="" 4="" int="" findminiter(a)="" 1:="" pre:="" (a="" is="" an="" array="" of="" integers)∧="" (a.length≥="" 1)="" 2:="" returnval←="" a[0]="" 3:="" i←="" 0="" 4:="" loopinv:="" 5:="" while="" i≤="" a.length−="" 1="" do="" 6:="" if="" a[i]≤="" returnval="" then="" 7:="" returnval←="" a[i]="" 8:="" end="" if="" 9:="" i←="" i+="" 1="" 10:="" end="" while="" 11:="" post:="" the="" subarray="" a[0="" .="" .="" .="" (a.length−="" 1)]="" does="" not="" contain="" an="" element="" that="" is="" smaller="" than="" returnval="" (a)(8="" pts)="" first,="" provide="" a="" loop="" invariant="" loopinv="" that="" could="" appear="" at="" line="" 4.="" then,="" using="" strong="" induc-="" tion,="" prove="" that="" your="" loop="" invariant="" is="" true="" every="" time="" that="" the="" loop="" condition="" is="" checked.="" you’ll="" need="" to="" do="" some="" planning="" ahead:="" read="" part="" (b)="" to="" help="" guide="" your="" choice="" of="" loop="" invariant.="" (b)(3="" pts)="" write="" out="" your="" loop="" invariant="" loopinv="" from="" part="" (a)="" again,="" then="" use="" it="" to="" prove="" the="" following="" statement:="" (loopinv="" is="" true)∧="" (loop="" condition="" is="" false)⇒="" (post="" is="" true).="" this="" proof="" should="" not="" reference="" anything="" that="" happens="" inside="" the="" loop="" or="" before="" the="" loop:="" like="" in="" the="" provided="" lectures="" and="" examples="" in="" um="" learn,="" your="" loopinv="" should="" contain="" enough="" information="" about="" the="" program’s="" variables="" so="" that="" you="" can="" prove="" post="" directly="" using="" only="" loopinv="" and="" the="" fact="" that="" the="" loop="" condition="" evaluated="" to="" false.="" you="" may="" need="" to="" go="" back="" to="" part="" (a)="" to="" modify="" your="" loopinv="" to="" achieve="" this.="" 5="" comp="" 2080="" winter="" 2021="" homework="" assignment="" 2="" solutions="" 1.="" for="" both="" parts="" of="" this="" question,="" consult="" algorithm="" 1.="" your="" answers="" should="" follow="" that="" same="" style="" and="" format="" as="" shown="" in="" lectures="" 6-8.="" algorithm="" 1="" 1:="" pre:="" (y="=" 3)="" ∧="" (n="" ∈="" {1,−1})="" 2:="" x←="" 2="" 3:="" z="" ←="" x+="" y="" 4:="" assert:="" 5:="" if="" n="">< 0="" then="" 6:="" z="" ←="" −z="" 7:="" end="" if="" 8:="" post:="" z="=" 5="" ·="" n="" (a)="" [3="" marks]="" provide="" an="" assert="" statement="" for="" line="" 4.="" you’ll="" need="" to="" do="" some="" planning="" ahead:="" read="" part="" (b)="" to="" help="" guide="" your="" choice="" for="" the="" assert="" statement.="" solution="" on="" line="" 4,="" define="" as="" assert="" as="" (z="=" 5)="" ∧="" (n="" ∈="" {−1,="" 1})="" 1="" (b)="" [5="" marks]="" prove="" that="" the="" code="" satisfies="" the="" partial="" correctness="" property.="" in="" particular:="" assume="" that="" the="" code="" terminates,="" and="" prove="" that="" the="" following="" two="" statements="" are="" true:="" •="" (pre="" is="" true="" when="" line="" 1="" is="" reached)⇒="" (assert="" is="" true="" when="" line="" 4="" is="" reached)="" •="" (assert="" is="" true="" when="" line="" 4="" is="" reached)⇒="" (post="" is="" true="" when="" line="" 8="" is="" reached)="" note:="" if="" you="" are="" having="" trouble="" proving="" either="" of="" the="" two="" statements="" above,="" you="" might="" need="" to="" go="" back="" to="" part="" (a)="" and="" change="" your="" assert="" statement.="" also,="" make="" sure="" that="" your="" proof="" that="" post="" is="" true="" does="" not="" rely="" on="" any="" information="" that="" appears="" before="" line="" 4="" (again,="" you="" might="" need="" to="" adjust="" your="" assert="" statement="" to="" prevent="" this).="" solution="" proof.="" (1)="" assume="" that="" the="" code="" terminates="" (i.e.,="" line="" 8="" is="" reached).="" (2)="" first,="" we="" prove="" that="" (pre="" is="" true="" when="" line="" 1="" is="" reached)⇒="" (assert="" is="" true="" when="" line="" 4="" is="" reached)="" (3)="" suppose="" that="" pre="" is="" true="" when="" line="" 1="" is="" reached,="" i.e.,="" that="" y="3" and="" n="" ∈="" {−1,="" 1}="" at="" line="" 1.="" (4)="" from="" (3)="" and="" the="" fact="" that="" the="" value="" of="" y="" is="" not="" modified="" in="" line="" 2="" of="" the="" code,="" it="" follows="" that="" y="3" when="" line="" 3="" is="" reached.="" (5)="" at="" line="" 2,="" the="" value="" of="" x="" is="" set="" to="" 2,="" so="" the="" value="" of="" x="" is="" 2="" immediately="" before="" line="" 3.="" (6)="" from="" (4)="" and="" (5),="" we="" conclude="" that="" x+="" y="2" +="" 3="5." this="" value="" is="" assigned="" to="" z="" on="" line="" 3,="" so="" the="" value="" of="" z="" is="" 5="" immediately="" before="" line="" 4.="" (7)="" from="" (3)="" and="" the="" fact="" that="" the="" value="" of="" n="" is="" not="" modified="" in="" lines="" 2-3="" of="" the="" code,="" it="" follows="" that="" n="" ∈="" {−1,="" 1}="" immediately="" before="" line="" 4.="" (8)="" from="" (6)="" and="" (7),="" we="" see="" that="" z="" is="" equal="" to="" 5="" and="" n="" ∈="" {−1,="" 1}="" at="" line="" 4,="" which="" confirms="" that="" our="" assert="" is="" true="" when="" line="" 4="" is="" reached.="" (9)="" next,="" we="" prove="" that="" (assert="" is="" true="" when="" line="" 4="" is="" reached)⇒="" (post="" is="" true="" when="" line="" 8="" is="" reached)="" (10)="" suppose="" that="" assert="" is="" true="" when="" line="" 4="" is="" reached,="" i.e.,="" that="" z="5" and="" n="" ∈="" {−1,="" 1}.="" (11)="" there="" are="" two="" cases="" to="" consider="" based="" on="" the="" possible="" values="" of="" n:="" •="" case="" (a):="" suppose="" that="" n="−1." in="" this="" case,="" since="" n="">< 0,="" the="" if="" condition="" on="" line="" 5="" evaluates="" to="" true.="" this="" means="" that="" line="" 6="" is="" executed.="" from="" (10),="" we="" know="" that="" z="5" at="" line="" 4,="" and,="" since="" the="" value="" of="" z="" is="" not="" changed="" on="" line="" 5,="" the="" value="" of="" z="" is="" 5="" immediately="" before="" line="" 6.="" at="" line="" 6,="" the="" value="" of="" z="" is="" changed="" to="" −z,="" so,="" immediately="" after="" line="" 6,="" the="" value="" of="" z="" is="" -5.="" as="" the="" value="" 2="" of="" z="" is="" not="" changed="" after="" line="" 6,="" the="" code="" reaches="" line="" 8="" with="" z="−5" =="" 5="" ·="" n.="" this="" proves="" that="" post="" is="" true="" when="" line="" 8="" is="" reached.="" •="" case="" (b):="" suppose="" that="" n="1." in="" this="" case,="" since="" n="" ≥="" 0,="" the="" if="" condition="" on="" line="" 5="" evaluates="" to="" false.="" this="" means="" that="" line="" 6="" is="" not="" executed,="" and="" line="" 8="" is="" reached="" immediately="" after="" line="" 5.="" from="" (10),="" we="" know="" that="" z="5" at="" line="" 4,="" and,="" since="" the="" value="" of="" z="" is="" not="" changed="" on="" line="" 5,="" it="" follows="" that="" z="5" =="" 5="" ·="" n="" at="" line="" 8.="" this="" proves="" that="" post="" is="" true="" when="" line="" 8="" is="" reached.="" �="" 3="" 2.="" [8="" marks]="" consider="" the="" following="" algorithm="" that="" attempts="" to="" compute="" the="" value="" k="" ·="" ∑n="" i="1" i="" for="" any="" real="" number="" k="" and="" any="" positive="" integer="" n.="" following="" the="" proof="" style="" from="" lecture="" 11,="" prove="" that="" sumalg(k,="" n)="" is="" fully="" correct.="" algorithm="" 2="" sumalg(k,="" n)="" 1:="" pre:="" (k="" ∈="" r)="" ∧="" (n="" ∈="" z)="" ∧="" (n=""> 0) 2: if n == 1 then 3: answer← k 4: else 5: answer← (k · n) + sumAlg(k, n− 1) 6: end if 7: return answer 8: //post: the return value is equal to k · ∑n i=1 i Solution Note: my solution puts k as a parameter of the predicate, but it is not necessary, since the value