DATA STRUCTURES

AND ALGORITHMS

DSA Introduction

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use

Lesson Objectives
§ Understand the basics of Data Structures and Algorithms?

§ Understand What is Pseudocode?

§ Able to use Pseudocode to write basic algorithms.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 2

Table Content
§ Algorithms

§ Pseudo code

§ Data Structures

§ Algorithm Complexity

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 3

Section 1

ALGORITHM BASICS

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 4

What is an algorithm?
Algorithm:

“A finite list of instructions, most often used in solving problems or

performing tasks”.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 5

A Real Life Algorithm
§ How to cook a new recipe?

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 6

A Real Life Algorithm

It’s a finite list of instructions used to perform a task.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 7

A Computer Program Algorithm
§ Write an algorithm to “Find the largest number among three numbers”?

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 8

Characteristics of an Algorithm
• Clear and Unambiguous: Algorithm should be clear and
unambiguous. Each of its steps should be clear in all aspects and must
lead to only one meaning.

• Well-Defined Inputs: An algorithm should have 0 or more well-defined

inputs..

• Well-Defined Outputs: An algorithm should have 1 or more well-

defined outputs, and should match the desired output.

• Finite-ness: Algorithms must terminate after a finite number of steps.

• Feasible: Should be feasible with the available resources.

• Language Independent: The Algorithm designed must be language-

independent, i.e. it must be just plain instructions that can be
implemented in any language, and yet the output will be same, as
expected.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 9

Characteristics of an Algorithm
§ In order to write an algorithm, the following things are needed as a
pre-requisite:
ü The problem that is to be solved by this algorithm.

ü The constraints of the problem that must be considered while solving the problem.

ü The input to be taken to solve the problem.

ü The output to be expected when the problem is solved.

ü The solution to this problem, in the given constraints.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 10

Example 1
§ Consider the example to add three numbers and print the sum:
ü Step 1: Fulfilling the pre-requisites
• The problem that is to be solved by this algorithm: Add 3 numbers and print their sum.

• The constraints of the problem that must be considered while solving the problem:
The numbers must contain only digits and no other characters.

• The input to be taken to solve the problem: The three numbers to be added.

• The output to be expected when the problem is solved: The sum of the three numbers
taken as the input.

• The solution to this problem, in the given constraints: The solution consists of adding
the 3 numbers. It can be done with the help of the ‘+’ operator, bit-wise, or any other
method.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 11

Example 1
§ Consider the example to add three numbers and print the sum:
ü Step 2: Designing the algorithm
• START
• Declare 3 integer variables num1, num2, and num3.

• Take the three numbers, to be added, as inputs in variables num1, num2, and num3 respectively.

• Declare an integer variable sum to store the resultant sum of the 3 numbers.

• Add the 3 numbers and store the result in the variable sum.

• Print the value of a variable sum

• END

ü Step 3: Testing the algorithm by implementing it.

In order to test the algorithm, let’s implement it in C language.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 12

Advantages and Disadvantges of Algorithms
§ Advantages of Algorithms:
ü It is easy to understand.
ü Algorithm is a step-wise representation of a solution to a given problem.
ü In Algorithm the problem is broken down into smaller pieces or steps hence, it is
easier for the programmer to convert it into an actual program.

§ Disadvantages of Algorithms:
ü Writing an algorithm takes a long time so it is time-consuming.
ü Branching and Looping statements are difficult to show in Algorithms.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 13

Example 2
§ Algorithm: Add two numbers entered by the user

Step 1: Start
Step 2: Declare variables num1, num2, and sum.
Step 3: Read values num1 and num2.
Step 4: Add num1 and num2 and assign the result to sum.
sum←num1+num2
Step 5: Display sum
Step 6: Stop

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 14

Example 3
§ Algorithm: Find the largest number among three numbers
Step 1:
Start
Step 2:
Declare variables a,b and c.
Step 3:
Read variables a,b and c.
Step 4:
If a > b
If a > c
Display a is the largest number.
Else
Display c is the largest number.
Else
If b > c
Display b is the largest number.
Else
Display c is the greatest number.
Step 5: Stop

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 15

Section 2

PSEUDO CODE

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 16

Introduction to Pseudo Code
An algorithm is merely the sequence of steps taken to solve a problem. The steps are
normally "sequence," "selection, " "iteration," and a case-type statement.

Pseudocode is an artificial and informal language that helps

programmers develop algorithms. Pseudocode is a "text-based"
detail (algorithmic) design tool.

§ Algorithms are represented with the help of pseudo codes as they can be interpreted
by programmers no matter what their programming background or knowledge is.
§ Pseudo code, as the name suggests, is a false code or a representation of code
which can be understood by even a layman with some school level programming
knowledge.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 17

Algorithm and Pseudo Code
§ Algorithm:
ü It’s an organized logical sequence of the actions or the approach towards a particular problem.

ü A programmer implements an algorithm to solve a problem. Algorithms are expressed using natural verbal
but somewhat technical annotations.

