Algorithms and Programming Techniques



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)

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

▪ problem solving phase

❑ 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

▪ 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 machine-language 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

➢ PL/I

▪ Programming Language One created in 1960

▪ general purpose language for powerful computations and

▪ sophisticated data structures

▪ today largely used in the oil industry

➢ BASIC

▪ Beginners Allpurpose Symbolic Instruction Code created in 1960

▪ easy to learn interactive language on a time-sharing computer

➢ PASCAL

▪ 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

➢ C

▪ 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

▪ is a language for symbol processing

➢ Logo

▪ 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 object

❑ each object has the same characteristics of drawing

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

❑ 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

▪ code re-use rather than reinvention and adaptable code

❑ these speed development & maintenance of applications and reduce cost

❑ Smaltalk, Objective-C and C++ are examples of OOPL

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.

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

Flowchart:

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

Flowchart:

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

Flowchart:

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:

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)

IF–THEN–ELSE 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

Flowchart:

NESTED IFS

➢ One of the alternatives within an IF–THEN–ELSE statement

▪ may involve further IF–THEN–ELSE 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 – (2/3)*ABSENT |Bonus Paid |

|>40 hours |$50 |

|>30 but ( 40 hours |$40 |

|>20 but ( 30 hours |$30 |

|>10 but ( 20 hours |$20 |

|( 10 hours |$10 |

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?

-----------------------

}low-level languages

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: 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 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download