• Every student starts with a piece of paper with their name, the month and day
ID: 3603541 • Letter: #
Question
• Every student starts with a piece of paper with their name, the month and day of their birthday, Sum1 = 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 Sum1 values together and write that as your new Sum1 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, Sum1 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) At any point in the process all stacks have their owner’s name on top
Each person puts the other person stack below its own stack.. Hence, The top of the stack sould be of owner itself....True
(b) At any point in the process, all stacks are sorted
False.. Stack A may be Jan7, MAr7
Stack B can be Feb7, Apr7..
So Stack A has earlier birthday, hence A will put B's stack below its own..
Complete stack will become
Jan7, Mar7, Feb7, Apr7.. So It is not sorted.. Hence false
(c) At any point in the process, Sum1 on the top paper of a stack will be equal to the number of papers in the stack.
True, Whenever we put a paper below our stack, we change the sum1 value of the top paper.. For a single paper, sum1 value is 1(base case). Hence at any point, the top paper contains the count of total papers in the stack.
(d) At any point in the process, The person with the earliest birthday will be holding papers.
True.. At any point, the top of the stack contains the least birthday in the stack.. hence when two stacks are joined, they also are put in order so that the top is earliest of them.. Hence the person holding holds the stack whose top is earliest birthday.
(e) At any point in the process, the bottom paper in each stack is the latest birthday among all the papers in the stack.
False.. Stack A may be Jan7, MAr7
Stack B can be Feb7, Feb27..
So Stack A has earlier birthday, hence A will put B's stack below its own..
Complete stack will become
Jan7, Mar7, Feb7, Feb27.. So The last paper is not the latest, rather Mar7 is latest.. Hence false
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.