1. Recall the activity from the first day of class: .Every student starts with a
ID: 3603533 • Letter: 1
Question
1. Recall the activity from the first day of class: .Every student starts with a piece of paper with their name, the month and day of their birthday, Sumi 1 and Sum2 1 .Repeat until only one person has papers: - If you have a pile of paper, find someone else with a pile of paper and do: (if there are an odd number of people, one person may have to skip this round.) s whoever has the eaier birthday: Sum your two Suml values together and write that as your new Suml value Add 1 to your Sum2 value Take the other person's stack and put it under your stack. Which of the following are loop invariants? (if it is a loop invariant, state why it is true for the base case and give a brief justification of why it is a loop invariant. If it is not a loop invariant, give a reason (a) At any point in the process all stacks have their owner's name on top (b) At any point in the process, all stacks are sorted (c) At any point in the process, Suml on the top paper of a stack will be equal to the number of papers in the stack. (d) At any point in the process, The person with the earliest birthday will be holding papers. (e) At any point in the process, the bottom paper in each stack is the latest birthday among all the papers in the stack. (f) Are there any other loop invariants that you can think of?Explanation / Answer
(a) This is a loop invariant.
Initially, every student has only one paper with his own name. So the invariant holds.
Suppose after i iterations, the invariant holds, i.e. every student having a pile has his own name on the top. If at the (i+1)th iteration, S1 takes the stack of S2, and puts it under his stack. So the top of the stack with S1 has the same name as it had before the iteration. So the invariant still holds after i+1 iterations if it was true after i iterations.
(b) This is not a loop invariant. This can be shown with a counter example.
Consider 4 students, S1, S2, S3, S4 with DOBs D1, D2, D3, D4, with the ordering of DOBs being D1 < D3 < D2 < D4.
At the first iteration, suppose the pairing is (S1, S2) and (S3, S4). So S1 takes S2's stack and puts it below his stack. So S1 now has (from top to bottom) - D1, D2. Similarly S3 has D3, D4. At the next iteration, S1 will take S3's stack and put it below his stack with the resultant stack being: D1, D2, D3, D4. This is not in sorted order, since D3 < D2.
(c) This is a loop invariant.
Initially, every student has one paper in his stack with S1 = 1. So the invariant holds.
Suppose the invariant holds after i iterations. So for students Sj and Sk, S1(Sj) and S1(Sk) denote number of papers in the stack with Sj and Sk respectively. If Sj takes Sk's stack at the (i+i)th iteration, the new S1 value for Sj will be S1(Sj) + S1(Sk). The number of papers in the resultant stack will be the sum of the papers in the stacks of Sj and Sk before the iteration, which is again S1(Sj) + S1(Sk). So the invariant holds after i+1 iterations if it held true after i iterations.
(d) This is a loop invariant.
Initially, every student holds one paper. So the invariant holds true trivially.
Suppose after i iterations, the student with the earliest birthday holds papers. Let Smin denote the student and Dmin his birthday. At the (i+1)th iteration, if Smin is paired with Sj having birthday Dj, then we know that Dmin < Dj, since Dmin is the earliest birthday. So, Smin will take over the stack of Sj and the invariant will still hold true after i+1 iterations if it held true after i iterations.
(e) This is not a loop invariant.
This can be shown using a counter example. Consider 4 students, S1, S2, S3, S4 with their DOB being in the order D1 < D2 < D3 < D4. Suppose the pairs formed in the first iteration are: (S1, S4), (S2, S3). So S1 takes S4's stack to get the following resultant stack from top to bottom: D1, D4. Similarly S2 has D2, D3. In the next iteration, S1 takes over S2's stack to get the following resultant stack: D1, D4, D2, D3. So, the latest birthday, D4 is not at the bottom of the stack.
(f) The following invariant will hold:
At any point in the process, the sum of S1 values at the top of the stacks will be the same, and will be equal to the total number of students.
Initially, every student has one paper in his stack with S1 = 1 for all students with n being the number of students. So the sum of the S1 values at the top of the stack is 1 X (No. of students) = n. So the invariant holds in the base case.
Suppose the invariant is true after i iterations. We can show that it will also hold after i+1 iterations. Consider any pair Sj and Sk paired at the (I+1)th iteration. Denote their S1 values after iteration i as S1(j) and S1(k). So we have:
S = S1(j) + S1(k) + R = n, where R denotes of the sum of the top of stacks for all students except Sj and Sk, S denotes the sum of the S1 values of the top of the stacks.
Suppose Sj has the lower of the two birthdays, and therefore takes over Sk's stack. Since Sk's stack is no longer present, its contribution becomes zero. The new value of S1 for Sj's stack will be S1(j) + S1(k). So S = [ S1(j) + S1(k) ] + 0 + R = S1(j) + S1(k) + R = n. So the moving of a stack to another student accompanied by modification of S1 values does not have any effect on the sum of S1's at the top of the stack. So the invariant holds after i+1 iterations if it held after i iterations.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.