Data Structures and Algorithms

Module1

1.1. Introduction to Data Structures:

Data structure is a representation of logical relationship existing between individual elements of data.

In other words, a data structure defines a way of organizing all data items that considers not only the

elements stored but also their relationship to each other. The term data structure is used to describe

the way data is stored.

To develop a program of an algorithm we should select an appropriate data structure for that

algorithm. Therefore, data structure is represented as: Algorithm + Data structure = Program

A data structure is said to be linear if its elements form a sequence or a linear list. The linear data

structures like an array, stacks, queues and linked lists organize data in linear order. A data structure

is said to be non linear if its elements form a hierarchical classification where, data items appear at

various levels.

Trees and Graphs are widely used non-linear data structures. Tree and graph structures represent

hierarchical relationship between individual data elements. Graphs are nothing but trees with certain

restrictions removed.

Data structures are divided into two types:

• Primitive data structures.

• Non-primitive data structures.

Primitive Data Structures are the basic data structures that directly operate upon the machine

instructions. They have different representations on different computers. Integers, floating point

numbers, character constants, string constants and pointers come under this category.

Non-primitive data structures are more complicated data structures and are derived from primitive

data structures. They emphasize on grouping same or different data items with relationship between

each data item. Arrays, lists and files come under this category. Figure 1.1 shows the classification of

data structures.

Data Structures Operations:

1. Traversing

2. Searching

3. Inserting

4. Deleting

5. Sorting

6. Merging

1. Traversing- It is used to access each data item exactly once so that it can be processed.

2. Searching- It is used to find out the location of the data item if it exists in the given collection

of data items.

3. Inserting- It is used to add a new data item in the given collection of data items.

4. Deleting- It is used to delete an existing data item from the given collection of data items.

5. Sorting- It is used to arrange the data items in some order i.e. in ascending or descending

order in case of numerical data and in dictionary order in case of alphanumeric data.

6. Merging- It is used to combine the data items of two sorted files into single file in the sorted

form.

Review of Arrays

The simplest type of data structure is a linear array. This is also called one dimensional array.

Definition:

Array is a data structure that can store a fixed-size sequential collection of elements of the same type.

An array is used to store a collection of data, but it is often more useful to think of an array as a

collection of variables of the same type. An array holds several values of the same kind. Accessing

the elements is very fast. It may not be possible to add more values than defined at the start, without

copying all values into a new array. An array is stored so that the position of each element can be

computed from its index.

For example, an array of 10 integer variables, with indices 0 through 9, may be stored as 10 words at

memory addresses 2000, 2004, 2008, 2036, so that the element with index i has the address 2000 + 4

× i.

Address Calculation in single (one) Dimension Array:

Array of an element of an array say “A[ I ]” is calculated using the following formula:

Address of A [ I ] = B + W * ( I – LB )

Where,

B = Base address

W = Storage Size of one element stored in the array (in byte)

I = Subscript of element whose address is to be found

LB = Lower limit / Lower Bound of subscript, if not specified assume 0 (zero)

Example:

Given the base address of an array B[1300…..1900] as 1020 and size of each element is 2 bytes in the

memory. Find the address of B[1700].

Solution:

The given values are: B = 1020, LB = 1300, W = 2, I = 1700

Address of A [ I ] = B + W * ( I – LB )

= 1020 + 2 * (1700 – 1300)

= 1020 + 2 * 400

= 1020 + 800

= 1820 [Ans]

Address Calculation in Double (Two) Dimensional Array:

While storing the elements of a 2-D array in memory, these are allocated contiguous memory

locations. Therefore, a 2-D array must be linearized so as to enable their storage. There are two

alternatives to achieve linearization: Row-Major and Column-Major.

Overview

Data Structures and Algorithms - Reema Thareja

