some questions

[Tahmoures Zadeh Tina]

Graph:
-is Path defined to be a sequence of *distinct* vertices each adj to the
next, or just a sequence of vertices each adj to the next?

hashtables:
- for inserting( either in chain or open addressing ) do we assume that
there is no similar key in the table? or do we have to first search to see
if that key already exists or not, if yes then insert if not then donot
insert. In case we have to search eachtime before insert then specially
for chaining the complexity of insert wouldnot be o(1) anymore, would it?

-in the linear probing example in the slides, pg 14,I donot understand
why the last two probes are 4 and 3? could you plz explain them clearly.
Also, by loading do u mean search?

-for the complexities given in pg20 of the hashing slides, could you give
some
explanation?

Regards
Tina

[Jim Clarke]

Tahmoures Zadeh Tina <***@ecf.utoronto.ca> writes:

I'll give unhelpful general answers here. For more specific
help, come to my office hours, announced on the course web
site.

Post by Tahmoures Zadeh Tina
-is Path defined to be a sequence of *distinct* vertices each adj to the
next, or just a sequence of vertices each adj to the next?

That depends on the application, but if you don't want them
to be distinct, won't you wind up with infinitely-long
paths that stay at the same vertex? Might there be a use for
this definition?

Post by Tahmoures Zadeh Tina
- for inserting( either in chain or open addressing ) do we assume that
there is no similar key in the table? or do we have to first search to see
if that key already exists or not, if yes then insert if not then donot
insert. In case we have to search eachtime before insert then specially
for chaining the complexity of insert wouldnot be o(1) anymore, would it?

You certainly have to make sure the key isn't already stored
before inserting it. Otherwise you couldn't figure out where
to put it.

The complexity depends on what you do as the load factor
increases.

Post by Tahmoures Zadeh Tina
-in the linear probing example in the slides, pg 14,I donot understand
why the last two probes are 4 and 3? could you plz explain them clearly.
Also, by loading do u mean search?

"Load" means "retrieve". The last two lines appear to be in
error.

Post by Tahmoures Zadeh Tina
-for the complexities given in pg20 of the hashing slides, could you give
some
explanation?

No. That's an "it can be shown" slide.
--
Jim Clarke -- Dept. of Computer Science, University of Toronto
http://www.cs.utoronto.ca/~clarke