Advertisement: Support JavaWorld, click here!
May 2003
HOME FEATURED TUTORIALS COLUMNS NEWS & REVIEWS FORUM JW RESOURCES ABOUT JW

Java 101

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

Summary
Welcome to the Java 101 study guide. This guide complements "Data Structures And Algorithms, Part 1." It provides a glossary of terms specific to that article, tips and cautions, homework, and Jeff Friesen's answers to questions from your fellow students.

The Java 101 study guides are evolving documents—they change periodically. For example, if you submit a question long after Jeff posts the relevant study guide, your question and his answer will eventually make its way onto that guide. Furthermore, from time to time, he will post additional examples and other material that clarifies an article's topic, so be sure to revisit the study guides periodically.

By Jeff Friesen

Index


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.

Back to index

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.

Back to index

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)?

Back to index

Answers to last month's homework

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

Back to index




Advertisement: Support JavaWorld, click here!


HOME |  FEATURED TUTORIALS |  COLUMNS |  NEWS & REVIEWS |  FORUM |  JW RESOURCES |  ABOUT JW |  FEEDBACK

Copyright © 2004 JavaWorld.com, an IDG company