These notes on Data Structures are a comprehensive and valuable resource for any student looking to deepen their understanding of the subject. The notes cover a wide range of topics, from basic concepts like arrays and linked lists to more advanced topics like trees and graphs. They are well-organi...
, 1. What is data structure? Explain categories in which data structure can be divided.
The data structure is a way of storing data in a computer’s memory so that it can be used efficiently. It is a
logical/mathematical model of the organization of data. Categories in which data structure can be divided are mentioned
below:
a. Linear Data Structure: Elements in linear data structure from linear sequence.
b. Non-Linear Data Structure: Elements in non-linear data structure do not from any linear sequence.
c. Static Data Structure: In static data structure size of the structure is fixed. The content of the data structure can be
modified without changing the memory space allocated to it.
d. Dynamic Data Structure: In Dynamic data structure size of the structure is not fixed and can be modified during
operations performed on it. Dynamic data structures are designed to facilitate change of data structures in run time.
e. Homogenous Data Structure: Homogeneous data structures are those structures that contain only similar types of
data—for example: like data structures containing only float and integer values. The simplest example is an array.
f. Non-Homogenous Data Structure: Non-heterogeneous data structures are those structures that contain a variety of
different types of data.
2. List and explain different operations that can be performed on the data structure
Insertion: Adding a new element into a data structure is known as insertion.
Deletion: Removing an element from the data structure is known as deletion.
Traversing: Accessing each element exactly once to process it is known as traversing.
Searching: Finding the position of the desired element in the data structure is known as searching.
Merging: Combining two or more lists into a single list is merging.
Splitting: Dividing a single list into two or more lists is a splitting operation.
Copying: Creating a duplicate copy of a list is known as a copy operation.
Sorting: Arranging elements in ascending or descending order is known as sorting.
3. What is an algorithm? what are the characteristics of the algorithm?
The algorithm can be defined as a finite collection of well-defined steps designed to solve a particular problem.
Characteristics:
a. Input: The algorithm must take some inputs that are required for the solution of the problem.
b. Process: The algorithm must perform certain operations on input data that are necessary for the solution of the
problem.
c. Output: The algorithm should produce a certain output after processing inputs.
d. Finiteness: The algorithm must terminate after executing a certain finite number of steps.
e. Effectiveness: Every step of the algorithm should play a role in the solution to the problem
4. What is the importance of algorithm analysis?
By considering algorithms for specific problems, we can begin to develop pattern recognition so that similar types of
problems can be solved with the help of this algorithm. Algorithms are often quite different from one another, though the
objectives of these algorithms are the same. For example, we know that a set of numbers can be sorted using different
algorithms. A number of comparisons performed by one algorithm may vary with others for the same input. Hence, the
time complexity of those algorithms may differ. At the same time, we need to calculate the memory space required by
each algorithm. Analysis of the algorithm is the process of analyzing the problem-solving capability of the algorithm in
terms of time and size required. However, the main concern of the analysis of algorithms is the required time or
performance. Generally, we perform the following types of analysis:
Worst-case: Maximum number of steps taken on any instance of size
Best-case: Minimum number of steps taken on any instance of size
Average case: Average number of steps taken on any instance of size
Amortized: Sequence of operations applied to the input of size averaged over time.
To solve the problem, we need to consider time as well as space complexity as the program may run on a system where
memory is limited but adequate space is available or maybe vice-versa. In this context, if we compare bubble sort and
merge sort. Bubble sort does not require additional memory, but merge sort requires additional space. Though the time
complexity of bubble sort is higher compared to merge sort, we may need to apply bubble sort if the program needs to
run in an environment, where memory is very limited.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller sushanttare. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.49. You're not tied to anything after your purchase.
