A4Q1 Sample Test Posted

[cs240]

Hi all,

I posted a sample input and output file for you to test your hash table.
You can download the files from the assignment page of the course website.

Please note the following before submitting your code:
1. You have included a makefile (the file name should be in all lower
case letters) in your submission.
2. Your program checks for invalid commands and issues error messages if
the commands start with letters other than c,s,i,d or q.
3. All error messages should be printed to stderr instand of stdout.

Vivian
CS240 Tutor

[Chris Jones]

How does 11 get inserted in T[0][2]?

11 mod 2 is 1.
So it should be inserted in the first available slot in T[>=1] and
since there is only T[1]...

[Chris Jones]

Sorry it would be T[0][1], but that doesn't make a logical difference.

Also inserting zero into the Hash Table is allowed?
It was very confusing as 0 stores an empty or deleted element.

[cs240]

You can use the values of f, d, e to figure out whether 0 indicates a key
or an non-filled cell.

Vivian

Post by Chris Jones
Sorry it would be T[0][1], but that doesn't make a logical difference.
Also inserting zero into the Hash Table is allowed?
It was very confusing as 0 stores an empty or deleted element.

[Chris Jones]

Yes, I understand that one, but I don't get how 11 goes to T[0]

[Alan Tang]

Post by Chris Jones
Yes, I understand that one, but I don't get how 11 goes to T[0]

The hash table uses chaining with linear probing.
T[1] is full at that point, so we go to the next slot, T[0] and find
that it has a non-filled cell, so we insert it there.

[Chris Jones]

To Alan: Aren't we using open addressing not chaining?

To Vivian:

Linear Probing has a h(k,i) = h(k) + i mod M correct? Where h(k) = k
mod M.

so first try is h(11,0) = 11 mod 2 + 0 mod M = 1 + 0 = 1, but t[1] is
full
so second try is h(11,1) = 11 mod 2 + 1 Mod 2 = 1 + 1 = 2, but t[2]
does not exist

is the actual h(k,i) supposed to be [h(k) + i] mod M then?

[cs240]

We are using open addressing, linear probing in particular, and chaining
at the same time. So if you find T[i] is full, you go to the next slot in
the table, T[i+1], T[i+2], etc.

You should realize that you made a mistake when you get a hash value of
M, which should be impossbile because we don't have a slot with index M.
And yes, you misunderstood the formula:

H(k, i) = (h(k) + i) mod M != k mod M + i mod M

Notice the above formula will always generate a number between 0 and
M-1, which means that you will always find a slot in the table provided
that the table is not completely full. So the second try would be:

H(11, 1) = (1 + 1) mod 2 = 0.

Vivian
CS240 Tutor

Post by Chris Jones
To Alan: Aren't we using open addressing not chaining?
Linear Probing has a h(k,i) = h(k) + i mod M correct? Where h(k) = k
mod M.
so first try is h(11,0) = 11 mod 2 + 0 mod M = 1 + 0 = 1, but t[1] is
full
so second try is h(11,1) = 11 mod 2 + 1 Mod 2 = 1 + 1 = 2, but t[2]
does not exist
is the actual h(k,i) supposed to be [h(k) + i] mod M then?

[cs240]

That's the first non-filled cell you can find.

Vivian

Post by Chris Jones
Yes, I understand that one, but I don't get how 11 goes to T[0]

[Yiyao LIU]

Post by cs240
Hi all,
I posted a sample input and output file for you to test your hash table.
You can download the files from the assignment page of the course website.
1. You have included a makefile (the file name should be in all lower
case letters) in your submission.
2. Your program checks for invalid commands and issues error messages if
the commands start with letters other than c,s,i,d or q.
3. All error messages should be printed to stderr instand of stdout.
Vivian
CS240 Tutor

Hi,

I wanna ask how strict the "check for invalid commands" requirement
is.
Like,
will there be strange input like :
i x
(instead of i + int)
or the only invalid input we need to consider is sth like:
r
e
o
(single char which is not 'c' 'i' 'd' or 'q' )


Thank you.

LIU Yiyao

[cs240]

You can safely assume that if a command is in a valid format if it starts
with one of c,i,d,s or q. For example, there won't be anything like "c 12"
or "d i".

Vivian
CS240 Tutor

Post by Yiyao LIU

Post by cs240
Hi all,
I posted a sample input and output file for you to test your hash table.
You can download the files from the assignment page of the course website.
1. You have included a makefile (the file name should be in all lower
case letters) in your submission.
2. Your program checks for invalid commands and issues error messages if
the commands start with letters other than c,s,i,d or q.
3. All error messages should be printed to stderr instand of stdout.
Vivian
CS240 Tutor

Hi,
I wanna ask how strict the "check for invalid commands" requirement
is.
Like,
i x
(instead of i + int)
r
e
o
(single char which is not 'c' 'i' 'd' or 'q' )
Thank you.
LIU Yiyao

[Su Zhang]

Post by cs240
2. Your program checks for invalid commands and issues error messages if
the commands start with letters other than c,s,i,d or q. 3. All error
messages should be printed to stderr instand of stdout.

Are the contents of the error messages irrelevant?

[cs240]

No, it doesn't matter as long as you output some error message to stderr
and your program does not crash beacuse of invalid commands.

Vivian
CS240 Tutor

Post by Su Zhang

Post by cs240
2. Your program checks for invalid commands and issues error messages if
the commands start with letters other than c,s,i,d or q. 3. All error
messages should be printed to stderr instand of stdout.

Are the contents of the error messages irrelevant?