Data Structures

 Unit-1

Introduction:

WHAT IS DATA STRUCTURE?

In computer science, a data structure is a way of organizing and storing data in a computer program so that it can be accessed and used efficiently. Data structures provide a means of managing large amounts of data, enabling efficient searching, sorting, insertion and deletion of data.

Data structures can be categorized into two types: Primitive data structures and non-primitive data structures.

Primitive data structures are the most basic data structures available in a programming language, such as integers, floating-point numbers, characters and Booleans.

Non-primitive data structures are complex data structures that are built using primitive data types, such as arrays, linked lists, stacks, queues, trees, graphs and hash tables.

The choice of data structure for a particular task depends on the type and amount of data to be

processed, the operations that need to be performed on the data and the efficiency requirements of the program. Efficient use of data structures can greatly improve the performance of a program, making it faster and more memory-efficient. A data structure is a particular way of organizing data in a computer so that it can be used effectively. The idea is to reduce the space and time complexities of different tasks.

The choice of a good data structure makes it possible to perform a variety of critical operations effectively. An efficient data structure also uses minimum memory space and execution time to process the structure.

Data Structure is a systematic way to organize data in order to use it efficiently.

Following terms are the foundation terms of a data structure.

 Interface − Each data structure has an interface. Interface represents the set of operations that a data structure supports. An interface only provides the list of supported operations, type of parameters they can accept and return type of these operations.

2 Data Structures

 Implementation − Implementation provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure.

Characteristics of a Data Structure

 Correctness − Data structure implementation should implement its interface correctly.

 Time Complexity − Running time or the execution time of operations of data structure must be as small as possible.

 Space Complexity − Memory usage of a data structure operation should be as little as possible.

Need for Data Structure

As applications are getting complex and data rich, there are three common problems that applications face now-a-days.

1. Efficient data processing: Data structures provide a way to organize and store data in a way that allows for efficient retrieval, manipulation and storage of data. For example, using a hash table to store data can provide constant-time access to data.

2. Memory management: Proper use of data structures can help to reduce memory usage and

optimize the use of resources. For example, using dynamic arrays can allow for more efficient use of memory than using static arrays.

3. Code reusability: Data structures can be used as building blocks in various algorithms and

programs, making it easier to reuse code.

4. Abstraction: Data structures provide a level of abstraction that allows programmers to focus on the logical structure of the data and the operations that can be performed on it, rather than on the details of how the data is stored and manipulated.

5. Algorithm design: Many algorithms rely on specific data structures to operate efficiently.

Understanding data structures is crucial for designing and implementing efficient algorithms.

6. Data Search − Consider an inventory of 1 million (106) items of a store. If the application is to search an item, it has to search an item in 1 million (106) items every time slowing down the search. As data grows, search will become slower.

3 Data Structures

7. Processor Speed − Processor speed although being very high, falls limited if the data grows to billion records.

8. Multiple Requests − As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data.

Importance of Data Structures in Programming

 Efficient data access and manipulation: Data structures enable quick access and manipulation of data. For example, an array allows constant-time access to elements using their index, while a hash table allows fast access to elements based on their key. Without data structures, programs would have to search through data sequentially, leading to slow performance.

 Memory management: Data structures allow efficient use of memory by allocating and deallocating memory dynamically. For example, a linked list can dynamically allocate memory for each element as needed, rather than allocating a fixed amount of memory upfront. This helps avoid memory wastage and enables efficient memory management.

 Code reusability: Data structures can be reused across different programs and projects. For example, a generic stack data structure can be used in multiple programs that require LIFO (Last-In-First-Out) functionality, without having to rewrite the same code each time.

 Optimization of algorithms: Data structures help optimize algorithms by enabling efficient data access and manipulation. For example, a binary search tree allows fast searching and insertion of elements, making it ideal for implementing searching and sorting algorithms.

 Scalability: Data structures enable programs to handle large amounts of data effectively. For example, a hash table can store large amounts of data while providing fast access to elements based on their key.

Basic Terminology

 Data − Data are values or set of values.

 Data Item − Data item refers to single unit of values.

