1    Amortized Analysis

1.1    Potential Functions

Note:  This is  one is just a warm-up  on the potential method and an  excuse  to think about trees.

Consider a tree data structure t. We note:

● r the root of t

● n(x) the number of nodes in the subtree rooted at x

● h(x) the height of a node x

● dlow  and dhigh , the minimum and maximum depths of leaves

Among the following options, mark which potential functions are valid (note that  since  you  do  not  know  the  structure  of t  or  the  algorithm performed  on it,  you  cannot know which  ones  if any make  sense  to perform  amortized anal- ysis,  only whether they  are valid or not).  Argue why/why not.  Determine the potential of an empty tree for each.

1.  φ 1 (t) = n(r)2

2.  φ2 (t) = dlow 一 dhigh

3.  φ3 (t) = h(r) 一 dlow

4.  φ4 (t) = 2h(r) 一 n(r)

1.2    Move To Front

Note:  This is not an easy application of amortized complexity, but I am running out of  “simple/self-contained” examples to illustrate the concept.  It is an inter- esting and different application of it nonetheless, and one in which the aggregate method does not work.

Linked lists are notorious for having bad complexity for random  accesses.  To address this shortcoming, one approach is that of self-organizing lists. The idea of self-organizing lists is that the nodes in the list are dynamically rearranged based on how frequently they are accessed (it is thus in some way related to the concept of consolidation)

Move  to front  (MTF) is a heuristic technique for self-organizing lists that consists in moving an element to the front of the list when it is accessed.  For instance, accessing D in the following list has the indicated effect:

(A, B, C, D, E, F) → (D, A, B, C, E, F)

The complexity of these accesses can be compared to that of an “idealized” heuristic.  Consider a heuristic IDL that knows in advance in what order ele- ments will be accessed, and has the ability to reorder the list once (for free) before starting these accesses. The IDL heuristic does not reorder the list after each find operation (although it can further be shown that this does not change the result below).

Show that the amortized cost of findMTF  in a singly-linked list is within a constant multiplicative factor of that of findIDL .

1.  Start by finding a potential function that captures the difference in poten- tial between a list ordered according to MTF and one according to IDL. Both heuristics are given an identical list (thus the potential must be 0), then IDL performs a free one-time re-ordering, then find operations may be performed and their cost analyzed.

2.  Compute the change in your potential function after executing a  find operation in MTF and in IDL.

3.  Show the stated bound.

2    Graphs

Note:   Graph  stuff.   Good  exercise  to  test  your  understanding  on  graphs,  and manipulate formal definitions and statements on them.

The  edge-to-vertex  dual  of an unidrected graph G =  (V, E) is an undirected graph G#  = (V# , E# ) such that:

● V#  = E;

● E#  = {(ei , ej ) ∈ E2  l ei   ej  and a v ∈ V : v ∈ ei A v ∈ ej }.

In other words:  for each edge in G there is a vertex in G# ; and for every two edges in G that share a vertex, there is an edge between their corresponding vertices in G# .  Below is an example of a graph G (left) transformed into its edge-to-vertex dual G#  (right).