ALGORITHMS

NINAN O. D.
• Algorithms are a set of well-defined rules/instructions used to solve a specific
problem.
• Each algorithm is unique in the way it tackles a problem, taking into account
factors like the problem size, resources, and efficiency, among others.

Role of Algorithms in Computer Science

• Algorithms help to reduce the complexity of a problem by breaking it down
into smaller, manageable sub-problems.
• They are essential for data processing and ensuring efficient memory usage.
• They ensue the security and protection of data, especially in areas like
cryptography.
• Algorithms are vital in data search for large databases.
 Data structures
• Data structures are a way of organising data in a computer so that it can be
used efficiently.
• An algorithm is a step-by-step procedure designed to perform specific
operations.
• As a pair, data structures and algorithms are a fundamental aspect of
computer science, facilitating efficient problem-solving strategies.
• .Algorithms utilise data structures to solve computational problems,
• Choosing the right data structure can mean the difference between a solution
and an optimal solution.
• A well-chosen data structure can improve an algorithm's efficiency
dramatically.
 Searching Algorithms
• searching algorithms are designed to find a particular item in a data
structure.
• Searching algorithms are designed to retrieve information stored within a
data structure, such as an array or a graph.
• The choice of searching algorithm often depends on the structure of your
data and the nature of the query.
• This algorithm returns the position if the element is found; otherwise, it
returns -1 or NULL.
• There are primarily two types of searching algorithms:
- Sequential Search (or Linear Search) and
- Interval Search (or Binary Search).
• Linear Search: A simple approach, this algorithm starts at the beginning of a
list and checks every element until it finds the one it's looking for.
• Binary Search: Only applicable to a sorted list or array, this algorithm divides
the list into two halves and determines if the desired value is in the first half
or second half. It continues halving until it locates the item.
• Binary Search requires the list to be sorted, while Linear Search does not.
• Euclidean Algorithm: Used for finding the greatest common divisor (GCD) of
two numbers.
• Sorting Algorithms
• sorting algorithms arrange elements in a specific order within a data
structure.
• sorting algorithms reorganise data in a particular format, often ordering the
elements in ascending or descending order.
• The most suitable sorting algorithm depends on a mixture of elements, the
structure of the data, and the system's memory.
• A Sorting Algorithm is a method that rearranges elements in a list according
to a certain order such as numerical or lexicographic.
• Sorting algorithms are categorised as either
- comparison-based (such as Bubble Sort, Quick Sort, and Merge Sort) or
- non-comparison based (like Counting Sort or Radix Sort).
• Bubble Sort: Repeatedly steps through the list, compares adjacent elements,
and swaps them if they are in the wrong order.
• Quick Sort: Divides the list based on a pivot element and sorts two
reduced arrays independently.
• Merge Sort: Divides the list into equal halves, sorts them, and then merges
them.
• Counting Sort: Assumes that the input elements are an integer array within a
specific range and counts the occurrence of each number.
• Radix Sort: Performs digit-by-digit sort starting from least significant digit to
most significant digit.
• Hash Sort: uses a Hash function (a search-optimised function) to distribute
elements across an array based on their key values. This method of sorting
allows for quickly locating elements during a search due to the uniform
distribution of data.
 Applications of Algorithms
• Digital Maps and Route Planning: e.g. Dijkstra’s algorithm which finds the
shortest path between two points on a graph.
• Search Engines: Search engines like Google use complex algorithms to
deliver the most relevant results for queries.
• PageRank, for example, is an algorithm used by Google Search to rank
websites in its search engine results.
• Online Shopping and Recommendations - recommendation algorithms.
• Medical Imaging: In the healthcare industry, image processing algorithms
help analyse and interpret medical images like X-rays, MRIs, or CT scans.
• cryptography, weather prediction, airline reservations, social networking
etc .
• INTRODUCTION TO PROBLEM SOLVING

• An algorithm is a sequence of simple steps that can be followed to solve a

