Assignment 3: Hashing
COMP 2140, Fall 2021
Due: Tuesday 2 November 2021 at 5:00 p.m
Instructions
• You must complete the “Honesty Declaration” checklist on the course website before you can submit
any assignment.
• Assignments must follow the programming standards document published on UM Learn.
• After the due date and time, assignments may be submitted, but will be subject to a late penalty. Please
see the course outline document published on UM Learn for the course policy for late submissions.
• If you make multiple submissions, only the most recent version (the last submission) will be marked.
We strongly encourage you to submit early!
• These assignments are your chance to learn the material for the exams. Code your assignments inde-
pendently. We use software to compare all submitted assignments to each other, and pursue academic
dishonesty vigorously.
• You can get help from the T.A. during your lab section and from the instructors and from the course
Assignment 3 discussion forum on UM Learn. You can discuss general topics related to the assignment
with fellow students or other people, but you cannot discuss the solution to the assignment with them.
You cannot copy code from anywhere except COMP 2140 class notes, unless we tell you otherwise. For a
full discussion of our expectations for individual work on this assignment, see the Department of Compute
Science’s expectations webpage.
• Your Java program must compile and run upon download, without requiring any modifica-
tions. The marker will not fix your program’s problems.
See also the “Hand in” instructions at the end of this assignment
Objective
To execute “programs” in a mini “programming language” (Karon) that has only integer variables, assignment
statements and simple integer expressions.
The Programming Language Karon
Here’s an example Karon program
length = 13
width = 10
area = length * width
extension = 14
fullarea = area + extension
t1 = XXXXXXXXXX
t1 = t1 / 4
t1 = 65 - t1
1
https:
sci.umanitoba.ca/cs/expectations
A Karon program consists of a sequence of assignment statements. Each assignment statement takes up one
line — there are no multi-line assignment statements in Karon. An assignment statement consists of a variable
name (described below), followed by an equals sign (=), followed by the right side of the assignment statement,
which can have one of the following two forms:
1. It can consist solely of one operand, which can be either an integer constant or a variable name.
2. It can consist of an operand, followed by an operator (’+’, ’-’, ’*’, or ’/’ ), followed by a second operand,
where each operand is either an integer constant or a variable name.
As you can see, variable names are strings of length at least one beginning with a letter and containing only
letters and numbers (all letters are lower case). All variables are integer variables.
A variable is “declared” when it first appears on the left side of an assignment statement. In other words,
ecause there are no separate variable declarations, only assignment statements, a variable declaration is an
assignment statement that assigns a value to the variable for the first time. So, the first time a variable appears
should be on the left side of an assignment statement. If a variable appears on the right side of an assignment
statement before it has had a value assigned to it, then we say that the variable is being used before it was
declared and that assignment statement contains an e
or.
For example, consider the following Karon program:
x = 3
= x
x = x + t
t = 36
Variables x and r are properly declared before they are used, but variable t is used before it is declared. Thus,
the assignment statement
x = x + t
is e
oneous.
The purpose of a Karon program is to compute values and store the values in variables. The output of a
Karon program is the values in the variables at the end of the program.
Your Program
You must write a program that reads in and executes Karon programs.
Your program will use a Dictionary to store “variable records”. Each variable record contains a variable
name and its associated value, with the variable name being the key. You will implement the Dictionary as a
hash table. (More information on the hash table below.)
For each assignment statement in a Karon program:
• Your program will read in an assignment statement as a String.
• You must first compute the value of the right side.
– There may be none, one, or two variables on the right side. For example, x = 3 has none, x = 32 +
t has one, and x = t * y has two.
– For each of the variables on the right side, you must find the variable in the Dictionary to retrieve
its value.
– For an integer constant, you can use Integer.parseInt() to retrieve its value.
– If there’s an operator on the right side, then, once you have the values of its operands, you must
perform the operation on the values of the two operands, to get the value of the right side.
• Then you must search the Dictionary for the variable on the left side of the assignment statement.
– If you find the variable, then you change its value to the value you computed for the right side of this
assignment statement. For example, consider the third assignment statement in the following:
2
x1 = 23
y = x1 + 2
y = y * 5
The variable on the left side (y) has already been declared in the previous statement, so it will already
e in the Dictionary. Thus, you will find it in the Dictionary, and simply change the value stored
with it to 125 (the value of the right side).
– If you don’t find the variable in the Dictionary, then this assignment statement is this variable’s
declaration. You must add the new variable (as a variable record) to the Dictionary along with the
value you computed for it on the right side of the assignment statement. For example, consider the
third assignment statement in the following:
x2 = 23
y2 = x2 + 2
z = y2 * 5
The variable on the left side (z) has not yet been declared, so this assignment statement is its
declaration. You will not find it in the Dictionary, so you will have to insert it along with its value
given by the right side (125).
• If a variable on the right side is not in the Dictionary, then it has not been declared before being used, so
you should print an e
or message, abandon this assignment statement, and go on to the next assignment
statement.
When you have executed all the assignment statements in a Karon program, you should print out all the variable
names and their values.
Hash Table:
You must create a Dictionary class that is implemented as a hash table that uses separate chaining to resolve
collisions. The dictionary (an a
ay of Nodes — as described in the pre-recorded videos) should have size N =
79 (which is a prime number). You should use the polynomial hash code for the variable name keys (and use
Horner’s method to compute the polynomial hash code efficiently). You should use the small prime constant
a = 23 for computing the polynomial hash code. Furthermore, for each step of Horner’s method, compute the
value modulo the table size N.
Dictionary Operations:
You must implement the following methods in your Dictionary implementation (hash table):
• A constructor, which creates a new, empty Dictionary (for this hash table implementation, the empty
Dictionary should have size 79).
• search(String variableName), which returns the variable record containing the variable’s name and its
associated value, or null if the variable is not in the Dictionary.
• insert(String variableName, int variableValue), which inserts the given variable and its associated
value into the Dictionary.
• updateValue(String variableName, int newValue), which attempts to find the variable in the Dictionary
and change its value to the given new value. This method should return true if it succeeds in finding the
variable and changing its value, and false if it fails.
• printVariables(), which simply goes through the Dictionary and prints out the variables stored in it.
Each variable should be printed on a separate line containing the variable name followed by its value.
In this hash table implementation, it should simply do a scan through the table, and for each a
ay entry
that is not an empty list, it should print out all the variables and their associated values that are stored
in the linked list.
You may, of course, create other helper methods as needed.
3
The Input:
The input file will contain multiple Karon programs.
The first line of the input file will contain the number of Karon programs contained in the file.
Each Karon program will contain a number of assignment statements, one assignment statement per line.
(There may also be blank lines anywhere in a Karon program; simply ignore them.) You may assume that the
integer constants, variable names, operator and equals sign within an assignment statement are separated from
each other by at least one blank. (There may be multiple blanks between them.)
The end of a Karon program will be indicated by a line containing a ‘Q’ (and no other letters, numbers,
operators, or equals signs). Notice that the ‘Q’ is uppercase, which differentiates it from a Karon variable, which
contains only lowercase letters or numbers.
We will provide a larger input file, called “A3bigData.txt”, a few days before the due date. Your program
must run on that input file. In the meantime, you can use the smaller input file “A3smallData.txt” to get you
code working. Write your own test files, too! (You can find both of these files in the “Assignments” section of
the course web site.)
Your program should prompt the user for the file to use as input — don’t hard-code file names! The markers
should be able to use whatever file they want as input.
The Output:
The output should begin with an appropriate opening message.
Then, for each Karon program, the output should contain an appropriate heading (number the programs),
followed by any e
or messages generated by variables being used before they were declared, followed by a
print-out of the final values of the variables after the program has been executed.
Finally, the output should end with an appropriate closing message.
For example, the output might look like the following:
COMP 2140 Assignment 4: Executing Karon Programs
Karon Program 0
----------------
E
or messages:
Final values of the variables:
temp = 43
answer = 166
Karon Program 1
----------------
E
or messages:
E
or in statement x = t1 * 13: t1 was used before being declared.
Final values of the