Q1
I was wondering for question 1, do we assume the graph has undirected or
directed edges?
A1
In the 1st question, you have to figure out yourself
what graph you can use to represent correctly information given
to you. So, it is up to your decision whether you will be using
a directed or undirected graph in Q1.
Q2
Is the 1st question from the assignment really easy,
or may be I'm missing something?
A2
Yes, this is a rather easy question. You just have to add a few lines
to one of the algorithms considered in class. However, you have to
provide also a detailed complexity analysis of the resulting algorithm.
I would say that all questions in this assignment are not difficult.
Q3
In question 2 you ask us to find a DP algorithm that needs to
find the "number of shortest path", by definition shortest would mean
that there is only one path that is the best (or shortest) so if you ask
us to find the number of shortest that would translate as that we are
required to find one path that is the shortest and all others that are
equal to it. Is that correct?
It just does not make sense to me to have many shortest paths. Let me
know if I am on the right track.
A3
If you study carefully the graph provided for Q1 in the assignment,
then you can notice easily that there are several shortests paths
between the vertices S and F. For example, S-A-C-D-F has the total
weight 6 and is the shortest path between S and F, but there are
other shortests paths as well: S-A-C-E-F, S-B-C-D-F, S-C-E-F, and so on.
All of them have the same total weight 6. In Q2, you are asked
to find the number of shortest paths between any two nodes V and W
in a directed graph, where weights can be positive or negative.
For the example above, the answer for vertices S and F would be
6 since there are 6 distinct shortests paths from S to F:
3 shortest paths from S to C times 2 shortest paths from C to F.
Q4
How can we reduce this problem to one of the problems solved in class?
A4
Yes, in Q3 of the assignment, you have
to describe clearly which graph you use and why it is convenient.
Q5
For assignment 3 question 2, do you want us to describe the steps of
developing the algorithm that will solve this problem like we did in the
previous assignment?
A5
Yes, please follow the outline from the 2nd assignment.
Also, I mentioned all the steps in class, when I explained
the methodology of designing DP algorithms.
Q6
I am just wondering for part 2 which asks us to count the number of shortest
paths. Are we only considering shortest paths with minimal edges, or just
simply all shortest paths with minimal cost?
A6
We are looking for shortests paths in terms of minimal
total cost. Develop an a DP algorithm that will count the number
of all such shortest paths.
Q7
For question 2 we are writing an algorithm for the length of a shortest path
of a directed graph. Part 5 of the questions asks us to trace our algorithm
using the graph from part 1. This graph however is undirected. Should we be
assuming the direction of all edges is just towards F (and away from S)?
A7
Yes, assume that all adges are going in the direction away from S and
towards F.
Q8
A8
Q9
A9
Q10
A10
Q11
A11
Q12
A12
Q13
A13
Q14
A14
Q15
A15
Q16
A16
Q24
A24
Q25
A25
CPS616