• 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 HAND– WRITTEN 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.
• Late submissions will be penalized 10% of the full grade per late day (or portion of a late day). Submissions that are late BY MORE THAN ONE DAY will not get any credits.
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
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.