Intro to DSA

Introduction to DSA
Sandeep G
Who Am I?
- Engineer / Front End developer

- Worked in Software AG, MSFT, SAP
- 9+ years of experience
- Worked in React JS, TypeScript, JS, CSS, HTML
- Built E-commerce platforms, ERP systems, Enterprise websites.
Agenda
● What is an Algorithm?
● Data Structures and Types
● Why Learn Data Structures and Algorithms?
● Asymptotic Analysis
What is an Algorithm?
What is an Algorithm?
● It is defined as a set of well defined instructions to solve a particular problem.
E.g. - Algo to add 2 numbers -

1. Take two number inputs
2. Add numbers using the + operator
3. Display the result
Qualities of Good Algorithm
● Well defined inputs and output

● Each step should be clear and precise
● It should be most efficient among all the other alternate solutions
● It should not include code, It should be generic enough to be used in any language.
Data Structures and
Types
Data Structure
● It is a storage that is used to store and organise data.

● It is a way of arranging data on a computer, so that it can be accessed and updated
efficiently.
● It is important to choose the right data structure for your project.
E.g. If you want to store data sequentially in the memory, then use Array data
structure.
Types of Data Structure
Linear data structure - The elements are arranged in sequence

one after another.
Non linear data structure - They do not store data in a sequential

manner, instead they store in hierarchical manner.
Popular Linear Data Structure
● Array - Elements are arranged in continuous memory. All the

elements are of similar type(except JS). We usually have to
declare the type of elements in the Array.
● Stack - Elements are store in the LIFO principle, as in the last Fig: Stack
element stored will be the first one to be removed. E.g. Stack of
plates.
● Queue - Elements are stored in the FIFO principle, as in the first
element to be stored in the queue, will be removed first. E.g.
people in queue of tickets.
● Linked List - Data elements are connected through a series of
Fig: Queue
nodes each nodes contains the data item and address of next
node. Node Fig: Linked List
Non Linear Data structure
Elements in non-linear data structures are not in any sequence. Instead they are arranged
in a hierarchical manner where one element will be connected to one or more elements.
They are divided in to following types -

1. Graph data structure
2. Trees data structure
Graph Data Structure Node Vertex
In graph data structure, each node is called vertex and each vertex is
connected to other vertices through edges.
Edges
Tree Data structures
Similar to a graph, a tree is also a collection of vertices and edges. However, in tree data
structure, there can only be one edge between two vertices.
Linear vs Non-linear Data Structures
Linear Data Structures Non-linear data structures
Elements arranged in sequential manner Elements arranged in hierarchical manner
Data items represented in single layer Data items represented in different layer
Can be traversed in single run. I.e. if we It may require multiple runs. I.e. if we start
start from start, we can go to end in a from one end, we might not reach till end in
sequential manner. one go.
Complexity to access elements, increases Complexity remains the same.

with increase in elements
Break
Why DS is important
Why to read Data Structure
Knowledge of data structure is important, as it would help you to write

memory and time efficient code.
E.g. you need to store students library card, you may store it in various ways -
1. Alphabetical order - sequential order
2. Based on department - hierarchical order
3. Based on type of book - hierarchical order
Now, if you know these different orders by which you can store, you will be
able to choose the best way to store these library cards. Such, that you are
able to access these cards fastest.
Find the factorial of ‘n’
Important resources in coding
● Time and memory is 2 of the important resources in programming.
● Time - It is the total time a computer takes to execute a program. If a computer

takes too much time, you have to wait forever to get the response.
● Memory - It is the total memory consumed by computer in order to execute a

program. If a computer takes too much memory, it will lead to crashing of OS.
Space Complexity
● Space complexity is the amount of memory that is required to run an algorithm or process.
● Constant Space Complexity -
● Linear Space Complexity -

Time Complexity
Time complexity is the time taken by the algorithm to execute each set of instructions
● Constant Time Complexity - Access array element

