
\documentclass[11pt]{article}
\setlength{\textwidth}{5.5in}
%\setlength{\evensidemargin}{-0.5in}
\usepackage{TRmydraft} % title page report
\usepackage{wmff} % algorithm
\usepackage{yprob} % algorithm listing, code, report exercises

\usepackage{graphicx}

\pagestyle{myheadings}
\markright{Design and Program Structures\hfill}

\begin{document}

\reptitle{\bf Design and Program Structures}
\author{Dr. Jos\'e M. Garrido}

%\date{February, 2009}

\subtitle{{}}
\subsubtitle{}


\authoraffil{Department of Computer Science} 
 
%
%\halftitlepage
%

\titlepage

\mdraft
%\maketitle
%\newpage
%\tableofcontents
%\newpage

\section{Design Notations}

Designing a solution to a problem involves design of an algorithm, which will be as general as possible to solve a family or group of similar problems. To describe an algorithm, several notations are used, such as informal English, flowcharts, and pseudo-code.

An algorithm can be described at several levels of abstraction. Starting from a very high-level and general level of description of a preliminary design, to a much lower-level that has more detailed description of the design.


A notation is a more informal and higher level than a programming language. It is set of rules used for the informal description of an algorithm. Two widely-used design notations are:

\begin{itemize}
 \item Flowcharts
 \item Pseudo-code
\end{itemize}

\subsection{Flowcharts}

Flowcharts\index{flowcharts} consist of a set of symbol blocks connected by arrows. A flowchart is a visual representation for describing a sequence of design or action steps of the solution to a problem. The arrows that connect the blocks show the order in which the action steps are to be carried out. The arrows also show the flow of data.

Several simple flowchart blocks are shown in Figure~\ref{fig:ksymbols}. A flowchart always begins with a {\em start} symbol\index{start symbol}, which  has an arrow pointing from it. A flowchart ends with a {\em stop} symbol\index{stop symbol}, which has one arrow pointing to it. 

\vspace{0.1in}
\begin{figure}[h]
\centereps{3.5in}{2.47in}{figs/ksymbols.eps}
\caption{Simple flowchart symbols}
\label{fig:ksymbols}
%\vskip\baselineskip
\end{figure}
\vspace{0.1in}


The {\em process} symbol or {\em transformation} symbol is the most common and general symbol; it represents a design step. The symbol is shown as a rectangular box and represents any computation or sequence of computations carried out on some data. There is one arrow pointing to it and one arrow point from it. 

Another flowchart symbol has the shape of a vertical diamond, and it represents a selection of alternate paths in the sequence of design steps. This symbol is also shown in Figure~\ref{fig:ksymbols}. This symbol is known as a decision block or a conditional block because the sequence of instructions can take one of two directions in the flowchart.

The flowchart symbol for a data input\index{input} or output\index{output} operation is shown in Figure~\ref{fig:inout}. There is one arrow pointing into the block and one arrow pointing out from the block.

\vspace{.1in}
\begin{figure}[h]
\centereps{1.75in}{2.0in}{figs/inout1.eps}
\caption{Flowchart data input/output symbol}
\label{fig:inout}
%\vskip\baselineskip
\end{figure}
\vspace{0.1in}


For larger or more complex algorithms, flowcharts are used for the high-level description of the algorithms.

\vspace{.1in}
\begin{figure}
\centereps{1.15in}{2.682in}{figs/ksequence.eps}
\caption{A simple flowchart}
\label{fig:kseq}
%\vskip\baselineskip
\end{figure}
\vspace{0.1in}


A simple flowchart with several basic symbols is shown in Figure~\ref{fig:kseq}.  

%\newpage

\subsection{Pseudo-code}

Pseudo-code\index{pseudo-code} is a notation that uses English description for describing the algorithm that defines a problem solution. It can be used to describe relatively large and complex algorithms. Pseudo-code is much easier to understand and use than any programming language. It is relatively easy to convert the pseudo-code description of an algorithm to a high-level programming language. 

%\newpage

%\vfill

\section{Algorithmic Structures}

There are four design structures with which any algorithm can be described. These can be used with flowcharts and with pseudo-code notations. The basic design structures are:

\begin{itemize}
\item
  {\em Sequence}\index{sequence}, any task can be broken down into a sequence of steps. 
\item
  {\em Selection}\index{selection}, part of the algorithm takes a decision and select one of several alternate paths of flow of actions. This structure is also known as alternation or conditional branch.
  \item
{\em Repetition}\index{repetition}, this part pf the algorithm has a set of steps that are to be executed zero, one, or more times.  This structure is also known as looping. 
\item
  {\em Input-output}\index{input-output}, the values of variables are read from an input device (such as the keyword) or the values of the variables (results) are written to an output device (such as the screen)
\end{itemize}

%\vfill

\subsection{Sequence}

Figure~\ref{fig:kseq} illustrates the sequence structure. A simple sequence of flowchart blocks is shown. The sequence structure is the most common and basic structure used in algorithmic design. 

%\vfill

\subsection{Selection}

With the selection structure, one of several alternate paths will be followed based on the evaluation of a condition. Figure~\ref{fig:ksel} illustrates the selection structure\index{selection structure}. In the figure, the actions in {\em Action step1} are executed when the condition is true. The instructions in {\em Action step2} are executed when the condition is false. 

\vspace{.1in}
\begin{figure}[h]
\centereps{1.8in}{1.958in}{figs/ksel.eps}
\caption{Selection structure in flowchart form}
\label{fig:ksel}
%\vskip\baselineskip
\end{figure}
\vspace{0.1in}


A flowchart example of the selection structure is shown in Figure~\ref{fig:kselex}. The condition of the selection structure is $X > 0$ and when this condition evaluates to true, the block with the action {\tt increment j} will execute. Otherwise, the block with the action {\tt decrement j} is executed.

\vspace{0.1in}
\begin{figure}[h]
\centereps{1.8in}{1.958in}{figs/kselx.eps}
\caption{An example of the selection structure}
\label{fig:kselex}
%\vskip\baselineskip
\end{figure}
\vspace{0.1in}


A variation of the selection structure has multiple alternate paths, each one depends on the value of a variable. This structure is known as the {\em case\/}\index{case} construct.  Figure~\ref{fig:case} illustrates this construct. 


\vspace{.1in}
\begin{figure}[h]
\centereps{2.85in}{2.137in}{figs/case.eps}
\caption{The {\em case\/} construct}
\label{fig:case}
%\vskip\baselineskip
\end{figure}
\vspace{0.1in}


\subsection{Repetition}

The repetition structure\index{repetition} will cause a set of action steps to be repeated several times. Figure~\ref{fig:kwhile} shows this structure. The execution of the actions in {\em Action step1\/} are repeated while the condition is true. This structure is also known as the {\em while loop}\index{while loop}.




\begin{figure}[h]
%\vspace{.2in}
\centereps{2.0in}{2.264in}{figs/kwhile.eps}
\caption{Repetition structure in flowchart form}
\label{fig:kwhile}
%\vskip\baselineskip
%\vspace{0.1in}
\end{figure}

A variation of the repetition structure is shown in Figure~\ref{fig:krep}. The actions in {\em Action step1\/} are repeated until the condition becomes true. This structure is also known as the {\em repeat-until\/}\index{repeat-until}  loop.

\begin{figure}[h]
%\vspace{.2in}
\centereps{2.0in}{2.275in}{figs/krep.eps}
\caption{Repeat-until loop of the repetition structure}
\label{fig:krep}
%\vskip\baselineskip
%\vspace{0.1in}
\end{figure}

\section{Programming Statements}

Programming languages are used to implement the solution that has been designed; this includes the data descriptions and the algorithm.  A programming language has language {\em statements\/}\index{statements} that are used for data declarations and for writing the instructions. 

This section mainly deals with simple OOSimL statements, such as the assignment and I/O statements. 

\subsection{Assignment and Arithmetic Expressions}

The most used statement is the {\em assignment\/}\index{assignment} statement and is used to assign a value to a variable. The statement is written with the keyword {\bf set}. This variable must be written on the left-hand side of the equal sign, which is the assignment operator.

The value to assign can be directly copied from another variable, from a constant value, or from the value that results after evaluating an expression. 

In the following example, the constant value 1435.5 is assigned to variable {\em h} and the value 100 to variable {\em j}.
\vspace{0.1in}
\begin{quote}
{\tt \small 
\begin{algorithm}
variables
\ \ {\bf float} h
\ \ {\bf float} p
\ \ {\bf float} q
\ \ {\bf integer} j
begin
\ \ . . .
\ \ {\bf set} h = 1435.5
\ \ {\bf set} j = 100
\ \ {\bf set} p = q + 14.5 * h


\end{algorithm}
}

\end{quote}
\vspace{0.1in}

The third assignment statement in the example, variable {\em p\/} is assigned the result of evaluating the expression, $q + 14.5 * h$. 

\subsection{Simple Numeric Computing}

Arithmetic expressions are normally used in an assignment statement. For example add 5 to the value of variable $j$, subtract the value of variable $h$ from variable $p$, the assignment statements with the simple arithmetic expressions are:

\vspace{0.1in}
\begin{quote}
{\tt \small 
\begin{algorithm}
\ \ {\bf set} j = j + 5 
\ \ {\bf set} p = p - h
\end{algorithm}
}
\end{quote}
\vspace{0.1in}

In the example, in the first assignment, the new value of $j$ is assigned by adding 5 to the previous value of $j$. In the second assignment, the new value of variable $p$ is assigned the value that results after subtract the value of $h$ from the previous value of $p$.

The OOSimL language provides the {\bf add} and the {\bf subtract} statements that are equivalent to the assignments of in the example. The following two statements show the same computation.

\vspace{0.1in}
\begin{quote}
{\tt \small
\begin{algorithm}
\ \ {\bf add} 5 to j
\ \ {\bf subtract} h from p
\end{algorithm}
}
\end{quote}
\vspace{0.1in}

To add or subtract 1, the language provides the {\bf increment} and the {\bf decrement} statement. For example, {\tt increment j}, adds the constant 1 to the value of variable $j$. {\tt decrement k} subtracts the constant value 1 from the value of variable $k$.


%\subsection{More Advanced Arithmetic Expressions}

The arithmetic\index{arithmetic} expression\index{expressions} used in the assignment statements discussed previously were very simple; only basic arithmetic operations appeared in the expressions. These are addition, subtraction, multiplication, and division. 

To carry out more complex calculations, the language class library provides various numerical functions. Most of these functions are static, so to use a particular function of the {\em Math\/} library class, the name of the class must appear followed by a dot and then the name of the particular function invoked. Class {\em Math\/} is part of the class library supplied with the Java compiler. This class provides several mathematical functions, such as square root, exponentiation, trigonometric. 


For example, consider the value of the expression $\cos{x} + y$ assigned to variable $z$ and \,$\sqrt{t}$ - p%\, assigned to variable {\em y}. 

The expression in the assignment statement use the mathematical functions {\em cos\/} and {\em sqrt\/} in class {\tt Math}. The OOSimL statements are:

\vspace{0.1in}
\begin{quote}
{\tt \small 
\begin{algorithm}
\ \ {\bf set} z = Math.cos(x) + y
\ \ {\bf set} y = Math.sqrt(t) - p
\end{algorithm}
}
\end{quote}
\vspace{0.1in}

The value of the mathematical expression $b^2$ assigned to variable {\em area\/}, is coded as:

\vspace{0.1in}
\begin{quote}
{\tt \small
\begin{algorithm}
\ \ {\bf set} area = Math.pow(b, 2)
\end{algorithm}
}
\end{quote}
\vspace{0.1in}

\subsection{Console I/O}

The programming language OOSimL provides two basic statements for console input/output. The input statement reads a value of a variable from the input device (e.g., the keyboard). This statement is written with the keywords {\bf read}, for input\index{input} of a single variable. The output statement can be used for the output of a list of variables and literals, it is written with the keyword {\bf display}. The general form of the input statement is:

\vspace{0.2in}
\begin{quote}
\tt %\footnotesize
\begin{algorithm}
\ \ {\bf read} $\langle${\em variable\_name} $\rangle$ 
\end{algorithm}
\end{quote}
\rm %\normalsize
\vspace{0.2in}

The following example uses the {\bf read} statement to read a value of variable {\em h}:

\vspace{0.2in}
\begin{quote}
\tt %\footnotesize
\begin{algorithm}
\ \ {\bf read} h
\end{algorithm}
\end{quote}
\rm %\normalsize
\vspace{0.2in}

The input statement implies an assignment statement for the variable {\em h}, because the variable changes its value to the new value that is read from the input device.

The output\index{output} statement writes the value of one or more variables to the output device. The variable does not change their values. The general form of the output statement is:

\vspace{0.1in}
\begin{quote}
{\tt \small 
\begin{algorithm}
\ \ {\bf display} $\langle${\em data\_list} $\rangle$ 
\end{algorithm}
}
\end{quote}
\vspace{0.1in}

With the output statement, a list of data items can be displayed on the console. The following example displays on the console: a string literal, followed by the value of variable {\em h\/}, followed by another string literal, and followed by the value of variable {\em q\/}.

\vspace{0.1in}
\begin{quote}
{\tt \small 
\begin{algorithm}
\ \ {\bf display} "value of h: ", h, " value of q: ", q
\end{algorithm}
}
\end{quote}  
\vspace{0.1in}


\section{Computing Area and Circumference}

This problem computes the area and circumference of a circle, given its radius.
The high-level algorithm description in informal pseudo-code notation is:

\begin{enumerate}
\item
Read the value of the radius of a circle, from the input device.
\item
Compute the area of the circle.
\item
Compute the circumference of the circle.
\item
Print or display the value of the area of the circle to the output device.
\item
Print or display the value of the circumference of the circle to the output device.
\end{enumerate}

A more detailed algorithm description follows:

\begin{enumerate}
\item
Read the value of the radius {\em r\/} of a circle, from the input device.
\item
Establish the constant $\pi$ with value 3.14159.
\item
Compute the area of the circle, $area = \pi \times r ^2$.
\item
Compute the circumference of the circle $cir = 2 \times \pi \times r$.
\item
Print or display the value of {\em area\/} of the circle to the output device.
\item
Print or display the value of {\em cir\/} of the circle to the output device.
\end{enumerate}

The following OOSimL program implements the data description and the algorithm for calculating the area of a circle. The example has a single class that includes function {\em main\/}. This class calls a function, {\em pow\/} of the library class, {\em Math\/}. 


\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
description
   This class computes the area and circumference of
   A circle, given its radius. This value is read 
   using console I/O.
   */
class Circle_comp is
 public
 function main is
    // data descriptions
 constants
    define PI = 3.14159 of type double
 variables  
    define r of type float
    define area of type double
    define cir of type double
 begin
    // instructions starts here
    display "enter value of radius: "
    read r
    // compute area of circle
    set area = PI * Math.pow(r, 2)
    // compute circumference of circle
    set cir = 2.0 * PI * r
    // now print the results
    display "Area of circle is: ", area
    display "Circumference of circle is: ", cir
 endfun main
endclass Circle_comp
\end{verbatim}
}
%\end{quote}
\vspace{0.1in}

After compiling the program is executed and produces the following results on the console:

\vspace{0.1in}
%\begin{quote}
{\tt \small
\begin{verbatim}
Enter value of radius: 2.75
Area of circle is: 23.758274375
Circumference of circle is: 17.278745
\end{verbatim}
}
%\end{quote}
\vspace{0.1in}



\end{document}
