Lesson 1 - Lecture notes 1

Science, Technology, and Society (DMC-College Foundation)

Scan to open on Studocu

Downloaded by Jaylien Rose Galamay Esteban

 Studocu is not sponsored or endorsed by any college or university

Downloaded by Jaylien Rose Galamay Esteban

CSC307/Complexity and Algorithm
Introduction to Design and Analysis of
Algorithm

MODULE NO. 1 /LESSON NO. 1

Objectives:

1. (Cognitive)
2. (Affective)
3. (Psychomotor)

INTRODUCTION TO DESIGN AND ANALYSIS OF ALGORITHM

An algorithm is a set of steps of operations to solve a problem performing calculation,
data processing, and automated reasoning tasks. An algorithm is an efficient method that can
be expressed within finite amount of time and space.

An algorithm is the best way to represent the solution of a particular problem in a very
simple and efficient way. If we have an algorithm for a specific problem, then we can
implement it in any programming language, meaning that the algorithm is independent from
any programming languages.

Algorithm Design

The important aspects of algorithm design include creating an efficient

algorithm to solve a problem in an efficient way using minimum time and space.

To solve a problem, different approaches can be followed. Some of them can

be efficient with respect to time consumption, whereas other approaches may be
memory efficient. However, one has to keep in mind that both time consumption and
memory usage cannot be optimized simultaneously. If we require an algorithm to run
in lesser time, we have to invest in more memory and if we require an algorithm to run
with lesser memory, we need to have more time.

Problem Development Steps

The following steps are involved in solving computational problems.

• Problem definition
• Development of a model

• Specification of an Algorithm

• Designing an Algorithm

• Checking the correctness of an Algorithm

Downloaded by Jaylien Rose Galamay Esteban

CSC307/Complexity and Algorithm
Introduction to Design and Analysis of
Algorithm
• Analysis of an Algorithm

• Implementation of an Algorithm

• Program testing

• Documentation

Characteristics of Algorithms

The main characteristics of algorithms are as follows −

• Algorithms must have a unique name

• Algorithms should have explicitly defined set of inputs and outputs

• Algorithms are well-ordered with unambiguous operations

• Algorithms halt in a finite amount of time. Algorithms should not run for infinity,
i.e., an algorithm must end at some point

Pseudocode

Pseudocode gives a high-level description of an algorithm without the

ambiguity associated with plain text but also without the need to know the syntax of a
particular programming language.

The running time can be estimated in a more general manner by using

Pseudocode to represent the algorithm as a set of fundamental operations that can
then be counted.

The Main Constructs of Pseudocode

The core of pseudocode is the ability to represent 6 programming constructs
(always written in uppercase): SEQUENCE, CASE, WHILE, REPEAT-UNTIL, FOR, and IF-
THEN-ELSE. These constructs — also called keywords —are used to describe the control
flow of the algorithm.

1. SEQUENCE represents linear tasks sequentially performed one after the

other. Input. READ, OBTAIN, GET
Output. PRINT, DISPLAY, SHOW
Compute. COMPUTE, CALCULATE, DETERMINE
Initialize. SET, INIT
Add. INCREMENT, BUMP Sub.
DECREMENT
2. WHILE a loop with a condition at its beginning.
WHILE condition
sequence
ENDWHILE

Downloaded by Jaylien Rose Galamay Esteban

CSC307/Complexity and Algorithm
Introduction to Design and Analysis of
Algorithm

3. REPEAT-UNTIL a loop with a condition at the

bottom. REPEAT
sequence
UNTIL condition

4. FOR another way of

looping. FOR iteration
bounds sequence
ENDFOR

5. IF-THEN-ELSE a conditional statement changing the flow of the algorithm.

IF condition THEN
sequence 1
ELSE
sequence 2
ENDIF

6. CASE the generalization form of IF-THEN-ELSE.