● Linear Time Complexity - Linear Search in Array
How approach decides time for execution
Time to run code = no. of instructions * time to execute each instruction (constant for
every computer).
* Instruction is defined as the operation or calculation, computer does in each step.
E.g. Write a program to calculate sum of ‘n’ numbers

Approach 1: Approach 2:
Traverse 1….n and find sum on the go Use the formula for sum of n numbers -
n(n+1)/2
Problem - Number of calculations will
increase with every number. Why Awesome -
The number of calculation remains
E.g. - for n = 10; There are 10 operations. constant. For n = 10 or n = 10000;
For n = 10000; There would be 10000 oper.
Scalable solution
Scalability refers to the ability of an organization (or a system, such as a computer

network) to perform well under an increased or expanding workload.
E.g. You wrote a program, that works well for smaller input. But, as the input increases
your performance of the program decreases.
Why considering memory is important
● Memory comes costly.

● If your program consumes too much memory, it would restrict other important program to
run smoothly. Just like in your OS.
○ Also, you need to pay extra
○ E.g. if you have written a function to sort(by name) products on Amazon, it consumes 10KB memory.
Suppose, tomorrow you were able to optimize it to consume only 2KB. That’s a saving of 8KB/request.
If we have 1 Million request/day, then that's a saving of 8TB/day.

Currently in AWS cost of 1TB/month - 23$.
So, you will be saving - $23*30 = 690$/month, just by improving your code.
Asymptotic Analysis
Asymptotic Analysis
The study of change in performance of the algorithm with the change in order of the input
size is defined as asymptotic analysis.
Our aim is to write the most efficient algorithm. Efficiency depends on the amount of time
and memory a program takes.
Asymptotic Notations - These are the mathematical notations used to describe the
running time of an algorithm when the input tends towards particular value.
Three Types of asymptotic notation -

1. Big-O notation - Worst case
2. Omega notation - Best case
3. Theta notation - Average case
Big O notation - Worst case
It is defined as the upper bound of running time of an algorithm. Also known as the
performance of the algorithm in the worst case.
Search 52 (worst case time)
Worst case -> 8 searches

=> O(8)
Omega notation - Best case
It is defined as the lower bound of running time of an algorithm. Also known as the
performance of the algorithm in the best case.
Best case -> 1 searches

Search 70 (best case time)
=> Ω(1)
Theta notation - Average case
It is defined as the lower bound of running time of an algorithm. Also known as the
performance of the algorithm in the average case.
Best case -> 1 searches

=> Θ(4) Search 57 (average case time)
Happy Coding!

Intro to DSA

Uploaded by

Copyright:

Available Formats

Intro to DSA

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Intro to DSA

Uploaded by

Copyright:

Available Formats

Introduction to DSA

- Engineer / Front End developer

● It is defined as a set of well defined instructions to solve a particular problem.

E.g. - Algo to add 2 numbers -

● Well defined inputs and output

● It is a storage that is used to store and organise data.

Linear data structure - The elements are arranged in sequence

Non linear data structure - They do not store data in a sequential

● Array - Elements are arranged in continuous memory. All the

They are divided in to following types -

Linear Data Structures Non-linear data structures

Elements arranged in sequential manner Elements arranged in hierarchical manner

Complexity to access elements, increases Complexity remains the same.

Knowledge of data structure is important, as it would help you to write

● Time and memory is 2 of the important resources in programming.

● Time - It is the total time a computer takes to execute a program. If a computer

● Memory - It is the total memory consumed by computer in order to execute a

● Linear Space Complexity -

● Constant Time Complexity - Access array element

E.g. Write a program to calculate sum of ‘n’ numbers

Scalability refers to the ability of an organization (or a system, such as a computer

● Memory comes costly.

If we have 1 Million request/day, then that's a saving of 8TB/day.

Three Types of asymptotic notation -

Worst case -> 8 searches

Best case -> 1 searches

Best case -> 1 searches

You might also like