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
-
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:
-
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
-
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
-
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)
-
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?
-
implement the program in some programming language (Pascal, Basic, C)
F igure 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
-
C
}low-level languages
ategories of programming languages are
-
machine
-
assembly
-
high-level
-
fourth-generation
-
fifth-generation
-
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
-
Types of language-translator programs
-
translates the program in assembly-language into machine-language
-
translates high-level language program into machine-language all at once
-
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
-
FORmula TRANslator introduced in 1957
-
for use by scientists, engineers and mathematicians
-
well suited for complex numeric calculations
-
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
-
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
-
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
-
is a language that processes symbol sequences (lists) rather than numbers
-
designed to handle data strings more efficiently than others
-
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
-
1. encapsulation
-
2. inheritance
-
3. polymorphism
-
combining data and instructions into a reusable structures
-
encapsulation generates prefabricated components of a program
-
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
-
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
-
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:
-
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?
-
implement the program in some programming language
-
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: 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”
The Flowchart -
Easier to convey ideas by picture than by words
-
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
-
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”
F
TRACE TABLE:
MARK
|
GRADE
|
STATUS
|
M1=80
|
80
|
|
M2=30
|
+ 30
|
|
M3=40
|
+ 40
|
|
M4=30
|
+ 30 /4
|
|
|
= 45
|
FAIL
|
lowchart:
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)
Figure 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
>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?
Share with your friends: |