Week 3: Exercises

1. Dynamic Array

Write a class DynArray that represents a variable-sized array of integers, with indices starting at 0. It should have the following members:

• DynArray() - create a new empty DynArray

• int length() - return the current array length

• void append(int i) - append an integer to the array

• int get(int index) - read the integer at the given index

• void set(int index, int val) - set the integer at the given index, which must be within the current array bounds

Do not use the C# class List<T> in your implementation! The point of this exercise is to implement a dynamic array yourself, using arrays.

What will be the average-case big-O running time of append()?

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()

• void enqueue(int i)

• int dequeue()

• bool tryDequeue(out int i)

All operations should run in O(1).

3. Binary Tree

Write a class BinaryTree that holds a binary search tree of integers. Your class should have these members:

• BinaryTree() - create a BinaryTree that is initially empty

• void insert(int i) - insert a value into the tree if it is not already present

• bool contains(int i) - return true if the tree contains the value i, otherwise false

• int[] toArray() - return an array holding all the values in the binary tree, in ascending order

For an extra challenge, you may write a method that removes a value from the tree.

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.

6. Set of Longs

Write a class Set that represents a set of values of type 'long'. Your class should have the following members:

• Set() - create a new empty set

• int count { get; } - return the number of elements in a set

• void add(long l) - add a value to the set if not already present

• bool contains(long l) - return true if the set contains the given value, otherwise false

What will be the average-case big-O running time of add() and contains()?

7. Wordle

In the game of Wordle, one player (A) thinks of a 5-letter English word. The other player (B) tries to deduce the word by making a series of guesses, each of which must be a 5-letter English word. After each guess, player A reveals which letters are green, i.e. they are correct and in the correct position, and which are yellow, i.e. they are correct, but not in the correct position. For example, if the word is SNAIL and the guess is SPIKE, then the S is green and the I is yellow. Player B must guess the word within 6 attempts, otherwise the game is lost.

Write a program that chooses a random word and lets the user try to guess it. The program should print each of the user's guesses with green or yellow letters as appropriate.

Here is a dictionary of 5-letter words in English that your progam can use.