Repeat the amortised analysis of simple persistent queues on two lists $($in a single$-$use case$),$ but using the banker's method. What is the credit invariant?

Note that the reverse function on persistent lists is not defined in the notes: define it yourself! It should work in linear time.

FIFO and LIFO queues can be generalised to double$-$ended queues $($often known as deques$),$ which allow insertion and deletion from both ends of the queue. Generalise the persistent implementation of queues to fulfill an appropriate deque interface, and show that all operations can be performed in amortised constant time.

Hint: Consider what cases should have potential of $0/$no credits. How can you obtain them from cases of high potential?

The amortised complexity doesn't always need to be constant. Show that the union$-$find data structure with arbitrary unions $($i$.$e$.,$ no optimisation of unions, can always pick left as a root, for instance$),$ but with path compression supports both union and find operations in amortised time O$($log n$).$

Hint: The analysis is slightly more complex this time. It is enough to consider find and union with the assumption that union is always called on roots of the respective sets $($since find has the same complexity$)$ in my analysis, both of these take logarithmic time. Banker's method was much more natural for me here, and all nodes except for roots and leaves contained some credits in my invariant.