581325-0 Data Structures, 1. Course Examination 28.2.2003/AW

1. An array of Objects that has "variable size" would sometimes be a handy tool for programmers. Let us make one! We define the class Vector as the following operations: (this comes from Java^TM 2 Platform Std. Ed. v1.3 ) (Do not program all of these!)
   1. public Vector(): Constructs an empty vector.
   2. public int size(): Returns the number of components in this vector.
   3. public boolean isEmpty(): Tests if this vector has no components.

   4. public int indexOf(Object elem): Searches for the first occurence of the given argument, testing for equality using the equals method.
   5. public int lastIndexOf(Object elem): Returns the index of the last occurrence of the specified object in this vector.

   6. public Object get(int index): Returns the element at the specified position in this Vector.
   7. public Object set(int index, Object element): Replaces the element at the specified position in this Vector with the specified element.

   8. public boolean add(Object o): Appends the specified element to the end of this Vector.
   9. public boolean remove(Object o): Removes the first occurrence of the specified element in this Vector If the Vector does not contain the element, it is unchanged.
   10. public void add(int index, Object element): Inserts the specified element at the specified position in this Vector. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
   11. public Object remove(int index): Removes the element at the specified position in this Vector. Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the Vector.
   1. Explain the implementation of class Vector so that the components are kept in an array and implement the operations 1, 2, 5, 6, 8 and 11. If the default array (let us say 10 elements) becomes too small, it is replaced by a bigger one. Try to program effective implementations.
   2. Explain the implementation of class Vector as a double linked list and implement the operations 1, 2, 4, 7, 9 and 10. Try to program effective implementations.

                                                                 (8 points)
   
   
   
   

2. One of your friends doesn't completely undestand the idea of using the O ("Big O") in estimating the running times of algorithms. Help your friend and give him/her examples of algorithms that belong to O(1), O(log n), O(n), O(n²) and O(2ⁿ). Your friend is suspicious! So justify your answers. Why each of the algorithms belongs to a certain class.

                                                                 (8 points)
   
   

3. A tree, where the nodes have 0 to 3 children could be called "trinary" tree. Let each node also have fields for the height and depth of the node:

      public class Tree {
        public Object data;
        public int height, depth;
        public Tree left, middle, right;
      }
   

   Program the following methods for "trinary" tree:
   1. public static void setDepths(Tree root): sets the depth-field of every node in the tree

   2. public static void setHeights(Tree root): sets the height-field of every node in the tree

                                                                    (8 points)