Part 2: Choose one of the following questions: 1. Argue why linked list update in the cost model where swaps involving the searched item cost 0 is not a metrical task

system. Model the problem as a request-answer game. 2. Prove that if a MTS algorithm ais C-competitive against sequences of elementary cost vectors, then it is C-competitive against any sequence of (non-negative) cost vectors. 3. Show that layered graph traversal where the input satisfies that for all t IX: ≤ 2 has a deterministic 9-competitive online algorithm. You may assume that the minimum non-zero distance is 1.