Dynamic Data Structures

Array Lists

  • See example routine ("Read words from file")
  • Reads in all the words from the file and puts them into an array list
ArrayList<String> words = new ArrayList<String>();
try{
    Scanner scan = new Scanner (new File(fileName));
    while (scan.hasNext()) {
        words.add(scan.next());
    }
}
catch (FileNotFoundException e) {
    System.out.println("File NOT found");
}

Printing Anagrams

  • See ("Printing Anagrams")

Counting Letters

  • determine if a set of letters contains the letters of a word.
  • Pass in both of as strings.
  • (See "Counting Letters")

Removing Letters

  • Strings are immutable, don't forget!
  • See the routine in PPT.

Summary of Array Lists

  • ArrayList allows us to create an expanding array of any Object type.
    • Primitive types are not allowed.
    • Use angle brackets to indicate the type
ArrayList<String> T = new ArrayList<String>();
  • A parameter in the constructor indicates initial capacity.
ArrayList<Double> D = new ArrayList<Double>(25);
  • ArrayList isn't all that fast, especially for wrapped primitive types.
String s0 = "Hello";
ArrayList T = new ArrayList();
T.add(s0);
  • See the ArrayList Methods.

Project Euler 25

  • Could use BigInt
  • doubles would also suffice to just get an estimate

Project Euler 48

  • BigInt is relevant again (actually not, too big)
  • We only need the low order 10 digits, long has 20 digits of accuracy
    • we use a squaring routine and a mod operation (by 1010)

Project Euler 92

  • Use a (partial) memos table to keep track of known

Project Euler 97

  • SUPER easy
  • All we need is a method to compute mod 1010
  • don't forget to add 1.
  • DONT NEED BIGINT.