Week 2: Exercises

1. Dynamic Array

Write a class DynArray representing a dynamic (i.e. resizable) array of integers. It should have these members:

DynArray()

Create a new DynArray that is initially empty.

DynArray(int length)

Create a new DynArray with the given initial length. All elements will be 0.

DynArray(int length, int val)

Create a new DynArray with the given initial length. All elements will initially be set to val.

int get(int index)

Retrieve the value at the given index, which must be less than the current array length.

void set(int index, int val)

Set the value at the given index, which must be less than the current array length.

void append(int i)

Append a new element to the array, growing its length by 1.

int getLength()

Get the current length of the array.

void setLength(int length)

Set the array length. All new elements will be 0.

int[] toArray()

Return an ordinary C# array holding all the elements of the dynamic array.

For example, your class could be used like this:

DynArray d = new DynArray(3, 7);
for (int i = 0 ; i < 3 ; ++i)
  d.append(i);
d.set(0, 100);
d.set(5, 100);
for (int i = 0 ; i < d.getLength() ; ++i)
  WriteLine(d.get(i));   // writes 100, 7, 7, 0, 1, 100

2. Graph

Write a class Graph that holds a directed graph, with vertices numbered from 0 to (N – 1).

The class should have these members:

Graph(string filename)

Build a graph, reading vertex/edge data from the given file, which will look e.g. like this:

4       // first line contains number of vertices
1 2     // neighbors of vertex 0
0 3     // neighbors of vertex 1
0 1 3   // neighbors of vertex 2
0       // neighbors of vertex 3

bool hasCycle()

Return true if the graph contains any cycles (including any edge from a vertex to itself).