CSCI 385 Spring 2019
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

Homework 2

Details

Implement the most efficient algorithm you can for each of the following problems.

  1. Use Algoraph to implement an algorithm called ShortestPathLengths that returns an array that gives the length of the shortest path from the first vertex (vertex 0) to all of the other vertices in an unweighted graph. By array I really mean a string with numbers separated by spaces since getResult returns a String.
    You can use any resources you want to find the best algorithm to use, but you must write your own code. (Hint: we discussed one or more potential algorithms in CSCI 255, and you can subclass an algorithm in Algoraph to implement yours. This one should be really easy!)
    Upload and test your algorithms in Algoraph. You can use any graphs to test this algorithm and you should test it on enough graphs to be pretty certain your algorithm is correct.
  2. Use Algoraph to implement an algorithm called ContainsTriangle that returns true if an algorithm has a cycle of length 3 and false otherwise.
    Upload and test your algorithms in Algoraph. Test it on enough graphs to be pretty certain your algorithm is correct.

For both problems, there are test programs on the AlgorithmTests page.

Hand in your Java file using Webhandin 385-HW2, making sure your Java class names are as specified. Also submit a PDF which describes each algorithm and gives a complete complexity analysis of them.