✓

Looping

Outline

• Data Management concepts
• Data types
• Primitive
• Non-primitive
• Types of Data Structures
• Linear Data Structures
• Non Linear Data Structures
• Performance Analysis and Measurement
• Time analysis of algorithms
• Space analysis of algorithms

What is Data?

• Data is the basic fact or entity that is utilized in calculation or manipulation.
• There are two different types of data Numeric data and Alphanumeric data.

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

2

When your data become Information ?

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

3

What is Data Structure?

• Data is symmetric way to organize data so that it can be used efficiently.
• Data Structure is a representation of the logical relationship existing between individual elements of data.
• Data Structure mainly specifies the following four things
• Organization of Data
• Accessing Methods
• Degree of Associatively
• Processing alternatives for information

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

4

What is Data Structure? Cont..

• The representation of a particular data structure in the memory of a computer is called Storage Structure.
• The storage structure representation in auxiliary memory is called as File Structure.

Algorithm

Data Structure

Program

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

5

Classification of Data Structure

Data Structure

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

6

Primitive / Non-primitive data structures

• Primitive data structures
• Primitive data structures are basic structures and are directly operated upon by machine instructions.
• Integers, floats, character and pointers are examples of primitive data structures.
• Non primitive data structure
• These are derived from primitive data structures.
• The non-primitive data structures emphasize on structuring of a group of homogeneous or heterogeneous data items.
• Examples of Non-primitive data type are Array, List, and File.

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

7

Non primitive Data Structure

• Array: An array is a fixed-size sequenced collection of elements of the same data type.
• List: An ordered set containing variable number of elements is called as Lists.
• File: A file is a collection of logically related information. It can be viewed as a large list of records consisting of various fields.

Array

List

File

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

8

Linear / Non-Linear data structure

• Linear data structures
• A data structure is said to be Linear, if its elements are connected in linear fashion by means of logically or in sequence memory locations.
• Examples of Linear Data Structure are Stack and Queue.
• Nonlinear data structures
• Nonlinear data structures are those data structure in which data items are not arranged in a sequence.
• Examples of Non-linear Data Structure are Tree and Graph.

Stack

Queue

Tree

Graph

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

9

Examples of Data Structure

Array

Facebook uses Graph Data Structure for showing connection between friends.

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

10

Example of Data Structure

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

11

Operations of Data Structure

• Create: It results in reserving memory for program elements.
• Destroy: It destroys memory space allocated for specified data structure.
• Selection: It deals with accessing a particular data within a data structure.
• Updating: It updates or modifies the data in the data structure.
• Searching: It finds the presence of desired data item in the list of data items.
• Sorting: It is a process of arranging all data items in a data structure in a particular order.
• Merging: It is a process of combining the data items of two different sorted list into a single sorted list.
• Splitting: It is a process of partitioning single list to multiple list.
• Traversal: It is a process of visiting each and every node of a list in systematic manner.

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

12

Time and space analysis of algorithms

• Sometimes, there are more than one way to solve a problem.
• We need to learn how to compare the performance of different algorithms and choose the best one to solve a particular problem.
• While analyzing an algorithm, we mostly consider time complexity and space complexity.
• Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input.
• Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.
• Time & space complexity depends on lots of things like hardware, operating system, processors, etc.
• However, we don't consider any of these factors while analyzing the algorithm. We will only consider the execution time of an algorithm.

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

13

Calculate Time Complexity of Algorithm

• Time Complexity is most commonly estimated by counting the number of elementary functions performed by the algorithm.
• Since the algorithm's performance may vary with different types of input data,
• hence for an algorithm we usually use the worst-case Time complexity of an algorithm because that is the maximum time taken for any input size.

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

14

Calculating Time Complexity

• Calculate Time Complexity of Sum of elements of List (One dimensional Array)

​

SumOfList(A,n)

{

Line 1 total = 0

Line 2 for i = 0 to n-1

Line 3 total = total + A[i]

Line 4 return total

}

A is array, n is no of elements in array

TSumOfList = 1 + 2 (n+1) + 2n + 1

= 4n + 4

= n

We can neglate constant 4

Time complexity of given algorithm is n unit time

Cost

No of Times

1

1

Line

1

2

n + 1

2

2

n

3

1

1

4

#3130702 (DS) ⬥ Unit 1 – Introduction to Data Structures

15