4 Data Structures

 Group Items − Data items that are divided into sub items are called as Group Items.

 Elementary Items − Data items that cannot be divided are called as Elementary Items.

 Attribute and Entity − An entity is that which contains certain attributes or properties, which may be assigned values.

 Entity Set − Entities of similar attributes form an entity set.

 Field − Field is a single elementary unit of information representing an attribute of an entity.

 Record − Record is a collection of field values of a given entity.

 File − File is a collection of records of the entities in a given entity set.

Data structures can broadly be classified into two main categories:

1. Primitive Data Structures

Primitive data structures are the most basic types of data structures provided by programming languages. They include:

 Integer: Whole numbers (e.g., 1, 2, 100).

 Float: Numbers with decimal points (e.g., 3.14, 0.001).

 Character: Single characters (e.g., ‘A’, ‘B’).

 Boolean: Logical values (true or false).

Data Structures

Sample Program in C++ (Primitive Data Types)

#include <iostream>

using namespace std;

int main() {

int num = 10; // Integer

float pi = 3.14; // Float

char letter = 'A'; // Character

bool isHappy = true; // Boolean

cout << "Integer: " << num << endl;

cout << "Float: " << pi << endl;

cout << "Character: " << letter << endl;

cout << "Boolean: " << isHappy << endl;

return 0;

}

2. Non-Primitive Data Structures

Non-primitive data structures are more complex and are built using primitive data types. They are further divided into:

a. Linear Data Structures

In linear data structures, elements are arranged sequentially, and each element has a unique predecessor and successor (except the first and last elements).

 Array: A collection of elements of the same type, stored in contiguous memory locations.

 Linked List: A collection of nodes where each node contains data and a pointer to the next node.

 Stack: A collection of elements following the Last In First Out (LIFO) principle.

 Queue: A collection of elements following the First In First Out (FIFO) principle.

Sample Program in C++ (Array)

#include <iostream>

using namespace std;

int main() {

Data Structures

int arr[5] = {1, 2, 3, 4, 5}; // Array of integers

cout << "Array elements:" << endl;

for (int i = 0; i < 5; i++) {

cout << arr[i] << " ";

}

cout << endl;

return 0;

}

b. Non-Linear Data Structures

In non-linear data structures, elements are not arranged sequentially but follow a hierarchical or interconnected structure.

 Tree: A hierarchical structure where each node has a parent node and zero or more child nodes.

 Graph: A set of nodes (vertices) connected by edges, representing relationships.

Sample Program in C++ (Basic Tree Traversal)

#include <iostream>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

Node(int val) {

data = val;

left = right = nullptr;

}

};

void inOrder(Node* root) {

if (root == nullptr) return;

inOrder(root->left);

cout << root->data << " ";

7 Data Structures

inOrder(root->right);

}

int main() {

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

cout << "In-order Traversal: ";

inOrder(root);

cout << endl;

return 0;

}

c. File Structures

Specialized data structures designed for storing data in secondary storage for efficient retrieval and updates. Examples include B-trees and hash files.

Applications of Data Structures:

Arrays: Arrays are used to store a collection of homogeneous elements contiguous memory locations. They are commonly used to implement other data structures, such as stacks and queues, and to represent matrices and tables.

Linked lists: Linked lists are used to store a collection of heterogeneous elements with dynamic memory allocation. They are commonly used to implement stacks, queues and hash tables.

Trees: Trees are used to represent hierarchical data structures, such as file systems, organization charts, and network topologies. Binary search trees are commonly used to implement dictionaries and symbol tables.

Graphs: Graphs are used to represent complex relationships between data elements, such as social networks, transportation networks and computer networks. They are commonly used to implement shortest path algorithms and graph traversal algorithms.

Hash tables: Hash tables are used to implement associative arrays, which store key-value pairs. They provide fast access to data elements based on their keys.

8 Data Structures

 Stacks: Stacks are used to store a collection of elements in a last-in-first-out (LIFO) order. They are commonly used to implement undo-redo functionality, recursive function calls and expression evaluation.

 Queues: Queues are used to store a collection of elements in a first-in-first-out (FIFO) order. They are commonly used to implement waiting lines, message queues and job scheduling.

Common operations on various Data Structures:

