In this example, we prove that if we pop the following list
[3, [2, [1, []]]]
At index 2, and the "visited" list is empty, the resulting list is
[3, [2, []]]
First, we use the induction step to pop 3, then 2, from the list and add them to the "visited" list. The index is also decremented twice. Then in step 7, we claim that we need to 1) reverse and insert the remaining list to the "visited" list, then 2) reverse the resulting list. Since the remaining list is empty, we really just need to reverse the "visited" list.
And in the remaining steps, we use the Transitive Property to reach the conclusion.
Quiz (1 point)
- remaining elements after [ x, xs ] is popped at index idx and visited stack is v = remaining elements after xs is popped at index (idx - 1) and visited stack is [ x, v ]
- 2 - 1 = 1
- remaining elements after [ x, xs ] is popped at index idx and visited stack is v = remaining elements after xs is popped at index (idx - 1) and visited stack is [ x, v ]
- 1 - 1 = 0
- remaining elements after [ x, xs ] is popped at index 0 and visited stack is ys = reverse of (result of dumping xs to ys)
- result of dumping [ ] to xs = xs
- reverse of [ x, [ y, [ ] ] ] = [ y, [ x, [ ] ] ]
if 2 - 1 = 1, then remaining elements after [ 2, [ 1, [ ] ] ] is popped at index (2 - 1) and visited stack is [ 3, [ ] ] = remaining elements after [ 2, [ 1, [ ] ] ] is popped at index 1 and visited stack is [ 3, [ ] ]
if 1 - 1 = 0, then remaining elements after [ 1, [ ] ] is popped at index (1 - 1) and visited stack is [ 2, [ 3, [ ] ] ] = remaining elements after [ 1, [ ] ] is popped at index 0 and visited stack is [ 2, [ 3, [ ] ] ]
if result of dumping [ ] to [ 2, [ 3, [ ] ] ] = [ 2, [ 3, [ ] ] ], then reverse of (result of dumping [ ] to [ 2, [ 3, [ ] ] ]) = reverse of [ 2, [ 3, [ ] ] ]
if the following are true:
- a = b
- b = c
then a = c
if the following are true:
- a = b
- b = c
then a = c
if the following are true:
- a = b
- b = c
- c = d
then a = d
if the following are true:
- a = b
- b = c
- c = d
then a = d
Please write your proof in the table below. Each row should contain one claim. The last claim is the statement that you are trying to prove.