§ Pseudo code:
ü It’s simply an implementation of an algorithm in the form of annotations (include while, do, for, if, switch)
and informative text written in plain English.

ü It has no syntax like any of the programming languages and thus can’t be compiled or interpreted by the
computer.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 18

Example 3
§ Algorithm: Find Root of the quadratic equation ax2 + bx + c = 0

Step 1: Start
Step 2: Declare variables a, b, c, D, x1, x2, rp and ip;
Step 3: Calculate discriminant
D ← b2-4ac
Step 4: If D ≥ 0
r1 ← (-b+√D)/2a
r2 ← (-b-√D)/2a
Display r1 and r2 as roots.
Else
Calculate real part and imaginary part
rp ← -b/2a
ip ← √(-D)/2a
Display rp+j(ip) and rp-j(ip) as roots
Step 5: Stop

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 19

Advantages of Pseudo Code
§ Improves the readability of any approach: It’s one of the best
approaches to start the implementation of an algorithm.

§ Acts as a bridge between the program and the algorithm or flowchart.

èAlso works as rough documentation, so the program of one developer can be understood easily when a
pseudo code is written out.

èIn industries, the approach of documentation is essential. And that’s where a pseudo-code proves vital.

§ The main goal of a pseudo-code is to explain what exactly each line

of a program should do, hence making the code construction phase
easier for the programmer.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 20

Disadvantages of Pseudo Code
§ Pseudocode does not provide a visual representation of the logic of
programming.

§ There are no proper format for writing the for pseudocode.

§ In Pseudocode their is extra need of maintain documentation.

§ In Pseudocode their is no proper standard very company follow their own

standard for writing the pseudocode.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 21

How to write a Pseudo-code?
1. Arrange the sequence of tasks and write the pseudocode accordingly.

2. Start with the statement of a pseudo-code which establishes the main

goal or the aim.
This program will allow the user to check
• Example: the number whether it's even or odd.

The way the if-else, for, while loops are indented in a program, indent the statements
likewise, as it helps to comprehend the decision control and execution mechanism.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 22

How to write a Pseudo-code?
§ They also improve the readability to a great extent.

if "1"
print response
"I am case 1"

if "2"
print response
"I am case 2"

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 23

How to write a Pseudo-code?
§ Use appropriate naming conventions.
§ Use appropriate sentence casings: such as camelCase for methods, upper case for
constants, and lower case for variables.
§ Don’t make the pseudo code abstract: Elaborate everything which is going to happen in the
actual code.
§ Use standard programming structures such as ‘if-then’, ‘for’, ‘while’, ‘cases’ the way we
use them in programming.
§ Check whether all the sections of a pseudo code is complete, finite, and clear to
understand and comprehend.
§ Don’t write the pseudo-code in a complete programmatic manner: It is necessary to be
simple to understand even for a layman or client, hence don’t incorporate too many technical
terms.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 24

Pseudo Code Examples
• 1. // Check student’s grade

• If student's grade is greater than or equal to 60

• Print "passed"

• else

• Print "failed"

2. // Calculate the average of ten students

Set total to zero
Set grade counter to one
While grade counter is less than or equal to ten
Input the next grade
Add the grade to the total
Set the class average to the total divided by ten
Print the class average.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 25

Pseudo Code Examples
§ Algorithm: Class average program with sentinel controlled repetition.
Initialize total to zero
Initialize counter to zero
Input the first grade
while the user has not as yet entered the sentinel
add this grade into the running total
add one to the grade counter
input the next grade (possibly the sentinel)
if the counter is not equal to zero
set the average to the total divided by the
counter
print the average
else
print 'no grades were entered'

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 26

Pseudo Code Examples
§ Algorithm: Find the factorial of a number

Step 1: Start
Step 2: Declare variables n, factorial and i.
Step 3: Initialize variables
factorial ← 1
i ← 1
Step 4: Read value of n
Step 5: Repeat the steps until i = n
5.1: factorial ← factorial*i
5.2: i ← i+1
Step 6: Display factorial
Step 7: Stop

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 27

Pseudo Code Examples
§ Algorithm: Check whether a number is prime or not

Step 1: Start
Step 2: Declare variables n, i, flag.
Step 3: Initialize variables
flag ← 1
i ← 2
Step 4: Read n from the user.
Step 5: Repeat the steps until i=(n/2)
5.1 If remainder of n÷i equals 0
flag ← 0
Go to step 6
5.2 i ← i+1
Step 6: If flag = 0
Display n is not prime
else
Display n is prime
Step 7: Stop

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 28

Some Keywords That Should be Used
§ The keywords that are to be used include: Do While...EndDo; Do Until...Enddo;
Case...EndCase; If...Endif; Call ... with (parameters); Call; Return ....; Return;
When; Always use scope terminators for loops and iteration.

§ As verbs, use the words Generate, Compute, Process, etc.

