Homework 7

A: You can often use a stack or queue to avoid recursion. Implement this algorithm for computing all permutations of a string str without recursion.

1. Add "|" + str to the queue.
2. While the queue is not empty,
   • Remove the element at the front. It has the form s | t. (That is, s is the substring before the | and t is the substring after the |.)
   • For each letter c in t, add s + c + "|" + (t with c removed) to the queue
   • However, if the | is at the end (that is, t is empty), add s to the result.

Using this algorithm, implement a method

public static ArrayList<String> permutations(String s)

Submit a file Homework7a.java.

Pay attention to upper/lowercase. For whatever reason, it's 7a, 7b, 7c in this assignment, not 7A, 7B, 7C.

The netbrat tester is here.

Draft: Your program should work for a string of length 2.

B: P15.3 in the Chapter 15 PDF in the content area.

Submit a file Homework7b.java. Read input from System.in.

The netbrat tester is here.

Draft: Works for a single sentence without uppercase words.

C: P15.15 in the Chapter 15 PDF in the content area. Read the file from System.in and write all strings with the same hash code to System.out, in the format

hashcode1: string1, string2 ...
hashcode2: string3, string4, string 5, ...
...

Print hash codes and strings in sorted order.

Submit a file Homework7c.java.

The netbrat tester is here.

Draft: Just print out the hash code for each word in the input, in the format

hashcode1: string1
hashcode2: string2

in the order in which they occur in the input.

Note: The draft is due on Monday, April 2. You can start working on it on Friday, March 23 and finish it on April 2, and still enjoy your spring break :-)