Programming project 8

Morse decoder

In this task you build a decoder for the Morse alphabet using a decision tree.

Download morse.scala. I've already implemented the node class Morse and entered the decision tree for you. Your task is to implement the missing method decode. It should be recursive. Do not modify anything else in the code.

Here is what running the program looks like when you have implemented decode correctly.

> scala MorseDecoder
Enter a Morse string: ...
Enter a Morse string: ... --- ...
Enter a Morse string: ... --- ...  ... --- ...
Enter a Morse string: -.-. ...  .. ...  ..-. ..- -.
Enter a Morse string: --. --- --- -..  .-.. ..- -.-. -.-  --- -.  - .... .  ..-. .. -. .- .-..
Enter a Morse string: 

Hash table

I have implemented a mutable Set using a hash table with linear probing in the file hashset.scala.

Your task is to fill in the missing methods doubleTable and -=.

The private method doubleTable is called when the load factor of the hash table reaches \(0.7\). It should create a new table of two times the size of the previous one, and transfer all elements from the old table to the new one. Be careful to put them in a slot where they can be found by the hash function of the new table!

The method -= removes an element from the set (if the element is not in the set, it does nothing).

Remember, when you have found the element to be deleted, you cannot simply delete it—otherwise some elements cannot be found in the future, see our lecture slides.

So what you have to do is to continue searching until you find some element that can be placed in the slot that has just become empty. This may again create an empty slot that has to be filled in the same way. Continue this way until reach an empty slot.