Important: This is the third of three labs. This is an assessed lab. You have the choice to
complete the lab in C, Java or Python. Program stubs for this exercise exist for each language. Only
one language solution will be marked. To submit your work please run the submit script in the
relevant directory this means:
? If you are submitting a C solution you should run submit lab3 c.sh
? If you are submitting a Java solution you should run submit lab3 java.sh
? If you are submitting a Python solution you should run submit lab3 python.sh
The most recent submission is the one that will count.
Also Important: After submitting your code log in to COMPjudge to check that you are passing
all of the tests (see Blackboard for details on COMPjudge). If you are not then you can resubmit.
If you do not see the submission in COMPjudge then first check that you can see the tag in your
GitLab page — make sure you are on the correct branch for the submit scripts to work.
For this assignment, you can only get full credit if you do not use code from outside
sources.
Note on extension activities: The marking scheme for this lab is organised so that you can get
over 80% without attempting any of the extension activities. These activities are directed at those
wanting a challenge and may take considerable extra time or effort.
Reminder: It is bad practice to include automatically generated files in source control (e.g. your git
repositories). This applies to object files (C), class files (Java), and compiled bytecode files (Python).
This is a general poor practice but for this course it can also cause issues with the online tests.
1
Learning Objectives
By the end of this lab you will be able to:
? Describe the role of the hash function in the implementation of hash tables and describe and
compare various hash collision strategies
? Describe the basic structure of a binary search tree as well as the basic operations and their
complexities
? Write C, Java, or Python code to implement the above concepts
Introduction
The aim of this exercise is to use the context of a simple spell-checking program to explore the binary
search trees and hash tables data structures.
Data structures
The spell-checking stores the dictionary of words using a Set datatype. There are three data structures
used to implement this Set datatype in this lab. You have already used the dynamic array in Lab 1.
In this exercise we use hash tables and binary search trees to implement the Set datatype. These
have been introduced in lectures and we describe these briefly below. You may want to look at the
recommended textbooks or online to complete your knowledge.