ALGORITHMS AND PROGRAMMING TECHNIQUES

Introduction to Program Development and Problem Solution

Computers do what we tell them to do NOT what we want them to do Computer Programming involves writing instructions and giving them to the computer to complete a task.

A computer program or software is:

a set of instructions written in a computer language in order to be executed by a computer to perform a useful task

Ex: Application software packages, such as word processors, spreadsheets and databases are all computer programs

A Computer Programmer is
is a person who translates the task you want a computer to do into a form that a computer can understand

A well designed computer program must be:

correct and accurate easy to understand easy to maintain and update efficient reliable flexible

The program development process involves the following steps:

document the program
program documentation is the text or graphics that provide description of the purpose of a function or a particular step the purpose of instruction in a program

determine the user needs

 design the program specifications review the program specifications design the algorithm
steps that will convert the available input into the desired output step by step solution for a given problem is called the algorithm a flowchart graphically details processing steps of a particular program

code the program

write the program in a programming language using a program editor a program editor is a program that allows to type, edit and save a program code on a disk

compile, test and debug the program

in order to find out possible errors in the program types of errors may be syntax errors, run-time errors and logic errors

get program to the user

install software on the users computer and offer training

Types of programming errors

Syntax of a programming language is the set of rules to be followed when writing a program syntax error occurs when these rules are violated run-time errors occur when invalid data is entered during program execution

e.g. program expects numeric data and alphabetic data is entered program will crash

logic error will not stop the program but results will be inaccurate The process of finding and correcting errors in a program is called debugging

For successful programming

give no ambiguity in program instructions give no possibility of alternative interpretations make sure there is only one course of action

 Programming task can be made easier

by breaking large and complex programs into smaller and less complex subprograms (modules) problem solving phase

Programming task can be separated into 2 phases (see Fig. 1)

produce an ordered sequence of steps that describe solution of problem this sequence of steps is called an algorithm Example of an Algorithm: a recipe, to assemble a brand new computer ... what else?

implementation phase
implement the program in some programming language (Pascal, Basic, C)

Figure 1: Problem Solving and Programming

What is structured programming

a programming technique that splits the program into smaller segments (modules) to

decrease program development time decrease program maintenance cost improve the quality of software

structured programming achieves these goals by using

top-down design and use of modules

use of limited control structures (sequence, selection and repetition) management control

Top-down design starts with major functions involved in a problem

and divide them into sub-functions until the problem has been divided as much as possible

Categories of programming languages are

machine low-level languages assembly high-level fourth-generation fifth-generation

Machine language is

made up of binary 1s and 0s this is the only programming language the computers can understand advantages of machine languages are:

fast execution speed and efficient use of main memory disadvantages of machine languages are writing machine language is tedious, difficult and time consuming

Types of language-translator programs

assemblers
translates the program in assembly-language into machine-language

compilers
translates high-level language program into machinelanguage all at once

interpreters
translates high-level language into machine-language a line at a time

Major high-level languages are

FORTRAN, COBOL, PL/I, BASIC, PASCAL, C, LISP, Prolog, Logo

 FORTRAN

FORmula TRANslator introduced in 1957 for use by scientists, engineers and mathematicians well suited for complex numeric calculations

COBOL

COmmon Business Oriented Language a programming language used for business data processing designed to handle large data files Programming Language One created in 1960 general purpose language for powerful computations and sophisticated data structures today largely used in the oil industry

PL/I

BASIC

Beginners Allpurpose Symbolic Instruction Code created in 1960 easy to learn interactive language on a time-sharing computer Named after Blaise Pascal and created in 1960 suited to both scientific and file processing applications designed to teach structured programming and top-down design

PASCAL

Developed at Bell Labs in 1970s used advantages of both high-level and low-level languages C gives programmers extensive control over computer hardware incorporates sophisticated control and data structures C++ is the object oriented version of C

LISP

is a language that processes symbol sequences (lists) rather than numbers designed to handle data strings more efficiently than others

Prolog Logo

is a language for symbol processing

