Assignment 12 - COP 3530, Fall 2006

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

Remember:

• Have your name, UF ID, and discussion session number as comments at the top of your code.
• ONLY SOFT copy is REQUIRED.
• Put each question in a separate file. One file one question ONLY.
• Jar all the files directly WITHOUT the dataStructures folder.
• Make sure to write a main method for every coding problem at the end of your code.
• Put the complexity analysis and other non-coding parts of THIS question in comments at the beginning of your code.
• For pen-paper questions, we only accept the following format file: Plain TEXT and PDF. Plain TEXT format is preferred. Also put each pen-paper question in separated files. Name it as Qx.txt, where x is the sequence number of this question. For example, if Question 1 is a pen-paper question, put your solution to the file "Q1.txt"
• Misspellings and wrong capitalization of class and method names (Java is case sensitive), incorrect method signatures, and improper jarring of files will be penalized heavily.

Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial, if you have trouble with the classpath settings you could try reading this tutorial.

For any coding question below, even though you may not use any of the methods of the class you are extending, you MAY use the constructor of the class to be extended when you create the constructor of your new class. For example, you may do something like this:

public ALLExtended (){
 super();
}
 
public ALLExtended( int n ){
 super(n);
}

You may NOT use any built-in array functions in the java API.

---

1.

1.1 Dijkstra's algorithm

Consider the directed graph G in figure 1.

Use Dijkstra's single-source shortest path algorithm (page 721-726) to calculate the shortest path from vertex 1 to each vertex of the graph shown below. The number along each edge between two vertices is the weight of the edge. Show the predecessor and distance arrays following each step of Dijkstra's algorithm. Refer to Figure 18.9 on page 722.

1.2 Minimum-cost spanning tree

Consider the undirected graph G in Figure 2,

(a) Using Kruskal's method to construct a minimum-cost spanning tree. Draw the spanning tree that is constructed and also give the steps (draw figures and state the decision made at each step) used to arrive at this tree.

(b) Do part (a) using Prim's method instead of Kruskal's method. Choose vertex 1 as your starting vertex.

---

2.

Create a new class MyLinkedDigraph that extends class LinkedDigraph. Implement two methods IsConnected() and HasCircle(). IsConnected() returns whether the directed digraph is strongly connected. Strongly connected directed graph is a graph where all nodes in the graph are reachable by all other nodes in the graph. HasCircle() returns whether the digraph has circles. You must use non-recursive DFS to implement IsConnected() and BFS to implement HasCircle().

package dataStructures;

import java.util.*;

public class MyLinkedDigraph extends LinkedDigraph {

// member variables go here

// constructors go here

// Performs a non-recursive depth-first search

public boolean IsConnected() {

// your code goes here

}

public Boolean HasCircle() {

// your code goes here

}

// helper methods(if necessary) go here

/** test program */

public static void main(String[] args) {

MyLinkedDigraph g = new MyLinkedDigraph(5);

g.putEdge(new Edge(1, 2));

g.putEdge(new Edge(3, 4));

g.putEdge(new Edge(4, 5));

g.putEdge(new Edge(5, 3));

if (g.IsConnected())

System.out.println("The graph is connected");

if (g.HasCircle())

System.out.println("The graph has circles");

}

}

a) Write the Java code for the methods IsConnected() and HasCircle().

b) Determine and justify your time and space complexity of both methods.

---