Data Structure and Algorithms(DSA-1)
DATA STRUCTURE OPERATIONS
- This section goes over the various operations that can be done on the various data structures mentioned earlier.
Traversing:
- It means basically accessing each data item once in order to process it. To print the names of all the students in a class, for example.
Searching:
- It is used to locate one or more data items that satisfy the specified constraint. This data item may or may not be present in the supplied data item collection. To get the names of all the students who received a perfect score in mathematics, for example.
Inserting
- It’s used to add additional data items to an existing data set.For example, to enter the information of a new student who has recently enrolled in the course.
Deleting
- It refers to the act of removing (deleting) a specific data item from a group of data items. For instance, to remove the name of a student who has dropped out of the class.
Sorting
- Depending on the type of application, data elements can be ordered in many ways, such as ascending or descending order. For example, organising the names of students in a class alphabetically, or calculating the top three winners by descending the participants’ scores and then removing the top three.
Merging
- Lists of two sorted data items can be combined to form a single list of sorted data itemsMany a time, two or more operations are applied simultaneously in a given situation. For example, if we want to delete the details of a student whose name is X, then we first have to search the list of students to find whether the record of X exists or not and if it exists then at which location, so that the details can be deleted from that particular location.
ABSTRACT DATA TYPE
- An abstract data type (ADT) is a way of looking at a data structure in which we focus on what it does rather than how it does it. Stacks and queues, for example, are excellent examples of ADTs. Both of these ADTs can be implemented using an array or a linked list. This exemplifies the ‘abstract’ nature of queues and stacks.
The Benefits of Using ADTs
Programs evolve in the real world as a result of new requirements or limitations, therefore modifying a programme usually necessitates a change in one or more of its data structures. For instance, if you want to add a new field to a student’s record so that you can keep track of more information about each student, you can do so, then it will be better to replace an array with a linked structure to improve the program’s efficiency.
ALGORITHMS
Algorithms are typically characterised as “a formally stated technique for executing some calculation.” A formal language can be used to implement a procedure that has been formally defined, and such a language is known as a programming language. An algorithm, in general, is a blueprint for writing a software to solve a certain problem. It is thought to be a useful method for addressing a problem in a finite number of stages. That is, a well-defined algorithm will always provide a result and will always terminate. Algorithms are primarily used to reuse software. Once we have a solution idea or design, we may develop it in any high-level language such as Java, python, c & c++.
It is not uncommon to have multiple algorithms to tackle the same problem, but the choice of a particular algorithm must depend on the time and space complexity of the algorithm
APPROACHES TO ALGORITHM DESIGN
Data structures hold data that is manipulated using algorithms. Algorithms are used to operate on stored data when working with data structures. A complex algorithm is frequently broken down into smaller parts. Modularization refers to the process of breaking down an algorithm into components. The following are the primary benefits of modularization:
- It simplifies the design
- implementation of a complicated algorithm.
- Each module can be created on its own basis.While designing one module, the complexities of other modules can be overlooked, resulting in more design clarity, which simplifies the whole algorithm’s implementation, debugging, testing, documentation, and maintenance.
The top-down and bottom-up approaches to algorithm design are the two basic methodologies.
- Top-down approach
- The complex algorithm is divided into one or more modules using a top-down design technique. These modules can be further dissected into one or more sub-modules, and the decomposition process can be repeated until the required level of module complexity is reached. The top-down design process is a type of stepwise refinement in which we start with the topmost module and add modules to it sequentially. As a result, in a top-down method, we begin with an abstract design and refine it into more concrete layers at each step until we reach a point where no further refinement is required.
- Bottom-up approach
- A bottom-up strategy is the exact opposite of a top-down strategy. In a bottom-up design approach, we start with the most basic or concrete modules and work our way up to higher level modules. The activities performed by lower level modules are used to implement higher level modules. As a result, sub-modules are brought together to form a higher level in this technique.
All the higher level modules are clubbed together to form even higher level modules. This process is repeated until the design of the complete algorithm is obtained
Top-down vs bottom-up approach
Whether a top-down or bottom-up approach should be used is an issue that can be answered based on the application. The top-down technique decomposes the algorithm into manageable modules step by step, whereas the bottom-up approach specifies a module and then links together numerous modules to construct a new higher level module. The top-down approach is preferred because it makes documenting modules, creating test cases, implementing code, and debugging much easier.
However, it has been criticised because the sub-modules are examined in isolation, with little attention paid to their communication with other modules or component reusability.
Although the bottom-up approach allows for information hiding since it first identifies what needs to be contained within a module and then offers an abstract interface to define the module’s boundaries as perceived by clients, the bottom-up approach allows for information hiding. All of this, however, is impossible to achieve with a strict bottom-up approach. For this, several top-down activities are required. Overall, the design of complicated algorithms should be a combination of top-down and bottom-up approaches, rather than following a strict pattern.
ALGORITHMS USE CONTROL STRUCTURES
There are several steps in an algorithm. Decisions and repetition could be required for some steps.
An algorithm may use one of the control structures listed below in general:
- sequence
- decision
- repetition
- Sequence
By sequence, we mean that each step of an algorithm is
executed in a specified order. Let us write an algorithm to
add two numbers. - Example
Step 1: Input first number as A
Step 2: Input second number as B
Step 3: SET SUM = A+B
Step 4: PRINT SUM
Step 5: END
- Decision
When the execution of a process is contingent on the conclusion of a condition, decision statements are applied. If x = y, for example, display EQUAL. As a result, the general form of the IF construct is:
IF situation Then proceed with the procedure.
Any statement that can evaluate to either a true or false value is referred to as a condition in this context.
A variable x can be equal to y or not equal to y in the example above. It cannot, however, be both true and false. The process is started if the condition is true.A decision statement can also be stated in the following manner:
IF condition
Then process1
ELSE process2
This form is popularly known as the IF–ELSE construct. Here, if the condition is true, then process1
is executed, else process2 is executed. - Example
Step 1: Input first number as A
Step 2: Input second number as B
Step 3: IF A=B
PRINT “EQUAL”
ELSE
PRINT “NOT EQUAL”
[END OF IF]
Step 4: END
- Repetition
Repetition, which involves executing one or more steps for a number of times, can be implemented
using constructs such as while, do–while, and for loops. These loops execute one or more steps
until some condition is true. - Example
Step 1: (INITIALIZE) SET I=1, N=10
Step 2: Repeat steps 3 & 4 while I<=N
step 3: PRINT I
step 4: SET I=I+1
[END OF LOOP]
Step 5: END
Examples of Algorithms
Step 1: Input first number as A
Step 2: Input second number as B
Step 3: SET TEMP = A
Step 4: SET A = B
Step 5: SET B = TEMP
Step 6: PRINT A, B
Step 7: END
Step 1: Input first number as A
Step 2: Input second number as B
Step 3: IF A>B
PRINT A
ELSE
IF A<B
PRINT B
ELSE
PRINT “The numbers are equal”
[END OF IF]
[END OF IF]
Step 4: END
Step 1: Input number as A
Step 2: IF A%2 =0
PRINT “EVEN”
ELSE
PRINT “ODD”
[END OF IF]
Step 3: END
Step 1: Enter the Marks obtained as M
Step 2: IF M>75
PRINT O
Step 3: IF M>=60 AND M<75
PRINT A
Step 4: IF M>=50 AND M<60
PRINT B
Step 5: IF M>=40 AND M<50
PRINT C
ELSE
PRINT D
[END OF IF]
Step 6: END
Step 1: Input N
Step 2: SET I = 1, SUM = 0
Step 3: Repeat Step 4 while I <= N
Step 4: SET SUM = SUM + I
SET I = I + 1
[END OF LOOP]
Step 5: PRINT SUM
Step 6: END
