[DATA STRUCTURE & Other Objects Using JAVA] Chapter 1 The Phases of Software Development

1.0 Introduction

1.0.1 Data Structure

A data structure is a collection of data, organized so that times can be stored and retrieved by some fixed techniques.

1.0.2 The Phases of Software Development

  1. Specification of the task
  2. Design of a solution
  3. Implementation (coding) of the solution
  4. Analysis of the solution
  5. Testing and debugging
  6. Maintenance and evolution of the system
  7. Obsolescence

The last one really surprises me. It is kind of sad for a programmer to say good-bye to his or her program which can be regarded as the baby. However, I realize that I need to code this way because I need to move on! Just like what Steve Job said, “Death is the most powerful change engine!”

1.0.3 Some Thing About Java

  • [Java](http://en.wikipedia.org/wiki/Java_(programming_language) was conceived by a group of programmers at Sun Microsystems in 1991.
  • The group was led by James Gosling.
  • Initial design was called Oak that was motivated by a desire for a single language in which programs could be developed and easily moved from one machine to another. (Great! Compile once, run everywhere!)
  • Java source code -> Byte code -> Java Runtime Environment (JRE)
  • Because the JRE controls all Java programs, there is an added level of security that comes from avoiding potential problems from running unknown programs.
  • Object-oriented programming: information hiding and component reuse

1.1 Specification, Design, Implementation

  • Specification: the specification is a precise description of the problem
  • Design: the design phase consists of formulation the steps (or algorithm) to solve the problem
  • Implementation: implementation is the actual java code to carry out the design.

1.1.1 Design Technique: Decomposing the Problem

  • The large problem is decomposed into subtasks, and subtasks are implemented as separate pieces of problem.
  • The subtask should help you produce short pseudocode—no more than a page of succinct description to solve the entire problem and ideally much less than a page.
  • Another two important things: code reusing and future updating
  • Large proportion of programmer’s time is spent maintaining and modifying existing programs.
  • When you are working on one method, you should not worry about how the other methods perform their jobs.
  • Information hiding: know only as much as you need but no more!

1.1.2 How to Write a Specification for a Java Method

  • Signature of a method: method name + parameter list + return type + modifiers

  • Procedural abstraction (method abstraction): When we pretend that we do not know how a method is implemented, we are using a form of information hiding called procedural abstraction.


  1. Short Introduction
    • method’s name
    • complete heading
    • short description
  2. Parameter Description
  3. Precondition: a precondition is a condition that is supposed to be true when a method is called.
  4. The Returns Condition or Postcondition
    • A return condition specifies the meaning of a method’s return value.
    • A postcondition is a complete statement describing what will be true when a method finishes.
  5. The Throws List

1.1.3 Throw an Exception To Indicate a Failed Precondition

  • Exceptions: violations of preconditions
  • Throwing an exception: The act of halting your own work and passing a message to the calling program is known as throwing an exception.
  • Syntax

  • IllegalArgumentException: tells a programmer that one of the method’s arguments violated a precondition.

  • What happens when an exception is thrown?

    1. The method stops its computation.
    2. An new “exception object” is created, incorporating the indicated error message.
    3. The exception, along with its error message, is passed up to the method or program that made the illegal call in the first place.

  • When an exception is not caught, the program halts, printing the error message along with a list of the method calls that led to the exception.

1.1.4 Programming Tips


Final Variables

  • Final variable means that its value will never be changed.
  • A common programming style is to use all capital letters for the names of final variables.

  • To increase clarity, some programmers declare all constants as final variables.

  • Use final variables instead of constants. Make exceptions when constant are clearer or less error prone.

Make Exception Messages Informative

Format Output with System.out.printf

1.2 Running Time Analysis

  • Time analysis: consists of reasoning about an algorithm’s speed.
  • Instead of measuring the actual elapsed time, we count certain operations that occur while carrying out the work.
  • The analysis counts the number of operations required.
  • There is no precise definition of what constitute an operation, although an operation should satisfy your intuition of a “small step”.

1.2.1 Big-O Notation

  • Precision is not always needed.
  • Quadratic time: O(n^2). The algorithm is called quadratic.
  • Linear time: O(n). The algorithm is called linear.
  • Logarithmic time: O(log n). The algorithm is called logarithmic.
  • Order of an algorithm: When a time analysis is expressed with big-O, the result is called the order of the algorithm.
  • Multiplicative constants are ignored in the big-O notation.
  • The order of an algorithm generally is more important than the speed of the processor.

1.2.2 Time Analysis of Java Methods

  • For Java, a good choice is to count the total number of Java operations, such as an assignment, an arithmetic operation, or the < comparison.
  • If a method calls other methods, we would also need to count the operations that are carried out in the other methods.
  • Frequent Linear Pattern: A loop that does a fixed amount of operations n times requires O(n) time.

1.2.3 Worst-Case, Average-Case and Best-Case Analysis

  • Worst-case analysis: Counting the maximum number of operations is called the word-case analysis, and we usually count the maximum number of required operations for inputs if a given size.
  • The actual number of operation must be guaranteed to be less than the estimate that you use in the analysis.

1.3 Testing and Debugging

  • Programming testing: programming testing occurs when you run a program and observe its behavior.

1.3.1 Choosing Test Data

  • You must know what output a correct program should produce for each test input.
  • The test inputs should include those inputs that are most likely to cause errors.

1.3.2 Boundary Values

  • Boundary value: A boundary value of a problem is an input that is one step away from a different kind of behavior.
  • Frequently zero has a special behavior, so it is a good idea to consider zero to be a boundary value whenever it is a legal input.
  • The number 1 and -1 also have special behavior in many situation, so they should be tested as boundary values whenever they are legal input.
  • In general, there is no precise definition of a boundary value, but you should develop an intuitive feel for finding inputs that are “one step away from different behavior.”

1.3.3 Fully Exercising Code

  • Make sure that each line of your code is executed at least once by some of your test data. Make sure that this rare situation is included among your set of test data.
  • If there is part of your code that is sometimes skipped altogether, make sure there is at least one test input that actually does skip this part of your code. For example, there might be a loop where the body is sometimes executed zero times. Make sure that there is a test input that causes the loop body to be executed zero times.

1.3.4 Assertion

  • Assert statements (also called assertions) are boolean expressions that can be checked for validity while a program is running.
  • Syntax

  • When an assert statement is reached

    • The boolean expression is tested.
    • if (true) { // Do nothing }
    • if (false) { // An exception calledAssertionErrorwill be thrown }.
    • When an AssertionError occurs, the method where the failure occurred will stop its computation and usually the program will stop, printing the indicated error message along with an indication of the line number where the AssertionError occurred.
  • Turn on assertion checking by using the -enableassertions option (or -ea) for the Java runtime system.

  • Assertions should not be used to check preconditions in a public method. Instead, programmers should throw exceptions which can not be turned off.