§ Words such as set, reset, increment, compute, calculate, add, sum, multiply,
... print, display, input, output, edit, test , etc. with careful indentation tend to
foster desirable pseudocode.

§ Do not include data declarations in your pseudocode

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 29

Section 3

DATA STRUCTURES

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 30

Introduction to Data Structures
§ Data Structure is a way of collecting and organizing data in such a way that we can perform operations on
these data in an effective way.

§ Data Structures are about rendering data elements in terms of some relationship, for better organization and
storage.
ü For example, we have some data which has, the player's name "Virat" and age 26. Here "Virat" is of String data type and
26 is of integer data type.

ü We can organize this data as a record like Player record/class, which will have both player's name and age in it. Now we
can collect and store player's records in a file or database as a data structure. For example: "Dhoni" 30, "Gambhir" 31,
"Sehwag" 33

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 31

Basic types of Data Structures
§ Primitive Data Structures: anything that can store data can be called as
a data structure, hence Integer, Float, Boolean, Char etc.

§ Abstract Data Structure: Linked List, Tree, Graph, Stack, Queue etc.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 32

Data Structure Characteristics
§ The data structures can also be classified on the basis of the following characteristics:

Characterstic Description

Linear In Linear data structures, the data items are arranged in a linear sequence. Example: Array

Non-Linear In Non-Linear data structures, the data items are not in sequence. Example: Tree, Graph

Homogeneous In homogeneous data structures, all the elements are of same type. Example: Array

Non-Homogeneous In Non-Homogeneous data structure, the elements may or may not be of the same type. Example: Structures

Static Static data structures are those whose sizes and structures associated memory locations are fixed, at compile time.
Example: Array

Dynamic Dynamic structures are those which expands or shrinks depending upon the program need and its execution. Also, their
associated memory locations changes. Example: Linked List created using pointers

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 33

Section 4

ALGORITHM COMPLEXITY

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 34

Algorithm Analysis
§ Efficiency of an algorithm can be analyzed at two different stages,
before implementation and after implementation.
§ They are the following:
ü A Priori Analysis − This is a theoretical analysis of an algorithm.
• Efficiency of an algorithm is measured by assuming that all other factors, for example,
processor speed, are constant and have no effect on the implementation.

ü A Posterior Analysis − This is an empirical analysis of an algorithm.

• The selected algorithm is implemented using programming language. This is then
executed on target computer machine. In this analysis, actual statistics like running time
and space required, are collected.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 35

Algorithm Complexity
§ Suppose X is an algorithm and n is the size of input data, the time and space
used by the algorithm X are the two main factors, which decide the efficiency of
X.

ü Time Factor − Time is measured by counting the number of key operations such as
comparisons in the sorting algorithm.

ü Space Factor − Space is measured by counting the maximum memory space required by
the algorithm.

§ The complexity of an algorithm f(n) gives the running time and/or the storage
space required by the algorithm in terms of n as the size of input data.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 36

Space Complexity
§ Space complexity of an algorithm represents the amount of memory space required by the
algorithm in its life cycle. The space required by an algorithm is equal to the sum of the following
two components

ü A fixed part that is a space required to store certain data and variables, that are independent of the size
of the problem. For example, simple variables and constants used, program size, etc.

ü A variable part is a space required by variables, whose size depends on the size of the problem. For
example, dynamic memory allocation, recursion stack space, etc.

§ Space complexity S(P) of any algorithm P is S(P) = C + SP(I),

ü where C is the fixed part and

ü S(I) is the variable part of the algorithm, which depends on instance characteristic I.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 37

Space Complexity
§ Example:

Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop

ü Here we have three variables A, B, and C and one constant.

ü Hence S(P) = 1 + 3. Now, space depends on data types of given variables and
constant types and it will be multiplied accordingly.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 38

Time Complexity
§ Time complexity of an algorithm represents the amount of time required by the
algorithm to run to completion.

ü Time requirements can be defined as a numerical function T(n), where T(n) can be
measured as the number of steps, provided each step consumes constant time.

§ Example:

ü addition of two n-bit integers takes n steps.

ü Consequently, the total computational time is T(n) = c ∗ n,

• where c is the time taken for the addition of two bits.

ü Here, we observe that T(n) grows linearly as the input size increases.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 39

Algorithm complexity
§ Algorithm complexity is commonly represented with the O(f) notation,
also known as asymptotic notation or “Big O notation”, where f is the
function of the size of the input data.

§ The asymptotic computational complexity O(f) measures the order of the

consumed resources (CPU time, memory, etc.) by certain algorithm
expressed as function of the input data size.

§ We will explore the Big-O concept in the next session.

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 40

Summary
§ Algorithms

§ Pseudo code

§ Data Structures

§ Algorithm Complexity

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 41

Q&A
09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Academy - Internal Use 42
THANK YOU!

09e-BM/DT/FSOFT - @FPT SOFTWARE - FPT Software Acadademy - Internal Use