Data Structures and Algorithms by Reema Thareja provides a comprehensive overview of essential data structures and their applications in programming. This resource covers key concepts such as linear and non-linear data structures, including arrays, stacks, queues, linked lists, trees, and graphs. Ideal for computer science students and professionals, this guide emphasizes the importance of selecting appropriate data structures for algorithm development. The text includes practical examples and exercises to enhance understanding and application of data structures in real-world scenarios. Key Points Explains the fundamentals of data structures and their importance in programming Covers linear data structures like arrays, stacks, and queues Discusses non-linear data structures includin…

/ 132

Figures

Data Structures and Algorithms - Reema Thareja — Module1

Array of an element of an array say “A[ I ]” is calculated using the following formula:

C allows for arrays of two or more dimensions. A two-dimensional (2D) array is an array of arrays. A

Data Structures and Algorithms - Reema Thareja — C allows for arrays of two or more dimensions. A two-dimensional (2D) array is an array of arrays. A

In above example matrix, there are only 6 non-zero elements ( those are 9, 8, 4, 2, 5 & 2) and matrix

Consider the above same sparse matrix used in the Triplet representation. This sparse matrix can be

In above representation, H0, H1,...,H5 indicates the header nodes which are used to represent indexes.

Data Structures and Algorithms - Reema Thareja — MODULE 2

Push operation is done by inserting a node at the start of the list and pop is done by deleting

Note: In case of empty queue, front is one position ahead of rear : FRONT = REAR +

Data Structures and Algorithms - Reema Thareja — Circular Queue

This situation also says that Queue is Full and the new elementcannot be inserted because,

Note that the container of items is an array. Array is stored in main memory. Main memory is

Addition causes the increment in REAR. It means that when REAR reaches N-1 position then

Deque is a variation of queue data structure, pronounced “deck”, which stands for double-

Data Structures and Algorithms - Reema Thareja — Start with the head and access each node until you reach null. Do not change the

The algorithm is similar to insert "before" algorithm. It is convinient to use two

A header linked list is a linked list which always contains a special node called the

Data Structures and Algorithms - Reema Thareja — header node

IN a singly linked circular list, the pointer field of the last node stores the address of

Data Structures and Algorithms - Reema Thareja — Child

Data Structures and Algorithms - Reema Thareja — Height

Left Child - Right Sibling Representation

In this representation, every node's data field stores the actual value of that node. If that node has left child,

Root of the general tree is the root of the binary tree.

Strictly binary tree data structure is used to represent mathematical expressions.

Data Structures and Algorithms - Reema Thareja — Types of Binary Trees

