1. Recall the activity from the first day of class » Every student starts with a
ID: 3603560 • 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, Suml -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 * whoever has the earlier 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) At any point in the process, the bottom paper in each stack is the latest birthday among all the papers in the stack (g) Are there any other loop invariants that you can think of?Explanation / Answer
a) this is a loop invariant because before start of the loop, every one has its own paper, inside the loop, one with earlier birthday gets to keep stack of other under his own stack, so owner's name will always be on top of the stack.
b) this is not loop invariant, consider following cases
Person1 28 MARCH 1990
Person2 30 MARCH 1990
Person3 26 MARCH 1990
Iteration 1 : Person2 finds Person3
Now, Person3 has following papers on stack {26 MARCH 1990, 30 MARCH 1990}
Iteration 2 : Person1 finds Person3
Now, Person3 has earlier birthday, so he will place other person's stack below his own stack
{26 MARCH 1990, 30 MARCH 1990, 28 MARCH 1990},
so stack is not sorted
c) yes, it is loop invariant, because everytime two stacks are combined sum1 contains sum of both sum1's values,
d) No , this is not loop invariant, as initially all person are holding the paper, and only one of them could be earlier
e) as explained in answer b), this is not loop invariant
f) this question is similar to e)
g) no
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.