DSA Self Placed

~GEEKSFORGEEKS

BY-
MOHAMMAD AMIR IDREESI
Reg No:11811970
OBJECTIVES

• To understand the concepts of

• Data structures
• Types of Data Structures
• Applications
• Algorithms
• ADTs
Topics
 Algorithms
 ADTs
 Properties of an Algorithm
 Data structures
 Types of Data structures
 Problem Solving Phase
 Stacks and Queues
What is Program?
 Programs consists of two things: Algorithms and data structures
 A Good Program is a combination of both algorithm and a data
structure
 An algorithm is a step by step recipe for solving an instance of
a problem
 A data structure represents the logical relationship that exists
between individual elements of data to carry out certain tasks
 A data structure defines a way of organizing all data items that
consider not only the elements stored but also stores the
relationship between the elements
Algorithms
 An algorithm is a step by step recipe for solving an instance of a
problem.
 Every single procedure that a computer performs is an algorithm.
 An algorithm is a precise procedure for solving a problem in finite
number of steps.
 An algorithm states the actions to be executed and the order in
which these actions are to be executed.
 An algorithm is a well ordered collection of clear and simple
instructions of definite and effectively computable operations
that when executed produces a result and stops executing at
some point in a finite amount of time rather than just going on
and on infinitely.
Time Complexity of an Algorithm

 Time Complexity of an algorithm is the amount of time(or

the number of steps) needed by a program to complete its
task (to execute a particular algorithm)
 The way in which the number of steps required by an
algorithm varies with the size of the problem it is solving.
The time taken for an algorithm is comprised of two times:
 Compilation Time
 Run Time
 Compilation time is the time taken to compile an
algorithm. While compiling it checks for the syntax and
semantic errors in the program and links it with the
standard libraries , your program has asked to.
Which Data Structure or Algorithm
is better?
 Must Meet Requirement
 High Performance
 Low RAM footprint
 Easy to implement
Time Complexity of an Algorithm

 Time complexity of a given algorithm can be defined for

computation of function f() as a total number of statements
that are executed for computing the value of f(n).
 Time complexity is a function dependent from the value of
 n. In practice it is often more convenient to consider it as a
function from |n|
 Time complexity of an algorithm is generally classified as three
types.
 Worst case
 Average Case
 Best Case
Time Complexity

 Worst Case: It is the longest time that an algorithm will use

over all instances of size n for a given problem to produce a
desired result.
 Average Case: It is the average time( or average space) that
the algorithm will use over all instances of size n for a given
problem to produce a desired result. It depends on the
probability distribution of instances of the problem.
 Best Case: It is the shortest time ( or least space ) that the
algorithm will use over all instances of size n for a given
problem to produce a desired result.
Space Complexity
 Space Complexity of a program is the amount of memory
consumed by the algorithm ( apart from input and output, if
required by specification) until it completes its execution.
 The way in which the amount of storage space required by an
algorithm varies with the size of the problem to be solved.
 The space occupied by the program is generally by the following:
 A fixed amount of memory occupied by the space for the program
code and space occupied by the variables used in the program.
 A variable amount of memory occupied by the component
variable whose size is dependent on the problem being solved.
This space increases or decreases depending upon whether the
program uses iterative or recursive procedures.
The Need for Data Structures
Data structures organize data
 more efficient programs.
More powerful computers  more complex applications.
More complex applications demand more calculations.
Complex computing tasks are unlike our everyday experience.
 More typically, a data structure is meant to be an organization for a collection of data
items.
 Any organization for a collection of records can be searched, processed
in any order, or modified.
 The choice of data structure and algorithm can make the difference between a
program running in a few seconds or many days. A data structure requires a certain
amount of:
 space for each data item it stores
 time to perform a single basic operation
 programming effort.
Classification of Data Structures
 “Data Structures ”deals with the study of how the data is organized
in the memory, how efficiently the data can be retrieved and
manipulated, and the possible ways in which different data items are
logically related.

Types:

1. Primitive Data Structure: Ex. int, float, char

2. Non-primitive Data Structures: Ex. Arrays ,Structures, stacks.
3. Linear Data Structures: Ex. Stacks, queues, linked list
4. Non-Linear Data Structures: Ex. Trees, Graphs
Stacks

 A Stack is defined as a special type of data structure where items

are inserted from one end called top of stack and items are
deleted from the same end.
 Stack is organized as a Last In First Out(LIFO) data structure.
 Operations performed on Stacks are:
 Insert an item into the stack (Push)
 Delete an item from the stack (Pop)
 Display the contents of the stack
Stack
 A stack is an ordered collection of items, generally implemented
with only two principle operations, called Push and Pop.
 stack – new nodes can be added and removed only at the top
 Push adds an item to a stack
 Pop extracts the most recently pushed item from the stack
 similar to a pile of dishes
 last-in, first-out (LIFO)
 Bottom of stack indicated by a link member to null
 stores the popped value
 constrained version of a linked list
Applications of Stack

 Conversion of expressions.
 Infix to postfix, postfix to prefix, prefix to infix, vice- versa.
 Evaluation of expressions.
 Arithmetic expression in the form of either postfix or
prefix.
 can be easily evaluated.
 Recursion.
 Ex. Tower of Hanoi etc.
 Other applications.
 Ex: Checking if a string is a palindrome or not.
 System Software and Compiler Design
 Towers of Hanoi
 Three pegs labeled A, B,C
 In A, there are finite number of disks with decreasing size
 Objective- move the disks from A to C using B as an
 auxiliary.
 The rules of the game are as follows
 Only one disk may be moved at a time.
 At no time can a larger disk be placed on a smaller disk

A B C
Procedure
For n disks
Move the top n-1 disks from peg A to peg B
Move the top disk from peg A to C
Move the top n-1 disks from peg B to peg C
Tower(N-1, BEG, END, AUX)
Tower(1,BEG, AUX, END)
Tower(N-1,AUX,BEG,END)

o Algorithm
o Tower(N,BEG,AUX,END)
o If N=1, then BEG END
o return
o Tower(N-1, BEG,END,AUX) // Move N-1 disks from BEG to AUX
o BEG-----END
o Tower(N-1, AUX, BEG,END)
o return
Queues
A queue is defined as a
special type of data
structure where the The end from where the
elements are inserted elements are inserted is REAR end.
from one end and called
elements are deleted from
the other end.

The end from where the Queue is organized as

elements are deleted is FRONT end. First In First Out (FIFO)
called Data

Structure.
Operations Performed on Queues

 Insertan item into a queue

 Delete an item from queue
 Display the contents of queue

Different types of Queues

 Queue(Ordinary queue)
 Circular Queue
 Double ended Queue
 Priority Queue
 Summary
o “Data Structures ”deals with the study of how the data is organized in the
memory, how efficiently the data can be retrieved and manipulated, and the
possible ways in which different data items are logically related.
o A Stack is defined as a special type of data structure where items are
inserted from one end called top of stack and items are deleted from the
same end.
o A queue is defined as a special type of data structure where the elements
are inserted from one end and elements are deleted from the other end.
o A Deque is a special type of data structure in which insertions and deletions
will be done either at the front end or at the rear end of the queue.
o In circular queue, the elements of a given queue can be stored efficiently in
an array so as to “wrap around” so that end of the queue is followed by the
front of the queue.
o The priority queue is a special type of data structure in which items can be
inserted or deleted based on the priority.