TDT4125: Aleksanders Conflicted Algkons Compendium
Amortized analysis
17.1-1 Aggregate Analysis
A multipush operation multipush(stack, n) is teta(n) cost. A push operation is O(1) A pop operation is O(1) A MultiPop is min(S, k) A MultiPush is k
Multipush is amortized over the k elements pushed, which gives it an amortized cost of teta(k) / k per element pushed, or Teta(1).
N combinations of push, pop, multipop, and multipush (All O(1) amortized) gives us O(n) / n = O(1).
17.1-2
If we allow a decrement operations, we allow for the line of operations consisting of maxint + 1 - 1 + 1 - 1 + 1 -1. Maxint +1 involves flipping all the 1-bits to 0, and MinInt + 1 the converse. This makes each operation Theta(k), resulting in Theta(n*k) as there are no other operations to amortize the cost over.
17.1-3
The total cost for n operations would be bounded by SUM(1..n)(1) + SUM(1..floor(log(n)))(2**i). This is bounded by n + 2n = O(n). Over n operations, this becomes O(n) / n -> O(1) amortized cost.
17.2-1 Accounting method
At worst, we will need k credits at a copy state. Between two copies, there will be k push or pop operations. By making push and pop operations pay for themselves, as well as one extra credit, k push and pop operations will have left k * 1 credits on the stack when the next copy comes around, guaranteeing that all copy operations can be performed.
17.2-2 When it's time to pay for each power of two (2^i), there will have been i debt collections. If there at the i'th iteration is available 1 ticket for each, everything goes fine. By having each operation pay 1 for the operation itself, 1 for the upcoming 2^i, and 1 for one of the numbers < i/2 that have used up all their credits for the previous 2^(i-1) wall we guarantee that all 2^i walls can be met.
In total, O(3).
17.2-3
We assume that updating max costs zero time.
As we have a pointer to the largest 1 bit, we only need to flip bits from max downto 0. As before, whenever a bit is set to 1, we pay 1 for the setting to 1, 1 for the future setting to 0, and 1 for the newly added peek-cost. In total 3. Resetting will then still cost 0 as all the peek-and-bitflips have been paid for.
If we assume that updating max costs O(1), add one cost to increment and reset, resulting in costs of 4 and 1.
17.3-1 Potential method
NP problems
34.2-1
Sort both columns and rows of both graph's neighbor matrixes with a stable sort. If the result is equal, the graphs are isomorphic. Running time O(4nlog(n)) = O(n*log(n)).
34.2-2
If G is an undirected bipartite graph with an odd umber of vertices, then G is nonhamiltonian. With subgraphs a, b, |a| =/= |b|, after visiting min(|a|, |b|)*2 vertices, you will be stuck in max(a, b), with no way to
a) visit the final vertices in max(a, b) b) return to the original vertice you started at
as there are no more vertices in min(a, b) to jump via,