Description

Data Structures
Homework 4
• NO SUBMISSIONS OUTSIDE SUCOURSE WILL BE ACCEPTED.
• SOLUTIONS HAVE TO BE YOUR OWN. NO COLLABORATION OR COOPERATION AMONG STUDENTS IS PERMITTED.
• Please provide only the requested information and nothing more. The solution papers should be typeset using Word, ScientificWorkplace, LATEX, etc., and any figures should be drawn using some kind of a drawing tool such as PowerPoint, Visio, etc. HOWEVER YOUR SOLUTIONS SHOULD BE SUBMITTED IN ONLY .pdf FORMAT. NO HANDWRITTEN SOLUTIONS WILL BE ACCEPTED. Make sure what is submitted can be properly printed, otherwise they will not be considered.
• You should name your homework as XXXXX-NameLastname-hw4.pdf where XXXXX is your student number (possibly with a leading 0). Make sure you do NOT use any Turkish characters in the file/folder name.
Question 1 (20 points)
Trace the Dijkstra’s weighted shortest path algorithm on the graph given in Figure 1. Use vertex E as your start vertex.
Question 2 (20 points)
Trace the Prim’s minimum spanning tree algorithm on the graph in Figure 1. Use vertex E as your start vertex.
1

Figure 1: An undirected weighted graph. Figure 2: A directed acyclic graph.
Question 3 (20 points)
Trace the Kruskal’s minimum spanning tree algorithm on the graph in Figure 1.
Question 4 (20 points)
Trace the breadth-first search traversal algorithm on the graph in Figure 1 starting from vertex E.
Question 5 (20 points)
Find a topological ordering of the graph in Figure 2.
2