Algorithm Analysis (45% = 15% X 3)
1. Briefly describe how to perform a new sequence method makeFirst (p) that moves an element of a sequence S at position p to be the first element in S while keeping the relative ordering of the remaining elements in S unchanged. That is, makeFirst (p) performs a move-to-front. Your method should run in O(1) time if S is implemented with a doubly linked list. (Need pseudo-code, and remove and addFirst methods cannot be used).

2. Using the Sequence interface methods, describe a recursive method for determining if a sequence S of n integers contains a given integer k. Your method should not contain any loops.

3. Suppose we are keeping track of access counts in a list L of n elements. Suppose further that we have made kn total accesses to the elements in L, for some integer k >= 1. What are the minimum and maximum numbers of elements that have been accessed fewer than k times?

The coding part (55%)

1. To implement the class FavoriteTester given below

import java.io.*;
import javax.swing.*;
import java.awt.*;
import java.net.*;
import java.util.Random;
/** Example program for the FavoriteList and FavoriteListMTF classes */
public class FavoriteTester {
public static void main(String[] args) {
String[] urlArray = {"http://wiley.com", "http://datastructures.net",
"http://algorithmdesign.net", "http://www.brown.edu",
"http://uci.edu" };
FavoriteList<String> L1 = new FavoriteList<String>();
FavoriteListMTF<String> L2 = newFavoriteListMTF<String>();
int n = 20; // number of access operations
// Simulation scenario: access n times a random URL
Random rand = new Random();
for (int k = 0; k < n; k++) {
System.out.println("-------------------------------------------");
int i = rand.nextInt(urlArray.length); // random index
String url = urlArray[i]; // random URL
System.out.println("Accessing: " + url);
L1.access(url);
System.out.println("L1 = " + L1);
L2.access(url);
System.out.println("L2 = " + L2);
}
int t = L1.size()/2;
System.out.println("-------------------------------------------");
System.out.println("Top " + t + " in L1 = " + L1.top(t));
System.out.println("Top " + t + " in L2 = " + L2.top(t));
// Pop up a browser window displaying the most popular URL in L1
try {
String popular = L1.top(1).iterator().next(); // most popular URL in L1
JEditorPane jep = new JEditorPane(popular);
jep.setEditable(false);
JFrame frame = new JFrame(popular);
frame.getContentPane().add(newJScrollPane(jep), BorderLayout.CENTER);
frame.setSize(640, 480);
frame.setVisible(true);
} catch (IOException e) { // ignore I/O exceptions
}
}
}

You need the PositionList interface as well as all necessary codes, and then debug them