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

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

Homework 1

Details

  • Implement an efficient algorithm to generate all permutations of the elements of an array. You may use one of the algorithms from the textbook or find another algorithm elsewhere (if so, say where you got the ideas/algorithm from). (Future note: change to MUST use one from the book) However, you may not use any code from any source. An important skill to develop is implementing an abstract algorithm in an actual programming language.
  • Your program should be written in Java. Name your class CombinatoricsUtilities. 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
  • 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 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.)