is an interactive education oriented language designed to teach inexperienced users logic and programming techniques includes list processing capabilities employs a triangular object called turtle to draw, animate and color images very simply

Object-Oriented Programming Languages (OOPL)

there are two main parts of a program, instructions and data traditional prog. languages treat instructions and data as separate entities an OOPL treats a program as a series of objects and messages

an object is a combination of data and instructions that work on data and is stored together as a reusable unit messages are instructions sent between objects

to qualify as an OOPL a language must incorporate concepts

of

1. encapsulation 2. inheritance 3. polymorphism

encapsulation is
combining data and instructions into a reusable structures encapsulation generates prefabricated components of a program

inheritance

is the ability of a programming language to define a new

object

that has all the attributes of an existing object programmer inherits the existing object writes the code that describes how the new object differs from the existing one

polymorphism is

the ability of an object to respond to a message in many

ways

for example, say you have a circle object and a square each object has the same characteristics of drawing

object

circle

when a drawing message is sent to a circle object it draws a

when a drawing message is sent to a square object it draws a square thus, each object has the same characteristics of drawing but the characteristics is implemented differently

Advantages of OOPL

these speed development & maintenance of applications and reduce cost Smaltalk, Objective-C and C++ are examples of OOPL

code re-use rather than reinvention and adaptable code

ALGORITHMS AND FLOWCHARTS

A typical programming task can be divided into 2 phases:
Problem solving phase
produce an ordered sequence of steps that describe solution of problem this sequence of steps is called an algorithm Examples of Algorithm: a recipe, to assemble a brand new computer ... what else?

Implementation phase

implement the program in some programming language

Steps in Problem solving

First produce a general algorithm (You can use pseudocode) Refine the algorithm successively to get step by step detailed algorithm that is very close to a computer language. Pseudocode is an artificial and informal language that helps programmers develop algorithms. Pseudocode is very similar to everyday English.

Example 1: Write an algorithm to determine the students final grade and indicate weather it is passing or failing. The final grade is calculated as the average of four marks. Solution: Pseudocode: by 4 Input a set of 4 marks Calculate their average by summing and dividing if average is below 50 Print FAIL else Print PASS

Detailed Algorithm: Step 1: Input M1, M2,M3,M4 Step 2: GRADE = (M1+M2+M3+M4)/4 Step 3: if (GRADE <50) then Print FAIL else Print PASS

The Flowchart
Easier to convey ideas by picture than by words
Examples:

It is easier to show how to go somewhere on a map than explaining It is easier to construct a toy if diagrams are shown It is easier to construct a new PC if diagrams are provided

Hence use pictorial format for describing an algorithm

this is called a FLOWCHART

A Flowchart
shows logic of an algorithm emphasises individual steps and their interconnections

e.g. control flow from one action to the next

standard flowchart symbols are shown below

Example 1: Write an algorithm to determine the students final grade and indicate weather it is passing or failing. The final grade is calculated as the average of four marks. Pseudocode: Input a set of 4 marks Calculate their average by summing and dividing by 4 if average is below 50 Print FAIL else Print PASS Detailed Algorithm: Step 1: Input M1, M2,M3,M4 Step 2: GRADE = (M1+M2+M3+M4)/4 Step 3: if (GRADE <50) then Print FAIL else Print PASS Flowchart:
START

TRACE TABLE: MARK M1=80 M2=30 M3=40 M4=30 GRADE 80 + 30 + 40 + 30 /4 = 45 STATUS

Input M1,M2,M3,M4

GRADE=(M1+M2+M3+M4)/4

FAIL

IS GRADE<5 0

PRINT PASS

PRINT FAIL

STOP

Example 2: Write an algorithm and draw a flowchart to convert the length in feet to centimeter. Pseudocode: Input the lenght in feet (Lft) Calculate the length in cm (Lcm) by multiplying LFT with 30 Print LCM Algorithm: Step 1: Input Lft Step 2: Lcm = Lft x 30 Step 3: Print Lcm
START

Flowchart:

Input Lft

Lcm = Lft x 30

Print Lcm

STOP

