Introduction to Data Structure

WHAT IS DATA :
• Data is the simply values or set of values.
• A data items refers to a single unit of values
• Data items that are divide into subitems are called group items; those
that are not called elementary items.
• For example, an employee’s name may be divided into three subitems-
first, middle & last. But employee number is single item.
• Collection of data organized into hierarchy of fields, record and files.

Prof Y. R. Shelokar
Introduction to Data Structure
• An entity is something that has certain attributes or properties which
may be assign values.
• Values may be either numeric or non-numeric.

• Attributes: Name Age Roll Number

• Values: ABC 25 1234
• Values: DEF 27 4567

Prof Y. R. Shelokar
Data Structure
The logical or mathematical mode of particular organization of data is
called a data structure.
Data Structure:
• Arrays
• Linked List
• Trees
• Stack
• Queue
• Garaph

Prof Y. R. Shelokar
Data Structure Operation
• Traversing- Accessing each record exactly once so that certain items in
the record may be processed
• Searching- Finding the location of the record with a given key value,
or finding the locations of all records whichsatisfy one or more
conditions
• Inserting-Adding a new record to the structure
• Deleting- Removing a record from structure

Prof Y. R. Shelokar
Algorithmic Notation
• Algorithm 2.1 (Largest Element in Array) A nonempty array DATA with N
numerical values is given. This algorithm finds the location LOC and the value
MAX of the largest element of DATA. The variable K is used as a counter.
• Step 1. [Initialize.] Set K:=1, LOC:=1 and MAX:= DATA[1].
• Step 2. [Increment counter.] Set K:= K+1.
• Step 3. [Test counter.] If K>N, Then:
Write : LOC, MAX, Exit.
• Step 4. [Compare and update.] If MAX<DATA[K], then:
Set LOC:= K and MAX:= DATA[K].
• Step 5. [Repeat loop] Go to Step 2.

Prof Y. R. Shelokar
Algorithmic Notation
• Identifying Number-
Algorithm is assigned an identifying number as follows
Example- Algorithm 2.1 (Unit 2- Algorithm 1)

• Step, Control, Exit-

The step of the algorithm are executed one after the other, beginning
with Step 1. Control may be transferred to Step n of the algorithm by
the statement “Go to Step n.” The algorithm is completed when the
statement Exit.

Prof Y. R. Shelokar
Algorithmic Notation
• Comments-
Each step may contain a comment in bracket which indicates the main
purpose of the step. The comment will usually appear at the beginning
or the end of the step.

• Variable Names-
Variable names will use capital letters, as in MAX and DATA. Single-
letter of variables used as counters or subscripts will also be capitalized
in the algorithms(K and N, for example)

Prof Y. R. Shelokar
Algorithmic Notation
• Assignment Statement
Our assignment statements will use the dots-equal notation := that is
used in Pascal. For example MAX:=DATA[1]

• Input and Output

Data may be input and assigned to varible by means of a read
statement with the following form
Read: Variable names
Write: Messages and/or varible names
Prof Y. R. Shelokar
Algorithmic Notation
• Procedures
The term “procedure” will be used for an independent algorithmic
module which solves a particular problem.

Prof Y. R. Shelokar
Complexity of Algorithms
• The complexity of an algorithm computes the amount of time
and spaces required by an algorithm for an input of size (n).
The complexity of an algorithm can be divided into two types.
The time complexity and the space complexity.
• The time complexity is defined as the process of determining a
formula for total time required towards the execution of that
algorithm.
• Space complexity is defining as the process of defining a
formula for prediction of how much memory space is required
for the successful execution of the algorithm.

Prof Y. R. Shelokar
Complexity Of Algorithms
• Best Case
• Average Case
• Worst Case

Prof Y. R. Shelokar
Notations for complexity of Algorithms
• Big O Notation (O): It represents the upper bound of the runtime of
an algorithm. Big O Notation's role is to calculate the longest time an
algorithm can take for its execution, i.e., it is used for calculating
the worst-case time complexity of an algorithm.
• Omega Notation (Ω(n)): It represents the lower bound of the runtime
of an algorithm. It is used for calculating the best time an algorithm
can take to complete its execution, i.e., it is used for measuring
the best case time complexity of an algorithm.
• Theta Notation (Θ(n)): It carries the middle characteristics of both Big
O and Omega notations as it represents the lower and upper
bound of an algorithm.

Prof Y. R. Shelokar
Storing Strings
• String are stored in three types of structure
1. Fixed-length structure
2. Variable-length structure with fixed maximum
3. Linked structure