problem.
• These steps must be organized in a logical, and clear manner.
• Algorithms are designed using three basic methods of control: sequence,
selection, and repetition.
• Sequential control.
• Sequential Control means that the steps of an algorithm are carried out in a
sequential manner where each step is executed exactly once.
• Sequential execution of code statements (one line after another) -- like
following a recipe
• Let’s look at the following problem:
• We need to obtain the temperature expressed in Farenheit degrees and
convert it to degrees Celcius.
• An algorithm to solve this problem would be:
1. Read temperature in Farenheit
2. Apply conversion formula
3. Display result in degrees Celcius
• In this example, the algorithm consists of three steps.
• Also, note that the description of the algorithm is done using pseudocode.
• A pseudocode is a mixture of English (or any other human language), symbols,
and selected features commonly used in programming languages.
• Here is the above algorithm written in pseudocode:

READ degrees_Farenheit
degrees_Celcius = (5/9)*(degrees_Farenheit - 32)
DISPLAY degrees_Celcius

• Another option for describing an algorithm is to use a graphical representation

in addition to, or in place of pseudocode.
• The most common graphical representation of an algorithm is the flowchart.
• Example : Write an algorithm to calculate the area of a rectangle
• Algorithm:
Step 1: Start
Step 2: Input length and breadth
Step 3: area = length * breadth
Step 4: print area
Step 5: stop

Ex. Draw the flowchart for the algorithms.

• Selection control.
• In Selection Control only one of a number of alternative steps is executed. In
data processing, it is often required to select one of the two different
alternatives depending on the prevailing condition.
• To select, a test is made of a condition that can either be true or false.
• If the condition is true, then one path is followed; and if it is false then the
other path is followed.
• The following algorithm and flowchart do illustrate the selection component.
if the condition is true
then follow step A
else follow step B
end if
• Flowchart

• Example 1. This is an algorithm that decides whether a student should receive

a distinction.

READ grade
IF (grade >= 95)
THEN student receives a distinction
• This is the simplest case of selection control. In fact, in essence it is a
sequential form but the second step is only taken when the condition
contained in the brackets is true, that is the last step (starting at THEN) is
selected for execution only when the condition is satisfied.
• Example 2. Control access to a computer depending on whether the user has
supplied a username and password that are contained in the system
database.
IF (username in database AND password corresponds to user)
THEN Accept user
ELSE
Deny user

• In this case, there is also a decision to be made but a more complex one. In
the condition is true only the Accept user step is executed and if the condition
is false only the Deny user step is executed.
• That is, the condition helps us make a selection which controls which of the
two steps will be executed.
• Now look more closely to the condition. Does it guarantees that the user is
valid? What if we had this condition instead, which looks pretty similar: IF
(username in database AND password in database)?
• What would happen if somebody typed a valid username but the password
of a different but also valid user?
• Does this second condition satisfies our requirement that to access this
account one should be the right user and know the corresponding password?
• When you write a condition always make sure that it performs exactly the
check that you intended it to! It is very easy to translate words in
pseudocode that does a different thing than what was intended!
Example 3. Decide on a student’s grade based on their coursework mark.

READ result
CASE (result >=90)
PRINT ‘A’
CASE (result >=80)
PRINT ‘B’
CASE (result >=70)
PRINT ‘C’
CASE (result >=60)
PRINT ‘D’
CASE (result <60)
PRINT ‘F’
• In example 3, there are five conditions which are checked, one after the other.

• Question. What is the difference between examples 1, and 2, and 3?

• Answer. There are three differences:

• Example 1 provides no alternative action is the condition is not true.

• Example 2 provides an alternative action when the conditions are false.
• Example 3 provides multiple alternatives to select from.
• Repetition.

• In Repetition one or more steps are performed repeatedly.

• Another action often required in data processing is looping, i.e. Repeating the
same set of operations for two or more occurrences of data.

• Example: Design an algorithm to find the sum of all integers between 1 and
10,000 inclusive. Draw a flowchart to depict your algorithm.
• Algorithm
Step 1 Set sum = 0
Step 2 Set number = 0
Step 3 Set sum = sum + number
Step 4 Set number = number + 1
Step 5 If number < 10001 then go to step 3 else go to step 6
Step 6 Print sum
Step 7 Stop
• Flowchart
• Example 1. Compute the average of ten numbers:

total = 0
average = 0
FOR 1 to 10
Read number
total = total + number
ENDFOR
average = total / 10
• Example 2. Read numbers and add them up until their total value reaches (or
exceeds) a set value represented by S.

WHILE (total < S) DO

Read number
total = total + number
ENDDO

