Mathematics for Computer Science
6.2. State Machines 133 Ifzis even, then we have thatxtDx^2 ;ytDy;ztDz=2. Therefore,zt 2 N and ytxtztDy.x^2 /z=2 Dyx^2 z=2 Dyxz ...
Chapter 6 Induction134 6.3 Strong Induction A useful variant of induction is calledStrong Induction. Strong induction and ordi- ...
6.3. Strong Induction 135 you can assume thatP.0/,P.1/,... ,P.n/are all true instead of onlyP.n/ during the inductive step. 6. ...
Chapter 6 Induction136 Here’s a detailed writeup using the official format: Proof. We prove by strong induction that the Inducti ...
6.3. Strong Induction 137 Stack Heights Score 10 5 5 25 points 5 3 2 6 4 3 2 1 4 2 3 2 1 2 4 2 2 2 1 2 1 2 1 2 2 1 2 1 1 1 1 1 2 ...
Chapter 6 Induction138 resulting substacks: total scoreD(score for 1st move) C(score for unstackingablocks) C(score for unstacki ...
6.4. Strong Induction vs. Induction vs. Well Ordering 139 So why three methods? Well, sometimes induction proofs are clearer bec ...
Chapter 6 Induction140 Problem 6.3. Prove by induction: 1 C 1 4 C 1 9 CC 1 n^2 < 2 1 n ; (6.7) for alln > 1. Problem 6. ...
6.4. Strong Induction vs. Induction vs. Well Ordering 141 Above, we group some terms, use the assumptionP.n/, and then simplify. ...
Chapter 6 Induction142 and a binary digit,cnC 1 , as outputs, and satisfies the specification: num. ̨n/Cnum.ˇn/Cc 0 D 2 nC^1 cnC ...
6.4. Strong Induction vs. Induction vs. Well Ordering 143 with at least one previously-placed square and no squares overlapped. ...
Chapter 6 Induction144 Pour from the little jug into the big jug: forl > 0, .b;l/! ( .bCl;0/ ifbCl 5 , .5;l.5b// otherwise ...
6.4. Strong Induction vs. Induction vs. Well Ordering 145 whiles¤ 0 do if 3 jsthen rWDrCrCr; sWDs=3; else if 3 j.s1/then aWDaCr; ...
Chapter 6 Induction146 4..3;0/ Thus, for example, Wall-E might walk as follows. The types of his steps are listed above the arro ...
6.4. Strong Induction vs. Induction vs. Well Ordering 147 The above scenario can be nicely modelled as a state machine in which ...
Chapter 6 Induction148 fill a bucket from the hose, pour from the receptacle to a bucket until the bucket is full or the recept ...
6.4. Strong Induction vs. Induction vs. Well Ordering 149 The state transitions correspond to exchanging the empty square and an ...
Chapter 6 Induction150 (+2,-1) Right 2, down 1 (-2,+1) Left 2, up 1 (+1,+3) (-1,-3) Prove that this robot can never reach (1,1) ...
6.4. Strong Induction vs. Induction vs. Well Ordering 151 (a)Give a mathematical model of the Authority’s system for letting car ...
Chapter 6 Induction152 (a)Model this situation as a state machine, carefully defining the set of states, the start state, and th ...
«
3
4
5
6
7
8
9
10
11
12
»
Free download pdf
