Algorithms and Complexity

CIS 621 Assignment 2

Prove correctness of the Stable Matching algorithm (page 6) by loop invariant. Hint: the property "current engagement list (ENG) represents stable matching of its constituents" is the crucial conjunct of a useful invariant. Some additional properties of the preference lists (as conjuncts of I) are necessary to prove "[I and C] B [I]".
(Remedial amortized complexity exercise) Implement a FIFO queue with two LIFO data structures (stacks), so that the amortized complexity of queue operations (enQueue and deQueue) is constant. Compare this with the worst-case complexity of these operations. Show correctness of your implementation using loop invariant and complexity using credit invariant argument.
Suppose that the initial state of a counter with $n$ bits has $b$ 1's. Show using credit invariant argument that the cost of performing $m$ Increment operations is $O(m)$ if $m\in\Omega(b)$.
Use a credit invariant argument to show linearity of the Topological Sorting algorithm.
Assume an implementation of Priority Queue (PQ) that allows logarithmic meld of two queues. Prove linearity of the following "round robin" algorithm to meld $m$ Priority Queues: given a (FIFO) list of PQ, meld the two first of them and remove them from the list, appending the resulting PQ to the end.