Question. What is the difference between Examples 1, and 2?

• Answer. The difference is that in Example 1 we know beforehand the exact
number of repetitions that will be carried out (they are 10), but in
• Example 2 we do not know beforehand (it depends on the particular
numbers that will be fed to our program during its execution).
• Sequence, selection, and repetition are by themselves simple.
• But put together, they can construct any algorithm that we can imagine.
• One can imagine a situation involving several decisions.
• This is illustrated in the example given below.
if condition 1 is true
then test condition 2
if condition 2 is true
then perform step A
otherwise perform step B
otherwise, perform step C
stop
• Flowchart

•
• The Concept of Algorithm
• One of the basic concepts of mathematics and computer science is algorithm.
• By an algorithm is meant a list of instructions specifying a sequence of
operations which will give the answer to any problem of a given type.
• In mathematics, a class of problems is considered solved when an algorithm
for solving them is found.
• The discovery of such algorithms is a natural aim of mathematics and
computer science.
• The concept of algorithm is very germane to the study of Computer Science.
• Computational problems are solvable only if there exist algorithms for solving
them.
• Characteristics of Algorithm
• It should be deterministic:
• An algorithm must be given in the form of a finite list of instructions
giving the exact procedure to be followed at each step of the calculation.
Thus the calculation does not depend on the calculator.; it is a deterministic
process which can be repeated successfully at any time and by anyone. So it
should not be ambiguous.

• . It should be general:
• An algorithm is a single list of instructions defining a calculation which
may be carried out on any initial data and which in each case gives the
correct result. In other words, an algorithm tells how to solve not just one
particular problem, but a whole class of similar problems.
• . It should be finite:
• Although the algorithm has definite length, its execution may repeat some
steps indefinitely that is, the computation may not terminate. In particular,
non-termination may occur for some input data. For example, an algorithm to
compute all the digits of the square root of x would terminate for x = 4, and
not terminate for x=3. To be accepted, an algorithm must terminate for all the
inputs.

• It should have one entry and exit: Multiple entries or exits may make the
algorithm ambiguous.
• It should act at least on one input and it should produce at least one output.
• DECISION TABLES
• A decision table, just like a flowchart is a tool of programming and systems
analysis. It can be used to define complex program logic.
Decision Table Format

• The table is divided into four major parts;

• The table is divided into four major parts;
I Condition Stub
II Condition entries
III Action Stub
IV Action entries.
• Apart from these, there is also a portion reserved for table heading and
another for decision rules.
• The condition stub will contain the conditions to be tested while the action
stub will contain actions to be taken after the examination of each rule.
• The rule itself is a combination of answers to the questions asked in the
conditions stub. If three conditions are entered in the condition stub, then
we will expect 8 rules i.e. 23.
• In general, if there are n conditions, there will be 2n rules.
• However, some of the rules may be irrelevant or redundant and hence such
rules are simply ignored. Realistically speaking then there will always be less
than or equal to 2n rules for n conditions.
• The condition entries are responses to the questions asked under the
conditions stub and they are usually answered as a “YES” or a “NO”.
• The action entries contain column by column, the action actually taken in
response to the rule in the column. X is put against each action taken in
response to a rule.
• ARRAY
• An array is a set of data items all of the same type and stored together in the
memory.
• All the data in an array can therefore be referred to, by a single identifier. The
number of data items in any array is fixed.
• Each array element can be referenced by use of a subscripted variable. An
array can be one-dimensional or multi-dimensional.
• A classic mathematical notation provides the way for naming both an array
and its individual elements.
• The identifier or variable ITEM, for instance can stand for the array of items in
a warehouse while
• ITEM(1), ITEM (2), ITEM (3), .....
• represent the first, second, third and other individual items in that array.
• ITEM(1), ITEM (2), ITEM (3), .....
• represent the first, second, third and other individual items in that array.
ITEM

• This is a linear array ITEM

• A two-dimensional array however is made up of rows and columns of data.

• A two-dimensional array of four rows and three columns can be depicted as
shown below
TABLE

A 2-dimensional array TABLE

• A multi-dimensional array is specified by giving more than a pair of

dimensional limits in the description of the array.
• Exercises

1. Write an algorithm to sort 10 numbers in increasing order

2. given a positive integer, write and algorithm to determine that it is a
prime number?