Math 121: Introduction to Computing Handout #22The Demo Programs in Folder Assignment5A. Arrays. The concept of an array as a linear list of data, i.e., as the programmingmanifestation of a list, is not a difficult one. There is some new syntax associated witharrays, but that also should come easily. In learning about arrays, the harder concepts tomaster are1. How arrays are represented internally. Understanding the internal representation ofarrays is important for building your intuition about how array parameters work.2. How to use arrays effectively in applications. Even though the mechanics of arraysare simple, it may not always be apparent when to use them. For applications thatinvolve lists of data values, arrays come up naturally. There are, however, severalcircumstances in which the idea of using an array is harder to see.The Roberts text includes an extensive discussion of the representation of arrays. Thishandout focuses on the second question in the context of a specific application that usesarrays in two rather different contexts.The program LetterFrequency.java creates a table of the frequency of lettersappearing in a text file. Such a program could be used in solving cryptograms, simpleletter-substitution ciphers in which each letter in the plaintext message is replaced bysome other letter. As an example, given a file containing the following cryptogram:UTK UR VAKGK LKT NG HKTNBG VU VAK UVAKE;QTF GU UR VAKGK. MANIA NG VAK TQVBEQO LQT,QTF MANIA VAK GXNENV? MAU FKINXAKEG VAKL?-- GAQZKGXKQEK, IULKFY UR KEEUEGthe LetterFrequency program should produce the following output for this file:– 2 –This program takes account of the following requirements:• The program should count only the letters in the file. All other characters should beignored.• The program should ignore the case of each letter. Thus, if the file contains both anuppercase A and a lowercase a, the program should treat them as the same letter andmake two entries in the corresponding counting array.• The report at the end should be in order by letter and should not include any lettersthat do not appear in the cryptogram.Letter-frequency programs are useful because they suggest what letters in the cryptogrammight correspond to the most common letters in English. For example, in the sample runabove, the characters K, A, and G each occur frequently and therefore might representletters such as E or T in the original.The program List.java illustrates by toy example how a FORTRAN programmer wouldimplement list-management and garbage collection in the bad old days. Here the data arecharacters, so that part of memory is allocated as an array of characters. A second array,of integers, encodes the list of character array entries that is in use, and the list ofcharacter array entries that is free. Finally, individual integers point to the heads of thetwo lists. Since array indexing starts at 0, the value -1 connotes a null pointer.– 3 –B. The ArrayList and HashMap Classes Most of the power associated with modern,object-oriented languages such as Java does not come from the language itself but insteadderives from the vast array of standard library classes that accompanies the languageitself. For Java, that set of libraries is called the Java Development Kit, or JDK for short.The two classes ArrayList and HashMap form part of a much larger structure called theJava Collections Framework, which was added to the JDK as part of release 1.2 (we’renow up to JDK version 1.5). As its name implies, the Java Collections Framework isdesigned to make it easier for programmers to work with collections of data of variouskinds. The ArrayList class is designed to make it easier to work with ordered lists of datawithout having to take account of the low-level details of arrays. The HashMap classprovides the ability to organize a collection, not by a linear order, but rather by setting upan association between a set of keys and a corresponding set of values.Given any class in a toolkit like the JDK, it is possible to understand that class from avariety of perspectives. From a holistic perspective, each class is defined in terms by itsabstract behavior. In this view, the important information about a class consists of thepublic methods it exports and a high-level model of what those methods do. From areductionistic perspective, on the other hand, a class is defined in terms of its underlyingimplementation. At this level, the important information lies in the actual code for themethods it contains. If you are creating a class, you need to be concerned about each ofthese perspectives. In the more likely case that you are using a class as a tool, you canlimit yourself to the more holistic, abstract view. In programming parlance, code thatmakes use of a class—and by extension the programmers who write that code—are calledclients of that class. As a general rule, clients can remain blissfully ignorant of theimplementation of a class and concentrate solely on the abstraction it presents to theoutside world.In Math 121, our primary concern is to learn how to use classes as clients, but thealgorithms and data structures course will look more deeply into how these classes areimplemented and how clever algorithms make them as efficient as possible.The ArrayList classA detailed description of this class appears in the Roberts text. The most importantmethods for the ArrayList class appear in Figure 10-4. This handout focuses on therelative advantages and disadvantages of ArrayLists with respect to Java arrays and,more specifically, the complexity of using wrapper classes to store primitive data valuesin an ArrayList.The most important advantages that ArrayLists offer over arrays are the following:– 4 –• An ArrayList can change its size dynamically without forcing the client to take careof the details. Once allocated, an array has a fixed length. Although it is possible tosimulate the behavior of an ArrayList by reallocating a new array with the desiredsize and reassigning that value to the array variable, the client programmer mustexplicitly copy values from the old array into the new one.• The fact that ArrayLists can grow and shrink dynamically makes it possible to defineoperations like add and remove that insert and delete elements. Java arrays offer noanalogous