Example 3: Write an algorithm and draw a flowchart that will read the two sides of a rectangle and calculate its area. Pseudocode: Input the width (W) and Length (L) of a rectangle Calculate the area (A) by multiplying L with W Print A Algorithm: Step 1: Input W,L Step 2: A = L x W Step 3: Print A
START

Flowchart:

Input W, L

A=LxW

Print A

STOP

Example 4: Write an algorithm and draw a flowchart that will calculate the roots of a quadratic equation ax2 + bx + c = 0 Hint: d = sqrt (b2 4ac), and the roots are: x1 = (b + d)/2a and x2 = (b d)/2a Pseudocode: Input the coefficients (a, b, c) of the quadratic equation Calculate the discriminant d Calculate x1 Calculate x2 Print x1 and x2 Algorithm: Step 1: Input a, b, c Step 2: d = sqrt (b2 4 x a x c) Step 3: x1 = (b + d) / (2 x a) Step 4: x2 = (b d) / (2 x a) Step 5: Print x1 and x2

Flowchart:

START

Input a, b, c d = sqrt(b2 4 x a x c) x1 = (b + d) / (2 x a) X2 = (b d) / (2 x a)

Print x1 and x2

STOP

DECISION STRUCTURES The expression A>B is a logical expression

it describes a condition we want to test if A>B is true (if A is greater than B) we take the action on left of

print the value of A (see Fig. 2)

if A>B is false (if A is not greater than B) we take the action on right

print the value of B (see Fig. 2)

Y Figure 2:

is A>B

Print A

Print B

IFTHENELSE STRUCTURE The structure is as follows

If condition then true alternative else false alternative endif

The algorithm for the flowchart in figure 2 is as follows:

If A>B then print A else print B endif

Here > is called the relational operator. Table 1 gives the possible relational operators:

Relational Operators Operator Meaning > Greater than < Less than = Equal to Greater than or equal to Less than or equal to Not equal to

Example 5: Write an algorithm that reads two values, determines the largest value and prints the largest value with an identifying message. Algorithm: Step 1: Input VALUE1, VALUE2 Step 2: if VALUE1 > VALUE2 then MAX = VALUE1 else MAX = VALUE2 endif Step 3: Print The largest value is, MAX
START Input VALUE1,VALUE 2 Y is
VALUE1>VALUE2

Flowchart:

MAX = VALUE1

MAX = VALUE2

Print The largest value is, MAX

STOP

NESTED IFS One of the alternatives within an IFTHENELSE statement may involve further IFTHENELSE statement Example 6: Write an algorithm that reads three numbers and prints the value of the largest number. Algorithm: Step 1: Input N1, N2, N3 Step 2: if N1>N2 then if N1>N3 then MAX = N1 [N1>N2, N1>N3] else MAX = N3 [N3>N1>N2] endif else if N2>N3 then MAX = N2 [N2>N1, N2>N3] else MAX = N3 [N3>N2>N1] endif endif Step 3: Print The largest number is, MAX

Flowchart: Draw the flowchart of the above Algorithm.

Example 7: Write and algorithm and draw a flowchart to a) read an employee name (NAME), overtime hours worked (OVERTIME), hours absent (ABSENT) and b) determine the bonus payment (PAYMENT). Bonus Schedule OVERTIME Bonus Paid (2/3)*ABSENT >40 hours $50 $40 >30 but 40 hours $30 >20 but 30 hours $20 >10 but 20 hours $10 10 hours Algorithm: Step 1: Input NAME,OVERTIME,ABSENT Step 2: if OVERTIME(2/3)*ABSENT > 40 then PAYMENT = 50 else if OVERTIME(2/3)*ABSENT > 30 then PAYMENT = 40 else if OVERTIME(2/3)*ABSENT > 20 then PAYMENT = 30 else if OVERTIME(2/3)*ABSENT > 10 then PAYMENT = 20 else PAYMENT = 10 endif endif endif endif Step 3: Print Bonus for, NAME is $, PAYMENT Flowchart: Draw the flowchart of the above algorithm?