When you say that as a human when Sirius can go diagonally, do you mean
going from (x,y) to (x+1,y+1) directly or first going to (x+1,y) and
then going to (x+1,y+1)?

Thank you
Kelum

It means going directly from (x,y) to (x+1,y+1), or generally, walking
along the direct line between any two points (as long as he has water).

Mina

On Thu, 13 Mar 2008, Kelum Peiris wrote:

For part a), the question is asking us to describe how we are going to
build the graph and label is with time costs. So by time costs does it
mean labelling the edges between each vertex with the minimum amount
of time required to get from one end to the other? And the hint says
we should use a data representation that has a space requirement of
BigTheta m. But we will have a total of m-1 edges (since there are m+2
vertices in total). So shouldn't the data representation take up
BigTheta m-1 instead?..Or am I missing something here??

thanks,
-Akshay

Yes.

This is not true.

Theta(m-1) is equal to Theta(m), additive constants do not matter.

Mina

Hello,

Can Sirius move backwards, lets say from (14,7) to (12,4) in the grid
(in my test input Azkaban is at (0,21) and Quidditch is at (21,0)). I
was thinking that if he can go backward then there might be a solution
in my test input. But, if he can only go forward, then there is no solution.

Thank you.

Kelum

Yes, Sirius can move backwards and he needs to do that in some maps to
make the trip.

Mina

On Fri, 14 Mar 2008, Kelum Peiris wrote:

Also to clarify, is going from (x,y) to (x+1,y+1) considered one unit?

On Thu, 13 Mar 2008 21:22:18 -0400, Mina Razaghpour wrote:

No, this is sqrt(2) units (euclidean distance between the 2 points).

On Mon, 17 Mar 2008, Scott Rycroft wrote:

When the assignment says "should not take more time than running
Dijkstra’s algorithm", what version of Dijkstra's should we be comparing
to? The one we will be using or some other (possibly better or worse)
version?

On Mon, 17 Mar 2008 00:30:58 +0000, Scott Rycroft wrote: