Description

Data Structures
• 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.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.

Figure 1: A directed weighted graph.
Question 1 (20 points)

Starting from G, trace the operations of the Dijkstra’s weighted shortest path algorithm on the graph given in Figure 1.
Question 2 (15 points)

Starting from G, trace the operations of the Prim’s minimum spanning tree algorithm on the graph given in Figure 1.
Question 3 (15 points)

Trace the operations of Kruskal’s minimum spanning tree algorithm on the graph given in Figure 1.
Question 4 (15 points)

Starting from S, trace the operations of breadth-first traversal on the graph given in Figure 2.

Figure 2: A directed weighted graph.
Question 5 (20 points)

Given Figure 2 and starting from S,
a) Trace the operations of depth-first traversal.
b) Give the post-order numbers for all the nodes.
c) Give the pre-order numbers for all the nodes.
d) List the tree arcs, cross arcs, forward arcs, and backward arcs.
Question 6 (15 points)

Find a topological ordering of the graph given in Figure 3.

Figure 3: An example DAG.