Week 3: Exercises

1. Vector

Expand the Vector class that we begin writing in the lecture:

class Vector {
    double[] v;
    
    public Vector(params double[] v) {
        this.v = v;
    }

    …
}

Add these elements:

• a read-only property dims that returns the number of dimensions of the vector

• a read-only property isZero that is true if the vector is zero

• an operator * that multiplies a scalar times a vector, yielding a new vector

• an operator * that computes the dot product of two vectors, yielding a scalar

• a method angle that computes the angle between two vectors in radians

2. Queue

Write a class Queue implementing a queue of integers. A queue should have an unlimited size. The Queue class should have these members:

Queue()

bool isEmpty { get; }

void enqueue(int i)

int dequeue()

3. Shortest Path

You are given a class Graph that holds a graph in adjacency-list representation:

class Graph {

 int[][] edge;


 public Graph(…) { }

}

Write the following method:

int[] shortestPath(int start, int end)

Return an array containing a list of vertices along the shortest path from (start) to (end). If there is no path from (start) to (end), return null.

4. Array to Tree

Write a method that takes an array containing a sorted list of integers and returns a binary search tree containing all the values in the array. The tree should be as balanced as possible, i.e. it should have the minimum possible height.

5. Tree Check

Write a method that takes a binary tree and returns true if the tree satisfies the ordering requirements of a binary search tree.