Data Structure is the way of storing data in computer’s memory so that it can be used easily and efficiently. There are different data-structures used for the storage of data. It can also be defined as a mathematical or logical model of a particular organization of data items. The representation of particular data structure in the main memory of a computer is called as storage structure.

For Examples: Array, Stack, Queue, Tree, Graph, etc.

Operations on different Data Structure:

There are different types of operations that can be performed for the manipulation of data in every data structure. Some operations are explained and illustrated below:

 Traversing: Traversing a Data Structure means to visit the element stored in it. It visits data in a systematic manner. This can be done with any type of DS.

 Searching: Searching means to find a particular element in the given data-structure. It is considered as successful when the required element is found. Searching is the operation which we can performed on data-structures like array, linked-list, tree, graph, etc.

 Insertion: It is the operation which we apply on all the data-structures. Insertion means to add an element in the given data structure. The operation of insertion is successful when the required element is added to the required data-structure. It is unsuccessful in some cases when the size of the data structure is full and when there is no space in the data-structure to add any additional element. The insertion has the same name as an insertion in the data-structure as an array, linked-list, graph, tree. In stack, this operation is called Push. In the queue, this operation is called Enqueue.

9 Data Structures

 Deletion: It is the operation which we apply on all the data-structures. Deletion means to delete an element in the given data structure. The operation of deletion is successful when the required element is deleted from the data structure. The deletion has the same name as a deletion in the data- structure as an array, linked-list, graph, tree, etc. In stack, this operation is called Pop. In Queue this operation is called Dequeue.

 Create: It reserves memory for program elements by declaring them. The creation of data structure can be done during

o Compile-time

o Run-time.

 Selection: It selects specific data from present data. You can select any specific data by giving condition in loop.

 Update: It updates the data in the data structure. You can also update any specific data by giving some condition in loop like select approach.

 Sort: Sorting data in a particular order (ascending or descending). We can take the help of many sorting algorithms to sort data in less time. Example: bubble sort which takes O (n^2) time to sort data. There are many algorithms present like merge sort, insertion sort, selection sort, quick sort, etc.

 Merge: Merging data of two different orders in a specific order may ascend or descend. We use merge sort to merge sort data.

 Split Data: Dividing data into different sub-parts to make the process complete in less time.

10 Data Structures

Algorithm Specifications:

What is an Algorithm? Algorithm Basics

The word Algorithm means” A set of finite rules or instructions to be followed in calculations or other problem-solving operations” or” A procedure for solving a mathematical problem in a finite number of steps that frequently involves recursive operations”. Therefore, Algorithm refers to a sequence of finite steps to solve a particular problem.

Use of the Algorithms:

Algorithms play a crucial role in various fields and have many applications. Some of the key areas where algorithms are used include:

Computer Science: Algorithms form the basis of computer programming and are used to solve problems ranging from simple sorting and searching to complex tasks such as artificial intelligence and machine learning.

Mathematics: Algorithms are used to solve mathematical problems, such as finding the optimal solution to a system of linear equations or finding the shortest path in a graph.

Operations Research: Algorithms are used to optimize and make decisions in fields such as transportation, logistics, and resource allocation.

Artificial Intelligence: Algorithms are the foundation of artificial intelligence and machine learning, and are used to develop intelligent systems that can perform tasks such as image recognition, natural language processing and decision-making.

Data Science: Algorithms are used to analyze, process, and extract insights from large amounts of data in fields such as marketing, finance and healthcare.

These are just a few examples of the many applications of algorithms. The use of algorithms is continually expanding as new technologies and fields emerge, making it a vital component of modern society.

Divide and Conquer

Introduction to Divide and Conquer Algorithm

 

Divide and Conquer Algorithm is a problem-solving technique used to solve problems by dividing the main problem into subproblems, solving them individually and then merging them to find solution to the original problem. Divide and Conquer is mainly useful when we divide a problem into independent subproblems

 

. 1. Divide:

Ø  Break down the original problem into smaller subproblems.

Ø  Each subproblem should represent a part of the overall problem.

Ø  The goal is to divide the problem until no further division is possible.

Ø  In Merge Sort, we divide the input array in two halves. Please note that the divide step of Merge Sort is simple, but in Quick Sort, the divide step is critical. In Quick Sort, we partition the array around a pivot.

 

