** 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.

** 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**