Placement Readiness

Training
 Data Structures using Python

2
Introduction to Data Structures
 Introduction to Data Structures

Relationship between Algorithm, Data Structure, and Program

Can you explain the relationship

between Algorithm, Data
Structures, and Program?

4 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Relationship between Algorithm, Data Structure, and Program

• Program = Algorithm + Data Structure

• A computer is a tool that can be used to implement a plan for solving a problem.

• A computer program is a set of instructions for a computer. These instructions describe the steps that

the computer must follow to implement a plan.

• An algorithm is a plan for solving a problem.

• A person must design an algorithm.

• A person must translate an algorithm into a computer program.

5 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Algorithm – Recap

• An algorithm is a finite set of instructions that accomplishes a particular task.

• In other words, an algorithm is a well-defined computational procedure in order to accomplishes a

particular task.

• It takes some value or a set of values as input and produces some value or a set of values as output.

Algorithm = Logic + Control

6 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Algorithm - Recap
Logic of the Problem

Algorithm = Logic + Control

Sequence Selection Looping

7 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

What is Data Structure?

• Data structure is a systematic way to organize data in computer memory so that it can be accessed

and used efficiently.

• In other words, Data Structure is the way of organizing, storing, and retrieving data and their relationship

with each other.

• There are several kinds of data structures like Array, stack, queue, linked list etc.

• Each of them are suitable for specific type of tasks.

8 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Classification
Data Structures

Primitive Non-Primitive

Integer Real Character Boolean

Built-in User-defined

List

Tuple Array Stack

Set Queue Graph

Dictionary Tree HashMap Linked

List
9 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0
 Introduction to Data Structures

Classification

Primitive data structure

• Primary Data Structures or Primitive Data Structures are the basic data structures that directly
operate upon the machine instructions.

• Example: Integer, Floating point numbers, Character constants, String constants, Pointers.

Non-primitive data structure

• Non primitive data structures or Secondary data structures are derived from one or more primitive
data structures.

• The objective of creating non-primitive data structures is to form sets of homogeneous or

heterogeneous data elements.

• It is categorized into two parts such as linear data structure and non-linear data structure.

10 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Classification

Linear data structure

• Linear data structure is a sequential type of data structure, and here sequential means that all the
elements in the memory are stored in a sequential manner;

• For example, element stored after the second element would be the third element, the element stored
after the third element would be the fourth element and so on.

• Linear data structures holding the sequential values such as Array, Linked list, Stack, Queue,
HashMap.

Ants go in line
11 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0
 Introduction to Data Structures

Classification

Non-linear data structure

• Non-linear data structure is a kind of random type of data structure.

• The non-linear data structures are Tree and Graph.

Tree Chess pieces move in random order

12 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Abstract Data Type (ADT)

• An abstract data type is an abstraction of a data structure that provides only the interface to which
the data structure must adhere.
• The interface does not give any specific details about something should be implemented or in what
programming language.
• The definition of ADT only mentions what operations are to be performed but not how these
operations will be implemented.
• It does not specify how data will be organized in memory and what algorithms will be used for
implementing the operations.
• It is called “abstract” because it gives an implementation-independent view.
• The process of providing only the essentials and hiding the details is known as abstraction.

13 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Abstract Data Type

• ADT is a collection of data together with a set of operations on that data.

ADT = Data + Operations

Definition :
Abstract Data type (ADT) is defined as a mathematical model with a collection
of operations defined on that model.

14 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Abstract Data Type

For example, If we consider the smart phone.
• We look at the high specifications of the smart phone, such as:
• 128 GB RAM, Snapdragon 8 generation processor
• 6.5 inch LCD screen, Dual camera, Android 11.0
• The above specifications of the smartphone are the data, and we can also perform the following
operations on the smartphone:

• call(): We can call through the smartphone.

• text(): We can text a message.

• photo(): We can click a photo.

• video(): We can also make a video.

• The smartphone is an entity whose data or specifications and operations are given above. They are
abstract and the implementation is hidden from user.
15 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0
 Introduction to Data Structures

Abstract Data Type

Simple ADTs
Integer ADT
• Predefined data types are Simple ADTs. ….. -3,-2,-1,0,1,2,3….

• Example: int, float, double, char, bool

• Consider Integer ADT: Integer ADT

Data
• This type of ADT is an integer with predefined ranges.
- Number
• Several operations that can be applied to this data type (addition, - Positive / Negative
subtraction, multiplication, division and so on) Operations
- Addition
- Subtraction
- Multiplication
- Division

