Newsletter sign-up
View all newsletters

Enterprise Java Newsletter
Stay up to date on the latest tutorials and Java community news posted on JavaWorld

Sponsored Links

Optimize with a SATA RAID Storage Solution
Range of capacities as low as $1250 per TB. Ideal if you currently rely on servers/disks/JBODs

JavaWorld.com > Java Standard Edition >

Study guide: Datastructures and algorithms, Part 1

Brush up on Java terms, learn tips and cautions, review homework assignments, and read answers to student questions

By Jeff Friesen, JavaWorld.com, 05/02/03

  • Print
  • Feedback
.

Glossary of terms

algorithm
A sequence of instructions that accomplishes a task in a finite amount of time.


anonymous array
An array created by a keyword new with an array intializer.


array
A sequence of elements, where each element associates with at least one index.


binary-search
An algorithm that searches, in a divisive fashion, a one-dimensional array for a specific data item.


bubble-sort
An algorithm that makes various passes over a one-dimensional array. Adjacent data items are compared and (possibly) swapped during each pass.


data items
Primitive type values or objects, via references.


datastructure
A container class that provides storage for data items and capabilities for storing and retrieving data items.


dimension
The number of indexes associated with an element in an array.


element
A group of memory bytes that stores a single data item.


flowchart
A visual representation of an algorithm's control flow.


index
Nonnegative integer.


linear-search
An algorithm that linearly searches a one-dimensional array for a specific data item.


matrix
A synonym for a two-dimensional array.


matrix-multiplication
An algorithm that multiplies one matrix by another matrix.


pseudocode
An algorithm's textual representation that approximates the final source code.


ragged array
A degenerate matrix where rows have different numbers of column elements.


sort
Order.


table
A synonym for a two-dimensional array.


Tips and cautions

These tips and cautions will help you write better programs and save you from agonizing over why the compiler produces error messages.

Tips

  • Java developers often place square bracket characters after type (int [] test_scores) rather than after variable_name (int test_scores []) when declaring an array variable. Keeping all type information in one place improves the source code's readability.
  • Another commonly used algorithm for one-dimensional arrays copies the elements from a source one-dimensional array to a destination one-dimensional array. Rather than write your own algorithm to accomplish that task, use java.lang.System's public static void arraycopy(Object src, int srcindex, Object dst, int dstindex, int length) method, which is the fastest way to perform the copy. (I will explore this method in a future article.)
  • In source code, specify .length (as in d.length) instead of an array's actual length. That way, you eliminate the risk of introducing length-related bugs into your code should you later change the array's length in that array's creation code.


Cautions

  • When creating a one-dimensional array based on a primitive type, the compiler requires the same primitive type keyword to appear on both sides of the equal-to operator. Otherwise, the compiler reports an error. For example, int [] test_scores = new long [20]; is illegal because keywords int and long represent incompatible primitive types.
  • Do not specify an integer expression between the square brackets on the right side of the equal-to operator. Otherwise, the compiler reports an error. For example, new int [3] { 70, 80, 20, 30 } causes the compiler to report an error because the compiler can already determine the number of elements from the initializer. Furthermore, the discrepancy arising from the 3 between the square brackets and four entries in the initializer signify a probable mistake.
  • Exercise caution when accessing array elements because you might receive an ArrayIndexOutOfBoundsException or an ArrayStoreException.
  • Matrix-multiplication requires that the number of columns in the left matrix (A) equal the number of rows in the right matrix (B). For example, to multiply a four-row by five-column matrix A by matrix B (as in A x B), B must contain exactly five rows.


Homework

  • Draw a flowchart that expresses the binary-search algorithm's control flow.
  • A magic square is an n x n matrix of integers from 1 to n2, such that the sum is the same for every row, column, and diagonal. If n equals 5, for example, we end up with the following matrix (where the common sum is 65):

    ==========================
| 15 |  8 |  1 | 24 | 17 |
|------------------------|
| 16 | 14 |  7 |  5 | 23 |
|------------------------|
| 22 | 20 | 13 |  6 |  4 | 
|------------------------|
|  3 | 21 | 19 | 12 | 10 |
|------------------------|
|  9 |  2 | 25 | 18 | 11 |
==========================


    A simple algorithm for generating a magic square when n is odd:

    • Begin with 1 in the top row
    • Move up and left, assigning numbers in increasing order to empty squares
    • If you fall off the square, imagine the same square as tiling the plane and continue
    • If a square is occupied, move down instead and continue


    Express the algorithm above in pseudocode and as a Java application for any odd n.

  • What does int [] x = { }; accomplish (assuming that code fragment is legal)?


Answers to last month's homework

Last time, I asked you to answer two questions. Here are my answers (which appear in red).

  • Not specifying the closing round bracket metacharacter in an embedded flag expression is one example of an illegal pattern. Identify two other illegal pattern examples.

    Forgetting the closing square bracket character in a character class (e.g., [abc).

    Placing a backslash prior to any alphabetic character that does not denote an escaped construct (e.g., \j). Such characters are reserved for future extensions to the regular-expression language.

  • Create a regex that matches phone numbers with or without area codes. If present, a three-digit area code must appear between round bracket characters. Optional space characters may appear between the area code and the number. The number consists of three digit characters followed by a hyphen character, followed by four digit characters. No space characters may appear on either side of the hyphen. Example: (123) 555-4678.

    The following regex matches phone numbers according to the previous specification: (\(\d{3}\))?\s*\d{3}-\d{4}



  • Print
  • Feedback