2. Conquer:

Ø  Solve each of the smaller subproblems individually.

Ø  If a subproblem is small enough (often referred to as the “base case”), we solve it directly without further recursion.

Ø  The goal is to find solutions for these subproblems independently.

Ø  In Merge Sort, the conquer step is to sort the two halves individually.

 

3. Merge:

Ø  Combine the sub-problems to get the final solution of the whole problem.

Ø  Once the smaller subproblems are solved, we recursively combine their solutions to get the solution of larger problem.

Ø  The goal is to formulate a solution for the original problem by merging the results from the subproblems.

Ø  In Merge Sort, the merge step is to merge two sorted halves to create one sorted array. Please note that the merge step of Merge Sort is critical, but in Quick Sort, the merge step does not do anything as both parts become sorted in place and the left part has all elements smaller (or equal( than the right part.

 

Characteristics of Divide and Conquer Algorithm

Divide and Conquer Algorithm involves breaking down a problem into smaller, more manageable parts, solving each part individually, and then combining the solutions to solve the original problem. The characteristics of Divide and Conquer Algorithm are:

 

Ø  Dividing the Problem: The first step is to break the problem into smaller, more manageable subproblems. This division can be done recursively until the subproblems become simple enough to solve directly.

Ø  Independence of Subproblems: Each subproblem should be independent of the others, meaning that solving one subproblem does not depend on the solution of another. This allows for parallel processing or concurrent execution of subproblems, which can lead to efficiency gains.

Ø  Conquering Each Subproblem: Once divided, the subproblems are solved individually. This may involve applying the same divide and conquer approach recursively until the subproblems become simple enough to solve directly, or it may involve applying a different algorithm or technique.

Ø  Combining Solutions: After solving the subproblems, their solutions are combined to obtain the solution to the original problem. This combination step should be relatively efficient and straightforward, as the solutions to the subproblems should be designed to fit together seamlessly. 

Examples of Divide and Conquer Algorithm

1. Merge Sort:

 

We can use Divide and Conquer Algorithm to sort the array in ascending or descending order by dividing the array into smaller subarrays, sorting the smaller subarrays and then merging the sorted arrays to sort the original array.

 

2. Quicksort:

 

It is a sorting algorithm that picks a pivot element and rearranges the array elements so that all elements smaller than the picked pivot element move to the left side of the pivot, and all greater elements move to the right side. Finally, the algorithm recursively sorts the subarrays on the left and right of the pivot element.

 

3. Binary Search 

 

Binary Search is an efficient algorithm for finding an element in a sorted array by repeatedly dividing the search interval in half. It works by comparing the target value with the middle element and narrowing the search to either the left or right half, depending on the comparison.

 

Advantages of Divide and Conquer Algorithm

Ø  Solving difficult problems: Divide and conquer technique is a tool for solving difficult problems conceptually. e.g. Tower of Hanoi puzzle. It requires a way of breaking the problem into sub-problems, and solving all of them as an individual cases and then combining sub- problems to the original problem.

Ø  Algorithm efficiency: The divide-and-conquer algorithm often helps in the discovery of efficient algorithms. It is the key to algorithms like Quick Sort and Merge Sort, and fast Fourier transforms.

Ø  Parallelism: Normally Divide and Conquer algorithms are used in multi-processor machines having shared-memory systems where the communication of data between processors does not need to be planned in advance, because distinct sub-problems can be executed on different processors.

Ø  Memory access: These algorithms naturally make an efficient use of memory caches. Since the subproblems are small enough to be solved in cache without using the main memory that is slower one. Any algorithm that uses cache efficiently is called cache oblivious.

 

Disadvantages of Divide and Conquer Algorithm

 

Ø  Overhead: The process of dividing the problem into subproblems and then combining the solutions can require additional time and resources. This overhead can be significant for problems that are already relatively small or that have a simple solution.

 

Ø  Complexity: Dividing a problem into smaller subproblems can increase the complexity of the overall solution. This is particularly true when the subproblems are interdependent and must be solved in a specific order.

 

Ø  Difficulty of implementation: Some problems are difficult to divide into smaller subproblems or require a complex algorithm to do so. In these cases, it can be challenging to implement a divide and conquer solution.

 

Ø  Memory limitations: When working with large data sets, the memory requirements for storing the intermediate results of the subproblems can become a limiting factor.

 

           Example

                                   

Merge Sort

 

Quick Sort

 

Data Warehousing & Data Mining Lab Important Questions

 

Q1

A real estate agency in a metropolitan area wants to develop a model to predict house prices accurately. Design an experiment using the suitable data mining algorithm to assist the agency in building a predictive model for house prices.

Instructions:

1.     Select a suitable dataset containing information about real estate properties, including   features like area, bedrooms, bathrooms, location, and sale prices.

2.     Perform necessary data preprocessing steps, including handling missing values, encoding categorical variables, and scaling numerical features.

3.     Choose relevant features that could influence house prices and build data mining model to predict prices based on these features.

4.     Choose appropriate data mining task that could influence house prices and build a model to predict prices based on these features.

5.     Split the dataset into training and testing sets and find which Model Selection method gives best accuracy among the following

           (a)Hold Out (b) K-Fold Cross Validation (c) Stratified K-Fold Cross Validation

6.   Evaluate the performance of the trained model using appropriate metrics such as Mean Absolute Error (MAE), Mean Squared Error (MSE), R-squared (R2) and accuracy

Analyze the coefficients of the of the model to interpret the impact of each feature on house prices.

8.     Predict house prices by reading multiple unknown values as a Data Frame.

9.     Plot the  model with input data values along with unknown values

1      Provide recommendations to the real estate agency based on the analysis and interpretation of the model results.

 

Q2

Educational institutions strive to support student success and improve academic outcomes by identifying students who may be struggling and providing them with appropriate interventions. Design an experiment using the suitable clustering algorithm to categorize students based on their academic performance, assisting in the identification of at-risk students who may benefit from intervention and support programs.

 

Instructions:

 

1. Select a suitable dataset containing student academic records, including features such as grades, attendance, study hours, participation in extracurricular activities, and socio-economic background.

2. Perform necessary data preprocessing steps to prepare the data for clustering analysis, ensuring data quality and consistency.

3.  Apply the suitable clustering algorithm to the preprocessed data to partition students into distinct clusters based on their similarities in academic performance metrics.

4. Analyze the resulting clusters to understand the unique characteristics and performance levels of students within each cluster.

5. Develop targeted intervention strategies for students in each performance category, including academic support programs, mentoring, counseling, and resources allocation tailored to the needs of students in each cluster.

6.  Provide recommendations to the educational institution based on the analysis and interpretation of the student performance categories to improve academic outcomes and support student success.

 

Q3

Organizations strive to optimize their employee hierarchy to ensure fair compensation, talent development, and organizational effectiveness. Design an experiment using the suitable Clustering algorithm to analyze the salary-based employee hierarchy within an organization, assisting in identifying potential areas for restructuring or improvement to enhance organizational performance.

 

Instructions:

 

1.    Select a suitable dataset containing information about employees within the organization, including features such as employee ID, salary, department, job title, years of experience, and performance ratings.

2.   Perform necessary data preprocessing steps to prepare the data for clustering analysis, ensuring data quality and consistency.

3.     Apply the suitable Clustering algorithm to the preprocessed data to identify hierarchical structures based on employee salaries.

4.   Analyze the resulting clusters to understand the grouping of employees based on salary levels and identify potential areas for optimization or restructuring.

5.   Develop recommendations for optimizing the employee hierarchy, including strategies for salary adjustments, promotions, talent development, and succession planning, based on the analysis of hierarchical clusters.

6. Provide actionable insights to organizational stakeholders based on the analysis and interpretation of the employee hierarchy optimization results to enhance organizational performance and employee satisfaction.

 

Q4

Retailers aim to enhance customer satisfaction and increase sales by delivering personalized shopping experiences tailored to the preferences and needs of individual customers. Design an experiment using the suitable clustering algorithm to segment customers based on spatial density, their purchasing behavior and demographics, assisting in targeted marketing and personalized customer engagement strategies.

 

Instructions:

 

1. Select a suitable dataset containing customer transaction data from a retail store, including features such as purchase history, frequency, recency, monetary value, demographics, and location.

2.  Perform necessary data preprocessing steps to prepare the data for clustering analysis, ensuring data quality and consistency.

3.  Apply the suitable algorithm to the preprocessed customer data to identify clusters of customers based on their spatial density in the feature space.

4.   Analyze the resulting clusters to understand the distinct segments of customers based on their purchasing behavior and demographics.

5.    Develop targeted marketing strategies for each customer segment, including personalized promotions, product recommendations, and communication channels tailored to the preferences and needs of customers in each cluster.

6. Provide recommendations for implementing and operationalizing the segmented customer strategy to enhance customer engagement and increase sales.

 

 

 

 

 

 

Q5

A telecommunications company is experiencing high customer churn rates and wants to develop a predictive model to identify customers at risk of churning. Design an experiment using appropriate data mining algorithm to assist the company in building a model for predicting customer churn.

Instructions:

1.     Select a suitable dataset containing information about telecommunications customers, including features such as account length, international plan, voicemail plan, number of customer service calls, and churn status.

2.     Perform necessary data preprocessing steps, including handling missing values, encoding categorical variables, and scaling numerical features.

3.     Choose relevant features that could influence customer churn and build a model to predict churn status based on these features.

4.     Split the dataset into training and testing sets and find which Model Selection method gives best accuracy among the following

           (a)Hold Out (b) K-Fold Cross Validation (c) Stratified K-Fold Cross Validation

5.     Evaluate the performance of the trained model using appropriate classification metrics such as accuracy, precision, recall, and F1-score on the testing data.

6.     Analyze the model structure by selecting the best splitting criterion to interpret the key factors driving customer churn and identify actionable insights for the telecommunications company.

7.     Predict the risk of churning by reading multiple unknown values as a Data Frame.

8.     Provide recommendations to the company based on the analysis and interpretation of the model results.

9.     Outline the steps the company should take to implement and utilize the predictive model effectively in their operations.

 

Q6

Email spam continues to be a significant problem, with potentially harmful consequences such as phishing attacks and malware distribution. Design an experiment using probability based classification algorithm to develop a model for detecting email spam, helping users filter out unwanted and potentially dangerous emails from their inboxes.

 

Instructions:

 

1.     Select a suitable dataset containing labeled emails, distinguishing between spam and non-spam (ham) emails.

2.     Perform necessary data preprocessing steps to convert the textual data into numerical features suitable for classification.

3.     Build a data mining model to classify emails as spam or non-spam based on the presence or absence of certain words.

4.     Split the dataset into training and testing sets and train the model using the training data.

5.     Evaluate the performance of the trained model using classification metrics such as accuracy, precision, recall, and F1-score on the testing data.

6.     Analyze the model's predictions and misclassifications to understand its effectiveness in distinguishing between spam and non-spam emails.

7.     Predict email spam by reading multiple unknown values as a Data Frame

8.     Provide recommendations for users based on the analysis and interpretation of the model results to improve email security and reduce the risk of falling victim to email scams or cyber attacks.

 

 

 

 

 

 

Q7

Retail stores strive to maximize sales and enhance customer satisfaction by understanding purchasing patterns and optimizing product offerings. Design an experiment using the different appropriate data mining algorithm to perform market basket analysis for a retail store, assisting in identifying associations between products and recommending strategies for improving sales and customer experience.

Instructions:

 

1.     Select a suitable dataset containing transaction records from the retail store, where each transaction lists the items purchased by a customer.

2.     Perform necessary data preprocessing steps to prepare the transaction data for market basket analysis, ensuring data quality and consistency.

3.     Apply the suitable algorithm to the transaction data to generate frequent itemsets, setting appropriate parameters such as minimum support threshold.

4.     Generate association rules from the frequent itemsets, considering metrics such as confidence, lift, and support to identify meaningful associations between products.

5.     Analyze the generated frequent itemsets and association rules to uncover patterns and insights that can inform decisions related to product placement, promotions, and cross-selling strategies by using different appropriate data mining algorithms

6.     Provide recommendations to the retail store based on the analysis and interpretation of the market basket analysis results to optimize sales and enhance the customer shopping experience.