Unit-1 Introduction to Data Structure

SESSION 1 Introduction to Data Structures

SESSION 2 Abstract Data Types
SESSION 3 Static & Dynamic Implementations with examples
SESSION 4 Arrays- ordered lists
SESSION 5 Representation of Arrays in Memory
SESSION 6 Operations on Arrays
SESSION 7 Asymptotic Analysis
SESSION 8 Space & Time Complexities

Dr. Swati, Ms Suman & Ms Neetu 1

Unit-1 Introduction to Data Structure

SESSION 9 Recurrence Relations

SESSION 10 Analysis of Iterative and Recurrence Relations
SESSION 11 Revision

Dr. Swati, Ms Suman & Ms Neetu 2

Recapitulation (Previous Session)

Quiz
Q1: What happens if you try to access an element at an index beyond the
array size?
a) The program crashes.
b) The element at that index is set to null.
c) It returns an error.
d) It returns the last element of the array.

Q2: Which of the following is an example of a two-dimensional array?

a) int[] array;
b) int[][] matrix;
c) ArrayList<int[]> list;
d) HashMap<int, int> map.

Dr. Swati, Ms Suman & Ms Neetu 3

Recapitulation (Previous Session cont..)

Q3: In C programming, how do you declare and initialize a static array of

integers with 5 elements?
a) int array[5] = {1, 2, 3, 4, 5};
b) array<int> array = {1, 2, 3, 4, 5};
c) int array[] = {1, 2, 3, 4, 5};
d) Array arrayName = new Array(5);

Q4: What is the index of the last element in an array with size n?
a) n
b) n-1
c) n+1

Dr. Swati, Ms Suman & Ms Neetu 4

Recapitulation (Previous Session)

Quiz (Answers)
A1: c) It returns an error.

A2: b) int[][] matrix;

A3: c) int array[] = {1, 2, 3, 4, 5};

A4: b) n-1

Dr. Swati, Ms Suman & Ms Neetu 5

Array

 Contiguous Memory Allocation

 Fixed Size
 Index-Based Access
 Searching
 Homogeneous Elements
 Sequential Storage

Fig. 1: Representation of array in memory

Dr. Swati, Ms Suman & Ms Neetu 6

Array Operations

Array Operations

Traversal Insertion Deletion Searching

Fig. 2: Different Array Operations

Dr. Swati, Ms Suman & Ms Neetu 7

Array Traversal

 Visiting all elements at once.

Fig. 3: Algorithm of Array Traversal

Dr. Swati, Ms Suman & Ms Neetu 8

Array Traversal (Program)

Fig. 4: Example of Array Traversal In language ‘C’

Fig. 5: Example of Array Traversal In language ‘Python’

Dr. Swati, Ms Suman & Ms Neetu 9

Insertion in Array

 Insert one or more elements

 Insertion at any position in array

Fig. 6: Algorithm of Insertion in Array

Dr. Swati, Ms Suman & Ms Neetu 10

Insertion in Array (Program)

Fig. 7: Example of Insertion in language ‘C’

Fig. 8: Example of Insertion in language ‘Python’

Dr. Swati, Ms Suman & Ms Neetu 11

Deletion in Array

 Deletes element at any index.

Fig. 9: Algorithm of Deletion in Array

Dr. Swati, Ms Suman & Ms Neetu 12

Searching in Array

 Searching for an element.

Fig. 10: Algorithm of Deletion in Array

Dr. Swati, Ms Suman & Ms Neetu 13

Searching in Array

Fig. 11: Python program of Searching in Array

Dr. Swati, Ms Suman & Ms Neetu 14

Time Complexity Analysis of operations an Array

Operation Best Case Average Case Worst Case

Traversal Ω(N) θ(N) O(N)

Insertion Ω(1) θ(N) O(N)

Deletion Ω(1) θ(N) O(N)

Searching Ω(1) θ(N) O(N)

Dr. Swati, Ms Suman & Ms Neetu 15

Space Complexity Analysis of operations an Array