In above figure, a normal binary tree is converted into full binary tree by adding dummy nodes (In pink

Data Structures and Algorithms - Reema Thareja — A binary tree in which every internal node has exactly two children and all leaf nodes are at same level is

A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes wherever

The level order traversal of the above tree is F B G A D I C E H

The following tree is a Binary Search Tree. In this tree, left subtree of every node contains nodes with

Every Binary Search Tree is a binary tree but all the Binary Trees need not to be binary search trees.

Data Structures and Algorithms - Reema Thareja — We use the following steps to delete a node with two children from BST...

In above figure threads are indicated with dotted links.

Graphs can be classified by whether or not their edges have

Fig (1) adjacency lsit for the graph of fig3

Example directed graph (assume self-edges allowed):

graph is small and connected. For a large graph ,whose matrix is sparse, adjacency

Data Structures and Algorithms - Reema Thareja — Figure 62

Data Structures and Algorithms - Reema Thareja — Figure 63

Data Structures and Algorithms - Reema Thareja — Figure 64

Data Structures and Algorithms - Reema Thareja — Figure 65

Data Structures and Algorithms - Reema Thareja — Figure 66

table. While searching for a value in a hash table, the array index is re-computed and the key

Double hashing minimizes repeated collisions and the effects of clustering.

The linked list at each hash element is often called a chain. A

Chaining overcomes collision but increases search time when the length of the overflow

Data Structures and Algorithms - Reema Thareja — Increment the global and local depth

When 4 inserted overflow occurred. So we split the bucket (no matter it is full or partially

3 to new bucket as (3 mod 6 = 3 ) and (12 mod 6 = 0 ). Then 11 and 2 are inserted. And

we need to hash 10 again using h1(10) = 10 mod 6 = 4th bucket.

FAQs

what is data structures and algorithms by reema thareja about

Data Structures and Algorithms by Reema Thareja provides a comprehensive introduction to the fundamental concepts of data structures and algorithms.

The book covers various data structures such as arrays, linked lists, stacks, queues, trees, and graphs.
It explains algorithms related to searching, sorting, and traversal techniques.
Real-world applications and examples are included to illustrate the concepts effectively.

what are the key topics in data structures and algorithms by reema thareja

The key topics in Data Structures and Algorithms by Reema Thareja include:

Basic data structures: arrays, linked lists, stacks, and queues.
Advanced data structures: trees, graphs, and hash tables.
Algorithm design techniques: divide and conquer, dynamic programming, and greedy algorithms.
Sorting algorithms: bubble sort, merge sort, quick sort, and radix sort.
Searching algorithms: linear search and binary search.

how does reema thareja explain sorting algorithms

Reema Thareja explains sorting algorithms with clarity, focusing on both the theory and practical implementations.

Each sorting algorithm is introduced with its time complexity and space complexity.
Examples are provided to illustrate how each algorithm works step-by-step.
Common algorithms covered include bubble sort, selection sort, insertion sort, quick sort, and merge sort.
Visual aids and pseudocode are used to enhance understanding.

what is the importance of data structures and algorithms in programming

Data structures and algorithms are crucial in programming as they provide the foundation for efficient problem-solving.

They help in organizing and managing data effectively.
Choosing the right data structure can significantly affect the performance of an application.
Algorithms provide step-by-step procedures for performing tasks, which is essential for optimizing code.
Understanding these concepts is vital for technical interviews and competitive programming.

what examples does reema thareja use in data structures and algorithms

In Data Structures and Algorithms by Reema Thareja, various real-world examples are used to illustrate concepts.

Examples include applications of trees in file systems and graphs in social networks.
Sorting algorithms are demonstrated using practical scenarios like organizing data in databases.
Data structures are explained through common applications such as stacks in expression evaluation and queues in task scheduling.

how to implement a binary search tree according to reema thareja

Reema Thareja outlines the implementation of a binary search tree (BST) in a clear manner.

Start by defining a node structure with left and right child pointers.
Implement insertion by comparing the new value with existing nodes to find the correct position.
For deletion, consider three cases: deleting a leaf node, a node with one child, and a node with two children.
Traversal methods such as in-order, pre-order, and post-order are also discussed.

what are the advantages of using linked lists in data structures

Linked lists offer several advantages in data structures as highlighted by Reema Thareja.

Dynamic size: Unlike arrays, linked lists can grow and shrink in size as needed.
Efficient insertions and deletions: Adding or removing nodes does not require shifting elements.
Memory utilization: Linked lists can utilize memory more efficiently, especially for sparse data.
Flexibility: They allow for complex data structures like stacks and queues to be implemented easily.

what sorting techniques are covered in data structures and algorithms by reema thareja

Data Structures and Algorithms by Reema Thareja covers a variety of sorting techniques.

Basic sorting algorithms: bubble sort, selection sort, and insertion sort.
Advanced sorting algorithms: quick sort and merge sort.
Specialized sorting: radix sort and its applications.
Each technique is explained with time complexity analysis and practical examples.

how does reema thareja define algorithms in her textbook

Reema Thareja defines algorithms as step-by-step procedures for solving problems.

She emphasizes the importance of efficiency and clarity in algorithm design.
Algorithms are categorized based on their approach, such as greedy algorithms and dynamic programming.
Examples illustrate how algorithms can be applied to real-world problems.

what is the role of recursion in data structures according to reema thareja

Recursion plays a significant role in data structures as explained by Reema Thareja.

It simplifies the implementation of algorithms for tasks like tree traversals and backtracking.
Recursion helps in breaking down complex problems into simpler subproblems.
Examples in the textbook demonstrate how recursion can be effectively used in sorting and searching algorithms.