16 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Abstract Data Type

Complex ADT:

• While several simple ADTs have been implemented, such as integer, real, character, pointer and so

on, and are available for use in most languages, many useful complex ADTs are not.

• We need some additional ADTs that should be created and stored in the library of the computer to be

used.

• Example: List, Set, Graph, Stack, Queue, etc.,

17 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Designing of Algorithm

• In Computer Science, developing an algorithm is an art or skill.

• And we can have mastery on algorithm development process only when we follow certain steps.

• Before actual implementation of the program or problem, designing an algorithm is very important

step.

18 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Designing of Algorithm

What are the steps that need to be followed while designing an algorithm?

Step 1: Understand the problem

• Read the problem description carefully and ask questions for clarifying the doubts about the problem.

• To find out what are the necessary inputs for solving that problem.

• The input to the algorithm is called instance of the problem.

• To decide the range of inputs so that the boundary values of algorithm get fixed

• The algorithm should work correctly for all valid inputs.

• Identify the strength and weakness of existing algorithm to refine and improve.
19 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0
 Introduction to Data Structures

Designing of Algorithm

Step 2: Decision making on

• Capabilities of computational device

– Essential to have proper choice of a computational device which is space and time efficient.

– For Example the sequential and parallel algorithms are need different kinds of computational
devices.

• Choice for either exact or approximate problem solving method

• Choice of Data structures

– Data Structure and algorithm work together and these are interdependent. The choice of proper
data structure is required before designing the actual algorithm.

20 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Relationship between Algorithm, Data Structure, and Program

What is the relationship between Algorithm,

Data Structures, and Program?

The implementation of any program is possible with the help

of algorithm and data structure.

Program = Data Structures + Algorithm

21 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Designing of Algorithm

• Choice of Algorithm strategies

– It is a general approach by which many problems can be solved algorithmically

• Some of the algorithm strategies:-

– Brute force

– Divide – and – Conquer

– Greedy Techniques

– Dynamic Programming

– Back Tracking

– Branch and bound

– Etc.,

22 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Designing of Algorithm

Step 3: Specification of algorithm

– There are various ways by which we can specify an algorithm

➢Using natural language

➢Pseudo code

➢Flowchart

Step 4: Algorithmic verification

– It means checking correctness of an algorithm

– Normally check whether the algorithm gives correct output in finite amount of times for a valid set
of input

23 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Designing of Algorithm

Step 5: Analysis of algorithm

• While analyzing an algorithm we should consider following factors :-

– Time efficiency of an algorithm: It means the amount of time taken by an algorithm to run. By

computing time complexity we come to know whether the algorithm is slow or fast.

– Space efficiency of an algorithm: It means the amount of space (memory ) taken by an algorithm.

By computing space complexity we can analyze whether an algorithm requires more or less space.

Step 6: Implementation or coding of algorithm

• It is done by suitable programming languages like C++ and JAVA.

24 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Which Data Structure and Algorithm is better?

How to decide which Data Structure

and Algorithm is better?

• Must meet requirements

• High Performance

• Low RAM footprint

• Easy to implement

25 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Quiz

1) Which of the following best describes a data structure?

a) A method for analyzing algorithms

b) A systematic way to organize, store, and

retrieve data in computer memory efficiently

c) A technique for debugging code

d) A programming paradigm focused on object-

oriented design

Answer : b)

26 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Quiz

2) When analyzing an algorithm, which two factors are

primarily considered to determine its efficiency?

a) Code readability and documentation

b) Input size and output size

c) Time efficiency and space efficiency

d) Compilation time and execution time

Answer : c)

27 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Quiz

3) Which statement describes an ADT?

a) An ADT specifies how data will be organized in

memory and the algorithms used for operations

b) An ADT defines only the operations to be performed,

without specifying how they will be implemented or in
which programming language

c) An ADT is a specific data structure implementation in

a particular programming language.

d) An ADT includes both the interface and the detailed

implementation of data operations.

Answer : b)
28 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0
 Introduction to Data Structures

Quiz

4) Which data structure is categorized as a non-linear data

structure?

a) Array

b) Linked List

c) Tree

d) Queue

Answer : c)

29 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Introduction to Data Structures

Quiz

5) Non-primitive data structures are derived from:

a) Machine instructions

b) Compiler optimizations

c) Operating system commands

d) Primitive data structures

Answer : d)

30 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0

 Success is nothing more
than a few straightforward
disciplines put into daily
practice.
31 Introduction to Data Structures | © SmartCliff | Internal | Version 1.0
THANK YOU