Homework 1

Details

• An important skill to develop is implementing an abstract algorithm in an actual programming language. Thus, for this assignment you must implement one of the algorithms from the textbook to generate all permutations of the elements of an array.
• Your program should be written in Java. Name your class CombinatoricsUtilities_Smith, where you should replace Smith with your last name. It should have a method

  public static ArrayList⟨String[]⟩ generatePermutations(String[] input)

  that returns an ArrayList of all permutations of the original array.
• To help you debug your code, include a method public static void printList(ArrayList⟨String[]⟩) that prints each array in the ArrayList, one per line. Each array should be printed by printing each element with commas in between. E.g. For array ["blah","foo","bar"], the output should be

  blah,foo,bar

• Implement a main method public static void main(String []args) that runs your algorithm on several lists, starting with lists of 3 elements, and including lists with 4, 5, and 8 elements.
• Note: The easiest mistake to make with this algorithm is to not copy an array when you need to.
• Submit your Java file(s) (NOT your .class files) using Webhandin 385-HW1.
• Submit a brief write-up (Printed out) that includes a description of your algorithm and gives the computational complexity of it, with justification. (Convince me that you fully understand how the algorithm works and that you understand the analysis of it.)