CASE expression OF
condition 1: sequence
1
condition 2: sequence 2
condition N: sequence
N OTHERS:
default sequence
ENDCASE
Although these 6 constructs are the most often used ones, you can
theoretically use them to implement any algorithm. You might find yourself needing
some more based on your specific application. Perhaps the two most needed
commands are:
1. Invoking classes or calling functions (using the CALL
keyword). CALL AvgAge with StudentAges
CALL Swap with CurrentItem and TargetItem
CALL getBalance RETURNING aBalance
CALL SquareRoot with orbitHeight RETURNING nominalOrbit

2. Handling exceptions (using EXCEPTION, WHEN

keywords). BEGIN
statements
EXCEPTION
WHEN exception
Statements to handle the
exception WHEN another exception
Statements to handle to exception
END

Downloaded by Jaylien Rose Galamay Esteban

CSC307/Complexity and Algorithm
Introduction to Design and Analysis of
Algorithm
Rules of Writing Pseudocode
When writing pseudocode, everyone often has their own style of presenting
things out since it’s read by humans and not by a computer; its rules are less rigorous
than that of a programming language. However, there are some simple rules that help
make pseudocode more universally understood.

1. Always capitalize the initial word (often one of the main 6 constructs).
2. Have only one statement per line.
3. Indent to show hierarchy, improve readability, and show nested constructs.
4. Always end multiline sections using any of the END keywords (ENDIF, ENDWHILE, etc.).
5. Keep your statements programming language independent.
6. Use the naming domain of the problem, not that of the implementation.
E.g., “Append the last name to the first name” instead of “name = first+ last.”
7. Keep it simple, concise, and readable.

Following these rules help you generate readable pseudocode and be able to
recognize a not well-written one.

Difference between Algorithm and Pseudocode

An algorithm is a formal definition with some specific characteristics that
describes a process, which could be executed by a Turing-complete computer machine
to perform a specific task. Generally, the word "algorithm" can be used to describe any
high level task in computer science.

On the other hand, pseudocode is an informal and (often rudimentary) human

readable description of an algorithm leaving many granular details of it. Writing a
pseudocode has no restriction of styles and its only objective is to describe the high-
level steps of algorithm in a much realistic manner in natural language.

For example, following is an algorithm for finding area of a rectangle.

Algorithm: Finding area of rectangle

Step 1: Start
Step 2: get l,b values
Step 3: Calculate
A=l*b Step 4: Display
A
Step 5: Stop

Here is a pseudocode that describes how the high-level abstract process

mentioned above in the algorithm finding area of rectangle could be described in a
more realistic way.

BEGIN

Downloaded by Jaylien Rose Galamay Esteban

CSC307/Complexity and Algorithm
Introduction to Design and Analysis of
Algorithm
READ l,b
CALCULATE A=l*b
DISPLAY A
END

In this module, algorithms will be presented in the form of pseudocode that is

similar in many respects different programming languages.

Another example is an algorithm to check greatest of two numbers.

Algorithm: To check greatest of two numbers

Step 1: Start
Step 2: get a,b value
Step 3: check if(a>b) print a is greater
Step 4: else b is greater
Step 5: Stop

Here is a pseudocode to check greatest of two numbers.

BEGIN
READ a,b
IF (a>b) THEN
DISPLAY a is greater
ELSE
DISPLAY b is greater
END IF
END

REFERENCES AND SUPPLEMENTARY MATERIALS

Books and Journals (Should be published from 2015 onwards only)

Online Supplementary Reading Materials

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithm
s_introduction.htm

https://www.brainkart.com/article/Examples-algorithms--pseudo-code,-flow-chart,-programming-
language_35900/

Downloaded by Jaylien Rose Galamay Esteban

CSC307/Complexity and Algorithm
Introduction to Design and Analysis of
Algorithm
https://towardsdatascience.com/pseudocode-101-an-introduction-to-writing-good-pseudocode-
1331cb855be7

Online Instructional Videos

Downloaded by Jaylien Rose Galamay Esteban