1) (a) Consider the following axioms from the Unsorted List ADT:
Delete(Create, i1) = Create
Delete(Make(L1, i2), i1) =
IF i1 = i2 THEN
L1
ELSE
Make(Delete(L1, i1), i2)
END IF
Briefly describe the behaviour of the Delete operation as defined by these axioms.
What changes would you make to the above axioms in order to carry out the other two types of deletion discussed in class?
(b) The interface file for a linked list implementation of the Unsorted List ADT offers the following methods:
public void make(Object item);
public void delete(Object item);
public ListReferenceBased concat(ListReferenceBased list2);
public ListReferenceBased tail();
public boolean isEmpty();
public boolean isIn(Object item);
public Object head();
public int length();
Write java code for a method that finds the smallest integer in an unsorted list of integers.
This method is to appear in a client program, thus must use methods from the above interface file. You do not need to handle exceptions. Assume the following skeleton:
public static Integer findSmallest(ListReferenceBased list) {
}
Provide appropriate PRE and POST conditions for your method.
(c) Describe and illustrate how items are normally added and removed from an efficient implementation of the queue ADT, as defined in class, which is implemented using an array.
What problems may arise in testing for an empty or a full queue and how might these be overcome?
Give two applications of a queue in computing.