Review Test Submission: Examination Opportunity 3
Course COS 212 S1 2021
Test Examination Opportunity 3
Attempt Score 30.01388 out of 50 points
Instructions
Results Submitted Answers, Correct Answers,
Displayed Feedback
Question 1
0 out of 2 points
When chaining is used in a hash table, linked lists store multiple keys for each hash
code. One disadvantage of chaining is that retrieval performance decreases when linked
list length increases. Suggest a simple way in which this performance decrease could be
reduced.
Selected By using Coalesced Hashing, which is a combination of Chaining and
Answer: Probing. The linked list function can still be implemented, when there is a
collision, use any type of probing to find new address for the value in the
hash table, store the index of the new position next to the position where
the collision occured, so that the value in the hash table is linked to the
value it had a collision with. They are able to reference each other like in a
linked list, without the heavy memory and performance decrease.
Correct
Answer: Once a linked list length, or average linked list length, increases beyond a
certain threshold (1 mark), increase table size and rehash (1 mark).
Response How will improve performance with only chaining
Feedback:
Question 2
0 out of 4 points
,Consider the adaptive Huffman tree in Figure 2 shown below:
Assume the following symbols are all encoded and transmitted using the adaptive
Huffman tree in Figure 2, modifying it as necessary,
in the given order:
x, b, b, e, x
Answer the following, assuming that the symbols in the table below are not
transmitted (i.e. do not modify the tree further):
What is the code word for
[a]
the symbol b?
What is the code word for the symbol x? [b]
What is the code word for the symbol e? [c]
Specified Answer 0111
for: a
Specified Answer 010
for: b
Specified Answer 01100
for: c 1
Correct Answers for: a
Evaluation Method Correct Answer Case Sensitivity
Exact Match 101
Correct Answers for: b
Evaluation Method Correct Answer Case Sensitivity
Exact Match 00
Correct Answers for: c
Evaluation Method Correct Answer Case Sensitivity
Exact Match 10001
Question 3
5 out of 5 points
Assume that the following list of words must be hashed from top to bottom with
Cichelli’s algorithm:
Saturnus
Sun
Mars
Moon
Venus
Uranus
Perform Cichelli’s algorithm with max = 3 on the list of words in the given order (the
list has already been sorted according to the
frequencies), and fill in the hash values for the words, and g-values for the characters
in the tables below:
Word Hash
, Value
Saturnus [a]
Sun [b]
Mars [c]
Moon [d]
Venus [e]
Uranus [f]
Charact g-
er value
S [h]
N [i]
M [j]
V [k]
U [l]
Specified Answer
for: a 2
Specified Answer
for: b 4
Specified Answer
for: c 5
Specified Answer
for: d 0
Specified Answer
for: e 1
Specified Answer
for: f 3
Specified Answer
for: h 0
Specified Answer
for: i 1
Specified Answer
for: j 1
Specified Answer
for: k 2
Specified Answer
for: l 3
Correct Answers for: a
Evaluation Method Correct Answer Case Sensitivity
Course COS 212 S1 2021
Test Examination Opportunity 3
Attempt Score 30.01388 out of 50 points
Instructions
Results Submitted Answers, Correct Answers,
Displayed Feedback
Question 1
0 out of 2 points
When chaining is used in a hash table, linked lists store multiple keys for each hash
code. One disadvantage of chaining is that retrieval performance decreases when linked
list length increases. Suggest a simple way in which this performance decrease could be
reduced.
Selected By using Coalesced Hashing, which is a combination of Chaining and
Answer: Probing. The linked list function can still be implemented, when there is a
collision, use any type of probing to find new address for the value in the
hash table, store the index of the new position next to the position where
the collision occured, so that the value in the hash table is linked to the
value it had a collision with. They are able to reference each other like in a
linked list, without the heavy memory and performance decrease.
Correct
Answer: Once a linked list length, or average linked list length, increases beyond a
certain threshold (1 mark), increase table size and rehash (1 mark).
Response How will improve performance with only chaining
Feedback:
Question 2
0 out of 4 points
,Consider the adaptive Huffman tree in Figure 2 shown below:
Assume the following symbols are all encoded and transmitted using the adaptive
Huffman tree in Figure 2, modifying it as necessary,
in the given order:
x, b, b, e, x
Answer the following, assuming that the symbols in the table below are not
transmitted (i.e. do not modify the tree further):
What is the code word for
[a]
the symbol b?
What is the code word for the symbol x? [b]
What is the code word for the symbol e? [c]
Specified Answer 0111
for: a
Specified Answer 010
for: b
Specified Answer 01100
for: c 1
Correct Answers for: a
Evaluation Method Correct Answer Case Sensitivity
Exact Match 101
Correct Answers for: b
Evaluation Method Correct Answer Case Sensitivity
Exact Match 00
Correct Answers for: c
Evaluation Method Correct Answer Case Sensitivity
Exact Match 10001
Question 3
5 out of 5 points
Assume that the following list of words must be hashed from top to bottom with
Cichelli’s algorithm:
Saturnus
Sun
Mars
Moon
Venus
Uranus
Perform Cichelli’s algorithm with max = 3 on the list of words in the given order (the
list has already been sorted according to the
frequencies), and fill in the hash values for the words, and g-values for the characters
in the tables below:
Word Hash
, Value
Saturnus [a]
Sun [b]
Mars [c]
Moon [d]
Venus [e]
Uranus [f]
Charact g-
er value
S [h]
N [i]
M [j]
V [k]
U [l]
Specified Answer
for: a 2
Specified Answer
for: b 4
Specified Answer
for: c 5
Specified Answer
for: d 0
Specified Answer
for: e 1
Specified Answer
for: f 3
Specified Answer
for: h 0
Specified Answer
for: i 1
Specified Answer
for: j 1
Specified Answer
for: k 2
Specified Answer
for: l 3
Correct Answers for: a
Evaluation Method Correct Answer Case Sensitivity
