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
q program documentation is the text or graphics that provide description of
q the purpose of a function or a particular step
q the purpose of instruction in a program
§ determine the user needs
§ design the program specifications
§ review the program specifications
§ design the algorithm
q steps that will convert the available input into the desired output
q step by step solution for a given problem is called the algorithm
q a flowchart graphically details processing steps of a particular program
§ code the program
q write the program in a programming language using a program editor
q 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
q in order to find out possible errors in the program
q types of errors may be syntax errors, run-time errors and logic errors
§ get program to the user
q 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
q e.g. program expects numeric data and alphabetic data is entered
q 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
q produce an ordered sequence of steps that describe solution of problem
q this sequence of steps is called an algorithm
q Example of an Algorithm: a recipe, to assemble a brand new computer ...
q what else?
§ implementation phase
q 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
q decrease program development time
q decrease program maintenance cost
q improve the quality of software
§ structured programming achieves these goals by using
q top-down design and use of modules
q use of limited control structures (sequence, selection and repetition)
q 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:
q fast execution speed and efficient use of main memory
§ disadvantages of machine languages are
q writing machine language is tedious, difficult and time consuming
Ø Types of language-translator programs
§ assemblers
q translates the program in assembly-language into machine-language
§ compilers
q translates high-level language program into machine-language all at once
§ interpreters
q 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
q an object is a combination of data and instructions that work on data
q and is stored together as a reusable unit
q messages are instructions sent between objects
§ to qualify as an OOPL a language must incorporate concepts of
q 1. encapsulation
q 2. inheritance
q 3. polymorphism
§ encapsulation is
q combining data and instructions into a reusable structures
q encapsulation generates prefabricated components of a program
§ inheritance
q is the ability of a programming language to define a new object
q that has all the attributes of an existing object
q programmer inherits the existing object
q writes the code that describes how the new object differs from the existing one
§ polymorphism is
q the ability of an object to respond to a message in many ways
q for example, say you have a circle object and a square object
q each object has the same characteristics of drawing
q when a drawing message is sent to a circle object it draws a circle
q when a drawing message is sent to a square object it draws a square
q thus, each object has the same characteristics of drawing
q but the characteristics is implemented differently
Ø Advantages of OOPL
§ code re-use rather than reinvention and adaptable code
q these speed development & maintenance of applications and reduce cost
q 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
q produce an ordered sequence of steps that describe solution of problem
q this sequence of steps is called an algorithm
Examples of Algorithm: a recipe, to assemble a brand new computer ...
what else?
§ Implementation phase
q 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:
q It is easier to show how to go somewhere on a map than explaining
q It is easier to construct a toy if diagrams are shown
q It is easier to construct a new PC if diagrams are provided
§ Hence use pictorial format for describing an algorithm
q this is called a FLOWCHART
Ø A Flowchart
§ shows logic of an algorithm
§ emphasises individual steps and their interconnections
q 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
q 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
q 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 OperatorsOperator / 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 ScheduleOVERTIME – (2/3)*ABSENT / Bonus Paid
>40 hours
>30 but £ 40 hours
>20 but £ 30 hours
>10 but £ 20 hours
£ 10 hours / $50
$40
$30
$20
$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?