## Question

For each of these tasks, you have been given a set of ten numbers. Your goal is in general to figure out how long (in computations or comparisons) it would take to reach each element of the search list. For the purposes of this, each time you compute something, make a comparison, or traverse an edge, you are executing an important function.

Part 1 (the easiest): Sequential Search

Recall that in a sequential search, the items have an order that they can be directly sorted into. For the list given, find the number of calculations it would take to get each specific value. Excel gives you an easy way to do this (the RANK function)

For Part 1, you should submit the following:

The RANK of each object (which is essentially synonymous with the length of calculations it will take to find it)

Part 2: 2-3 Balanced Search Tree

In this part, you will need to take the objects in the order they are presented and construct the 2-3 BST for them. Then use that structure to determine the number of calculations. Remember: if you have a multi-node, we will consider it to be left leaning. This means that if you need to access the smaller of a doubled-up node, then you need to add one step.

Let me recommend this strategy:

If you have post-it notes or index cards, put each item on a separate one. Then use that to dynamically reorganize them after each new item is added to the list. You may even use yarn or something like that to physically show the connection. Once you are finished, then make a PPT slide or otherwise that encodes your picture.

For Part 2, you should submit the following:

• Your completed 2-3 BST for the list

• The number of steps to get to each element of the list

• For each individual element, is it faster to use the 2-3 BST or the RANK?

• For each individual element, is it faster to use the 2-3 BST or the RANK? Part 3: Modular Hashing

In this part, you are going to take the same list and explore a few prime numbers as to which ones will produce the best hash. Remember that the goals are uniform distribution and smaller list sizes (it is a balancing act).

For Part 3, you should submit the following:

• Graphs that profile the distribution of the hash values for the first 5 prime numbers (2, 3, 5, 7, and 11)

All of this (with the exception of the BST) can be done right in Excel. You will want to know these three functions:

• RANK – computes the rank (ascending or descending) of an object within its list when sorted

• MOD – computes the remainder after dividing by a number

• COUNTIF – determines the number of times a condition is found within a list

The easiest thing will be to submit this assignment as a Powerpoint file. You can copy your tables out of Excel and make them a table in PPT. Similarly, you can do the same thing with the charts that you make.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

1. Part 1 (the easiest): Sequential SearchRecall that in a sequential search, the items have an order that they can be directly sorted into. For the list given, find the number of calculations it would take to get each specific value. Excel gives you an easy way to do this (the RANK function)

For Part 1, you should submit the following:

• The RANK of each object (which is essentially synonymous with the length of calculations it will take to find it)

Number and Calculation s

88 1

99 2

306 3

458 4

155 5

427 6

81 7

316 8

456 9

258 10

249 11

307 12

89 13

110 14

419 15

6 16

234 17

254 18

194 19

302 20

406 21

523 22...

By purchasing this solution you'll be able to access the following files:

Solution.zip.