Exercises B#

Note

You must complete these exercises by Wednesday of W3.

Exercise 1.2.1 (INGInious: Circular Linked List)#

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 consisting of creating an iterator and then iterating over the first k elements?

Exercise 1.2.2 (INGInious: Implement a stack with an Array)#

In your implementation, you will need to resize the array if the size of the stack reaches the maximum size. Does 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 implementation 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.3#

Postfix notation (or Reverse Polish notation) is used to represent algebraic expressions. For simplicity, we only consider postfix expressions with positive integers and the + and * operators: for example, 2 3 1 * + 9 *, which evaluates to 45, and 4 20 + 3 5 1 * * +, which evaluates to 39.

Write an algorithm in Java to evaluate a postfix expression from a string of \(n\) characters.
What data structure do you use?
What is the time and space complexity of your algorithm?

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.4 (INGInious: Functional Lists)#

Functional Programming is an increasingly important programming paradigm. In this programming paradigm, data structures are immutable. We are interested here in implementing an immutable list called FList designed for use in a functional framework. Here is the API of 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 where function f has been applied to each element
    public final <B> FList<B> map(Function<A,B> f);

    // return a list containing only the elements that satisfy the predicate
    public final FList<A> filter(Predicate<A> f);

    // return an iterator over the elements 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 manipulating such a list. If you are unfamiliar with Java 8 functional interfaces, we recommend familiarizing yourself with them 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 (prefer recursive methods where appropriate).
determine the time complexity of each method.

The INGInious task is the following: FList.

Exercise 1.2.5#

Fill in the following table with the time complexity of each operation. If an operation is not supported (for example, accessing the middle of a Stack is not supported by the ADT), indicate it with a cross. Specify in each case whether it is an amortized complexity. SL = Singly Linked List, DL = Doubly Linked List, Arr = Resizing Array.

Complexity#
ADT	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
List	Arr

Exercise 1.2.6#

Does Java provide classes for Stack, Vector, List? If so, in which package? In your opinion, is it important to know this package well for the exam? Is List an interface or a class? How can you create an object of type List? What about an object of type Queue?
What is the error in the following code where the student is trying 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 this code, given a list of size \(n\)? How can it be improved?

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