Week 10 has a lab, but not an assignment. The only thing left is to make sure you understand the concepts for the exam.

Goals for this lab section

• Practice hash tables
• Practice algorithmic complexity calculations

Prelab:

1. Hash Function

Write a hash function as your prelab.

int hash ( char *string );

Follow this recipe for computing an unsigned long int key for a string:

1. 1. Initialize an unsigned long int result to 17 (unsigned long res = 17;).
2. 2. Loop over the characters in the string. For every character, set the result to be 37 times itself plus the ASCII numeric value of the character.

(This hashing algorithm recipe is from Effective Java by Joshua Bloch.)

For example, the hash code for the word FORK, given that the ASCII values of the characters in FORK are 70, 79, 82 and 75, is as follows:

res = 17
res = 37*17+70     = 699
res = 37*699+79    = 25942
res = 37*25942+82  = 959936
res = 37*959936+75 = 35517707
(As you can see, the numbers get big.)

2. Complexity Analysis

for(i=0;i<n;i*=2)
   for(j=0;j<m;j++)
	do something;

for(i=0;i<n;i++)
   for(j=0;j<i;j++)
	do something;

int recursiveFun1(int n)
{
	if (n <= 0)
		return 1;
	else
		return 1 + recursiveFun1(n/5);
}

Lab

During lab today, you are going to complete the final exam from spring 2018. Your exam will likely be similar to this exam, either because it draws from slightly different concepts or from similar concepts with the problems changed enough so you can't copy the answers from this exam.

You may complete these alone or with a partner, you can ask your TA for help. The goal is understanding the material. To get attendance credit, you may not leave until the TA has verified that you have completed the exam and done well on it. Otherwise, you need to ask questions about problems you don't understand.

Sample Exam