Exercises B

Note

You must complete these exercises by Wednesday of W3.

Exercise 1.2.1 (Inginious)

• What is the difference between an Iterable and an Iterator?

Implement a Circular Linked List and its iterator.

In your implementation, what is the time complexity of:

• public void enqueue(Item item)?

• public Item remove(int index) ?

• a sequence of operations which consists of creating an iterator and then iterating over the first k-elements?

Exercise 1.2.1 (Inginious)

In your implementation, you will need to resize the array if the size of the stack reaches the maximum size. oes Java have an efficient way to resize/refill an array? If yes, give an example of Java code to perform this operation.

Implement the Stack interface with an internal array-based implemenation and with a linked-list.

In your implementation, what is the time complexity of:

• public void push(E item)?

• a sequence of n push operations

Exercise 1.2.2

Post-fix notation (or Inverse Polish) is used to represent algebraic expressions. We consider for simplicity only post-fix expressions with positive integers and the + and * operators. For example 2 3 1 * + 9 * whose result is 45 and the result of 4 20 + 3 5 1 * * + is 39.

1. Write an algorithm in Java to evaluate a post-fix expression from a string of n-characters.

2. What data structure do you use?

3. What is the complexity of your algorithm (temporal and spatial)?

As a reminder, here is how you can iterate over the elements of a string that are separated by spaces.

String in = "4 20 + 3 5 1 * * +";
StringTokenizer tokenizer = new StringTokenizer(in);
while (tokenizer.hasMoreTokens()) {
     String element = tokenizer.nextToken();
}

Exercise 1.2.3 (Inginious)

Functional Programming is an increasingly important programming paradigm. In this programming paradigm, data structures are immutable. We are interested here in the implementation of an immutable list called FList allowing to be used in a functional framework. Here is the API of a FList

public abstract class FList<A> implements Iterable<A> {

    // creates an empty list
    public static <A> FList<A> nil();

    // prepend a to the list and return the new list
    public final FList<A> cons(final A a);

    public final boolean isNotEmpty();

    public final boolean isEmpty();

    public final int length();

    // return the head element of the list
    public abstract A head();

    // return the tail of the list
    public abstract FList<A> tail();

    // return a list on which each element has been applied function f
    public final <B> FList<B> map(Function<A,B> f);

    // return a list on which only the elements that satisfies predicate are kept
    public final FList<A> filter(Predicate<A> f);

    // return an iterator on the element of the list
    public Iterator<A> iterator();

}

As you can see, none of the methods allow you to modify the state of the list. Here is an example of manipulation of such a list. If you are unfamiliar with the https://docs.oracle.com/javase/8/docs/api/java/util/function/package-summary.html functional interfaces of Java8, we ask that you familiarize yourself with these first.

FList<Integer> list = FList.nil();

for (int i = 0; i < 10; i++) {
    list = list.cons(i);
}
// list = 9,8,7,...,0

list = list.map(i -> i+1);
// will print 10,9,...,1
for (Integer i: list) {
    System.out.println(i);
}

list = list.filter(i -> i%2 == 0);
// will print 10,...,6,4,2
for (Integer i: list) {
    System.out.println(i);
}

Here is a partial implementation of the FList

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.function.Function;
import java.util.function.Predicate;

public abstract class FList<A> implements Iterable<A> {

    public final boolean isNotEmpty() {
        return this instanceof Cons;
    }

    public final boolean isEmpty() {
        return this instanceof Nil;
    }

    public final int length() {
        // TODO
    }

    public abstract A head();

    public abstract FList<A> tail();

    public static <A> FList<A> nil() {
        return (Nil<A>) Nil.INSTANCE;
    }

    public final FList<A> cons(final A a) {
        return new Cons(a, this);
    }

    public final <B> FList<B> map(Function<A,B> f) {
        // TODO
    }

    public final FList<A> filter(Predicate<A> f) {
        // TODO
    }


    public Iterator<A> iterator() {
        return new Iterator<A>() {
            // complete this class


            public boolean hasNext() {
              // TODO
            }

            public A next() {
              // TODO
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }


    private static final class Nil<A> extends FList<A> {
        public static final Nil<Object> INSTANCE = new Nil();
        // TODO
    }

    private static final class Cons<A> extends FList<A> {
        // TODO
    }


}

We ask you to

• complete this implementation, if possible use recursive methods as much as possible.

• determine the complexity of each method.

The inginious taks is the following: FList

Exercise 1.2.4

Fill in the following table with the complexities of each operation? If an operation is not possible (for example, going to the middle of a Stack is impossible because not provided for by the TAD, indicate it with a cross. Specify each time if it is an amortized complexity or not. SL = Simply Linked List, DL = Doubly Linked List, Arr = Array with redimentioning.

Complexité

TAD	Implementation	Insertion (head)	Insertion (end)	Insertion (pos \(i\))	Remove (head)	Remove (end)	Remove (pos \(i\))	Get (head)	Get (end)	Get (pos \(i\))
Stack	SL
Queue	SL
Stack	Arr
Queue	Arr
List	SL
List	DL
Liste	Arr

What is this ?

Exercice 1.2.5

• Does Java provide a class for Stack, Vector, List?

  If so in which package? In your opinion, is it interesting to know this package well for the exam? Is List an interface or a class? How to create an object of type List? And an object of type Queue?

• What is the error in the following code where the student is looking to create an array of 5 lists and then insert the integer 4 into the 3rd list? Correct the code.

  List<Integer>[] myList = new List<Integer>[5];
  myList[2].add(4);
  

• What is the error in the following code where the student is trying to create an Iterable object? Correct the code.

  Iterable<Integer> myIterable = new Iterable<Integer>();
  

• What is the error in the following code where the student is trying to define a constructor?

  public class ADT {
    private int n = 4;
    private ADT myAdt;
    public ADT(int n) {
      n = n;
      myAdt = new ADT(4);
    }
  }
  

• What is the time complexity of is this code, given the size of the list, \(n\)? How to improve it?

  void printList(List<Integer> l) {
      for (int i = 0; i < l.size(); i++) {
          int elem = l.get(i);
          System.out.println(elem);
      }
  }