Operation Best Case Average Case Worst Case

Traversal Ω(1) θ(1) O(1)

Insertion Ω(1) θ(N) O(N)

Deletion Ω(1) θ(N) O(N)

Searching Ω(1) θ(1) O(1)

Dr. Swati, Ms Suman & Ms Neetu 16

Applications of an Array Data Structure

 SearStoring and accessing data

 Sorting
 ching
 Matrices
 Stacks and queues
 Graphs
 Dynamic programming

Dr. Swati, Ms Suman & Ms Neetu 17

Real-time Applications of an Array Data Structure

•Multimedia Applications
•Data Mining
•Robotics
•Real-time Monitoring and Control Systems
•Financial Analysis
•Scientific Computing
•Signal Processing

Dr. Swati, Ms Suman & Ms Neetu 18

Practice Questions
Q1: Write a C++ function to find the maximum element in the array
[8, 12, 6, 3, 15, 7, 1] . What is the maximum element?

Q 2: Write a C++ function to find the minimum element in the array [4, 9, 11, 2, 8,
6] . What is the minimum element?

Q 3: Write a C++ function to reverse the array [1, 2, 3, 4, 5]. What will be the
resulting array?

Q 4: Write a C++ function to calculate the average of the elements in the array [10,
20, 30, 40, 50]. What is the average?

Dr. Swati, Ms Suman & Ms Neetu 19

 General Code (Solutions)
• // Online C++ compiler to run C++ program online
• #include <iostream>
• #include <climits>
• using namespace std;
• int main() {
• int n;
• cout<<"Enter the size of array: ";
• cin>>n;
• int arr[n];
• cout<<"Enter the elements of array: ";
• for(int i=0;i<n;i++){
• cin>>arr[i];
• }
• cout<<endl;
• cout<<"Printing the elements of array: ";
• for(int i=0;i<n;i++){
• cout<<arr[i]<<" ";
• }
• cout<<endl;
• int rev[n];
• for(int i=0;i<n;i++){
• rev[i]=arr[n-1-i];
• }
• cout<<"Reversing the array: ";
• for(int i=0;i<n;i++){
• cout<<rev[i]<<" ";
• }
• cout<<endl;
• int max = INT_MIN;
• int min = INT_MAX;
• for(int i=0;i<n;i++){
• if(arr[i]>max){
• max=arr[i];
• }
• if(arr[i]<min){
• min=arr[i];
• }
• }
• cout<<"The largest element of array is : "<<max<<endl;
• cout<<"The smallest element of array is : "<<min<<endl; Dr. Swati, Ms Suman & Ms Neetu 20
• int sum=0;
• for(int i=0;i<n;i++){
Practice Questions (Answers)
A1: #include <iostream>
using namespace std;

int getMax(int arr[], int size) {

int max = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
int main() {
int arr[] = {8, 12, 6, 3, 15, 7, 1};
int size = 7;

int maxElement = getMax(arr, size);

cout << "Maximum element: " << maxElement <<
endl;

return 0;
} Dr. Swati, Ms Suman & Ms Neetu 21
Practice Questions (Answers)
A2: #include <iostream>
using namespace std;

int getMin(int arr[], int size) {

int min = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
int main() {
int arr[] = {4, 9, 11, 2, 8, 6};
int size = 6;

int minElement = getMin(arr, size);

cout << "Minimum element: " << minElement <<
endl;
return 0;
}
Dr. Swati, Ms Suman & Ms Neetu 22
Practice Questions (Answers)
A3: #include <iostream>
using namespace std;

void reverseArray(int arr[], int size) {

int start = 0, end = size - 1;
while (start < end) {
swap(arr[start], arr[end]);
start++;
end--;
}}

A4: #include <iostream>

using namespace std;

int sumOfElements(int arr[], int size) {

int sum = 0;

Dr. Swati, Ms Suman & Ms Neetu 23

THANK YOU

Dr. Swati, Ms Suman & Ms Neetu 24