Prof Y. R. Shelokar
Fixed-Length Storage
• Each line of print is viewed as a record, where all record have the
same length i.e. each record accommodates the same number of
characters.

Prof Y. R. Shelokar
Variable Length Storage with Fixed Maximum
• The storage of variable-length string in memory cells with fixed length
can be done in two general ways:
1. One can use marker, such as dollar sign($$), to signal end of the
string.
2. One can list length of the string- as an additional item in the pointer
array.

Prof Y. R. Shelokar
Variable Length Storage with Fixed Maximum

Prof Y. R. Shelokar
Linked List
• Linearly ordered sequence of memory cells, called nodes, where each
node contains an item, called link, which points to the next node in
the list.

Prof Y. R. Shelokar
Character Data Type
• Constants- String constants by placing the string in either single or
double quotation mark. Ex- ‘THE END’ are string constant of length 7
characters
• Variables- falls into three categories.
1. Static character variable- fixed & defined before program executed
2. Semi-static character variable- length may vary execution of
program as long as the length does not exceed a maximum value
determined by the program before program executed.
3. Dynamic character variable- length change during execution of
program

Prof Y. R. Shelokar
String Operation
• Substring- Accessing substring from given string
• SUBSTRING(string , initial, length)
• Example –
SUBSTRING(‘TO BE OR NOT TO BE’,4,7)
ANS= ‘BE OR N’

Prof Y. R. Shelokar
String Operation
• Indexing, also called pattern matching, refers to finding the position
where a string pattern P first appears in a given Text T.
• INDEX(text , pattern)
• If the P does not appear in the text T, then INDEX is assigned the value
0.
• Example-
INDEX(‘HIS FATHER IS THE PROFESSOR’,’THE’)
ANS=7

Prof Y. R. Shelokar
String Operation
• Concatenation-Let S1 and S2 be string that concatenation of s1 and
s2, which we denoted by S1//S2, is the string consisting of the
character of S1 followed by the characters of S2.
• Example-
S1=‘ABC’ S2=‘DEF’
S1//S2 ABCDEF

Prof Y. R. Shelokar
String Operation
• Length- Number of character in string is called its length.
• LENGTH(string)
• Example-
LENGTH(‘COMPUTER’)=8

Prof Y. R. Shelokar
Word Processing
• Computer also processes printed matter, such as letters, articles and
reports. It is in this letter context that we use term “word processing”.
• Word processing operations

• Insertion- Inserting a string in the middle of the text.

INSERT(text, position, string)
INSERT(‘ABCD’,3,’XYZ’) = ABXYZCD

Prof Y. R. Shelokar
Word Processing
• Deletion- Deleting a string from the text.
DELETE(text, position, length)
DELETE(‘ABCDEFG’,4,2) = ABCFG

• Replacement- Replacing one string in the text by another

REPLACE(text, pattern1,pattern2)
REPLACE(‘XABYABZ’,’AB’,’C’)= XCYABZ

Prof Y. R. Shelokar
Pattern Matching Algorithm
• Pattern matching is the problem of deciding whether or not a given
string pattern P appears in a string text T.
• First Pattern Matching Algorithm- The first pattern matching
algorithm is the obvious one in which we compare a given pattern P
with each of the substring of T, moving from left to right, until we get
a match.
• The second pattern matching algorithm uses a table which is derived
from a particular pattern P but is independent of the text T.

Prof Y. R. Shelokar
First Pattern Matching Algorithm

Prof Y. R. Shelokar
Complexity of first pattern matching
algorithm
• The complexity of this pattern matching algorithm is measured by the
number C of comparisons between characters in the pattern P and
characters of text T.
• C=N1+N2+..+NL

L is the position L in T where P first appears or L=MAX if P does not appear in T

MAX=LENGTH(T)-LENGTH(P)+1

Prof Y. R. Shelokar
Complexity of first pattern matching
algorithm
• In general, when P is an r-character string and T is an s-character
string, the data size for the algorithm is
• n=r+s
• In worst case- C(n)=r(s-r+1) [s=n-r]
• C(n)=r(n-2r+1) [r=(n+1)/4]
• C(n)=(n+1)2/8
• C(n)=O(n2)

Prof Y. R. Shelokar
Pattern Matching Algorithm
• Example P=aaba

Prof Y. R. Shelokar
Pattern Matching Algorithm

Prof Y. R. Shelokar
Pattern Matching Algorithm
• The running time of the above algorithm is proportional to the
number of times the step 2 loop is executed. The worst case occurs
when all of the text T is read i.e when loop is executed n=length(T)
times.
• The complexity of this pattern matching algorithm is equal to O(n).

Prof Y. R. Shelokar