Workshop 5A

Workshop 5A#

Practice#

If you have not done so yet, fork the template workshop repository and clone it to your computer.

Create a folder called ws5a in your workshop repository. You may want to download the gitlab-ci file and put it in the root directory of your repository (i.e. outside ws5a). Rename it to .gitlab-ci.yml - the . at the start is important! Commit and push your work when you are done.

TreeContains#

In a file called TreeContains.java in ws5a

Design the following function:

//[T] represents your type for binary trees of Integers, where
// Integers are contained in inner nodes only (leaves are empty)

/**
 * returns true if the given tree contains the given number
 * somewhere in it, false otherwise
 */
boolean treeContains([T] tree, int number)

Follow the Design Recipe!

Provide the following testing interface:

/** creates a leaf node of your tree type */
[T] makeLeafNode()
/**
 * creates an inner node of your tree type, containing
 * the given number
 */
[T] makeInnerNode([T] left, [T] right, int number)

TreeLevels#

In a file called TreeLevels.java in ws5a

A “level” of a tree expresses the number of ancestor nodes one would have to go through to get to the root. So the root node is at level 0, its immediate children are at level 1, their immediate children are at level 2, and so on.

Design the following function:

//[T] represents your type for trees with arbitrarily
// many children per node, each of which contain an integer

/**
 * returns all the numbers on the given level of
 * the tree, from left to right
 */
ConsList<Integer> treeLevel([T] tree, int number)

Follow the Design Recipe!

Provide the following testing interface:

/** creates a new node of your tree type with the
 * given children, containing the given number
*/
[T] makeNode(ConsList<[T]> children, int number)

CharacterCount#

In a file called CharacterCount.java in ws5a

Design the following functions:

/**
 * returns a cons-list-based map that maps each character
 * in the given string to how often the character appears
 * in the string
 */
ConsList<Pair<Character,Integer>> characterCountCons(String str)
/**
 * returns a stateful hash map that maps each character
 * in the given string to how often the character appears
 * in the string
 */
Map<Character,Integer> characterCountHash(String str)

Follow the Design Recipe!