1.1   Programming Model


This section under major construction.


Our study of algorithms is based upon implementing them as programs written in the Java programming language. We do so for several reasons:

Primitive data types and expressions.

A data type is a set of values and a set of operations on those values. The following four primitive data types are the basis of the Java language: A Java program manipulates variables that are named with identifiers. Each variable is associated with a data type and stores one of the permissible data-type values. We use expressions to apply the operations associated with each type.

basic building blocks for Java programs
The following table summarizes the set of values and most common operations on those values for Java's int, double, boolean, and char data types.

primitive data types in Java

Statements.

A Java program is composed of statements, which define the computation by creating and manipulating variables, assigning data-type values to them, and controlling the flow of execution of such operations.


The following table illustrates different kinds of Java statements.

Java statements

Arrays.

An array stores a sequence of values that are all of the same type. If we have N values, we can use the notation a[i] to refer to the ith value for any value of i from 0 to N-1.

Static methods.

Static methods are called functions in many programming languages, since they can behave like mathematical functions. Each static method is a sequence of statements that are executed, one after the other, when the static method is called.








APIs.

Strings.

Java's string data type

Input and output.

Binary search.

Below is a complete Java program BinarySearch.java that illustrates many of the basic features of our programming model. It implement a classic algorithm known as binary search and tests it for an application known as whitelist filtering.

anatomy of binary search
The static method rank() takes an integer key and a sorted array of int values as arguments and returns the index of the key if it is present in the array, -1 otherwise. It accomplishes this task by maintaining variables lo and hi such that the key is in a[lo..hi] if it is in the array, then entering into a loop that tests the middle entry in the interval (at index mid). If the key is equal to a[mid], the return value is mid; otherwise the method cuts the interval size about in half, looking at the left half if the key is less than a[mid] and at the right half if the key is greater than a[mid]. The process terminates when the key is found or the interval is empty.

binary search in an ordered array









Input and output libraries.

Here is a list of the input and output libraries that we use throughout the textbook and beyond.


§ PROGRAM DESCRIPTION / JAVADOC
1.5 StdIn.java read numbers and text from standard input
1.5 StdOut.java write numbers and text to standard output
1.5 StdDraw.java draw geometric shapes in a window
1.5 StdAudio.java create, play, and manipulate sound
2.2 StdRandom.java generate random numbers
2.2 StdStats.java compute statistics
2.2 StdArrayIO.java read and write 1D and 2D arrays
3.1 In.java read numbers and text from files and URLs
3.1 Out.java write numbers and text to files
3.1 Draw.java draw geometric shapes
3.1 Picture.java process digital images
3.2 Stopwatch.java measure running time
- BinaryStdIn.java read bits from standard input
- BinaryStdOut.java write bits to standard output
- BinaryIn.java read bits from files and URLs
- BinaryOut.java write bits to files


We briefly describe the input and output libraries and include a sample client.


Standard input and standard output.

StdIn.java and StdOut.java are libraries for reading in numbers and text from standard input and printing out numbers and text to standard output. Our versions have a simpler interface than the corresponding Java ones (and provide a few technical improvements). RandomSeq.java generates random numbers in a given range. Average.java reads in a sequence of real numbers from standard input and prints their average on standard output.
% java Average
10.0 5.0 6.0 3.0 7.0 32.0
3.14 6.67 17.71
<Ctrl-d>
Average is 10.05777777777778
In.java and Out.java are object-oriented versions that support multiple input and output streams, including reading from a file or URL and writing to a file.


Standard drawing.

StdDraw.java is an easy-to-use library for drawing geometric shapes, such as points, lines, and circles. RightTriangle.java draws a right triangle and a circumscribing circle.


Draw.java is an object-oriented versions that support drawing in multiple windows.


Standard audio.

StdAudio.java is an easy-to-use library for synthesizing sound. Tone.java reads in a frequency and duration from the command line, and it sonifies a sine wave of the given frequency for the given duration.
% java Tone 440.0 3.0


Image processing.

Picture.java is an easy-to-use library for image processing. Scale.java takes the name of a picture file and two integers (width w and height h) as command-line arguments and scales the image to w-by-h.

% java Scale mandrill.jpg 298 298
298-by-298
% java Scale mandrill.jpg 200 200
200-by-400
% java Scale mandrill.jpg 200 400
200-by-400


Q + A

Q. How important is it to use a good shuffling algorithm?

A. Here's an amusing anecdote of what happens when you don't do it correctly (and you're business is online poker!). If you're running an online casino, here's the recommended approach for shuffling a deck of cards: (i) get a cryptographically secure pseudo-random number generator, (ii) assign a random 64-bit number to each card, (iii) sort the cards according to their number.

Creative Problems

  1. Binomial distribution. Estimate the number of recursive calls that would be used by the method call binomial1(100, 50, .25) in Binomial.java. Develop a better implementation that is based on saving computed values in an array.

Web Exercises

  1. Sattolo's algorithm. Write a program Sattolo.java that generates a unifomly distributed cycle of length N using Sattolo's algorithm.

  2. Wget. Write a program Wget.java that reads in data from the URL specified on the command line and saves it in a file with the same name.
    % java Wget http://introcs.cs.princeton.edu/data/codes.csv
    % more codes.csv
    United States,USA,00
    Alabama,AL,01
    Alaska,AK,02
    ...
    

  3. Right triangle. Write a client RightTriangle.java that draws a right triangle and a circumscribing circle.

      % java RightTriangle
    right triangle and circumscribing circle

  4. Bouncing ball. Write a program BouncingBall.java that illustrates the motion of a bouncing ball.

    Your browser can not display this movie.
    Be sure that Javascript is enabled and that you have Flash 9.0.124 or better.