Data Structure And Algorithms- Tasks To Be Completed

SIT221 Data Structures and Algorithms     Trimester 2, 2019 

1   

Practical Task 9.1   (Pass Task) 

Submission deadline: 10:00am Monday, September 23  Discussion deadline: 10:00am Saturday, September 28 

General Instructions 

In this task, answer all the following questions and complement each answer with a detailed explanation. 

1. Consider the directed graph  ⟨ , ⟩ represented by the following cost adjacency matrix:  

. 3 . . . 10 . . . .

. . . 5 11 . 7 1 . .

. . . . 2 . . . . . 6 . . . . 1 . . . . . . . . 0 . . 0 . 3 . . . 3 . . . . . . . . . . . 2 . . . . . . 10 . . . . . . . . . . . . . . 5 . . . . . 5 . . . . . .

 

Assume that element   positioned in row   and column   in matrix A stores the distance between node 

 and node   in graph  . Draw the graph and solve the single‐source‐shortest path problem by running  Dijkstra’s algorithm on  , starting at node 1. What is the order in which nodes get removed from the  associated priority queue? What is the resulting shortest‐path tree? 

2. Let   be a shortest path from some vertex   to some other vertex   in a graph. If the weight of each edge  in the graph is increased by one, then will   be still a shortest path from   to  ? Explain your answer. 

3. Consider the directed graph  ⟨ , ⟩ represented by the following cost adjacency matrix:  

. 3 . . . . . . .

. . 4 . 4 . . . . 2 . . 5 . . . . 7 . 10 . . 6 . . 1 1 . . . . . . 7 8 . . . . . 5 . . 6 . . . . . . 4 . . . . . . . . . 2 . . 0 . . . . . . . .

 

Assume that element   positioned in row   and column   in matrix A stores the distance between node 

 and node   in graph  . Draw the graph and solve the single‐source‐shortest path problem by running  Bellman‐Ford’s algorithm on  , starting at vertex 1. What is the resulting shortest‐path tree? Which nodes  are get ‘infected’?  

Further Notes 

 The  lecture  notes  of  week  9  should  be  a  good  starting  point  outlining  the  required  shortest  path  algorithms. 

 Reading chapter 14.6 of the course book “Data Structures and Algorithms in Java” by Michael T. Goodrich,  Irvine Roberto Tamassia, and Michael H. Goldwasser (2014) will help you with completion of this task. You  may  access  the  book  on‐line  for  free  from  the  reading  list  application  in  CloudDeakin  available  in 

SIT221 Data Structures and Algorithms     Trimester 2, 2019 

2   

Resources  Additional Course Resources  Resources on Algorithms and Data Structures   Course  Book: Data structures and algorithms in Java. 

Marking Process and Discussion 

To get this task completed, you must finish the following steps strictly on time: 

 Submit your answers to the task via OnTrack submission system. You may submit a hand‐written and then  scanned  document,  but  ensure  that  the  text  and  figures  are  very  clear  to  read.  Note  that  this  is  a  theoretical task, thus we do not expect you to write any program code. 

 Meet with your marking tutor to explain your solutions. When the solutions are hand‐written, do not  forget to bring them with you. Cloud students must record a short video explaining their work and use a  sort of white‐board, e.g. a graphical editor, or a scanned document with the answers. 

 Answer all additional (theoretical) questions that your tutor may ask you. Questions are likely to cover  lecture notes, so attending (or watching) lectures should help you with this compulsory interview part.  Please, come prepared so that the class time is used efficiently and fairly for all the students in it. You  should start your interview as soon as possible as if your answers are wrong, you may have to pass another  interview, still before the deadline. Use available attempts properly.   

Note that we will not check your solution after the submission deadline and will not discuss it after the  discussion deadline. If you fail one of the deadlines, you fail the task and this reduces the chance to pass the  unit.  Unless  extended  for  all  students,  the  deadlines  are  strict  to  guarantee  smooth  and  on‐time  work  through the unit. 

Remember that this is your responsibility to keep track of your progress in the unit that includes checking  which tasks have been marked as completed in the OnTrack system by your marking tutor, and which are still  to be finalised. When marking you at the end of the unit, we will solely rely on the records of the OnTrack  system and feedback provided by your tutor about your overall progress and quality of your solutions.