CLASS NOTES [DATA STRUCTURES]
What is algorithm?
An algorithm is a step-by-step procedure or a set of instructions that are followed to solve a problem or
perform a specific task.
An algorithm should have the following characteristics −
1. Correctness: An algorithm should be designed to produce the correct output for a given input.
2. Efficiency: An algorithm should be designed to perform the task it is intended to solve in
a reasonable amount of time and with minimal resources.
3. Clarity: Algorithm should be clear and unambiguous. An algorithm should be designed to
be easy to understand and read by humans.
4. Modularity: An algorithm should be designed to be modular, meaning it can be broken
down into smaller, more manageable components.
5. Robustness: An algorithm should be designed to handle unexpected or invalid inputs, such
as incorrect data types or values.
6. Scalability: An algorithm should be designed to handle larger or more complex inputs
without sacrificing efficiency or correctness.
Advantages and Disadvantages of Algorithm
Advantages of Algorithms
1. Consistency: Algorithms provide a consistent approach to solving a problem. By
following a set of predefined steps, an algorithm ensures that the same result will be
obtained every time the same input is given.
2. Efficiency: Algorithms can be designed to solve problems in an efficient manner, using
the least amount of resources possible. This can be particularly important when dealing
with large data sets or complex computations.
3. Reusability: Algorithms can be reused in different applications or modified to solve
related problems. This can save time and effort in the development process, as well as
improve the quality of the solution.
4. Accuracy: Algorithms can be designed to produce accurate and reliable results, without
human error or bias. This is particularly important in applications that require high precision
or where mistakes could have serious consequences.
5. Debugging: Algorithms can be easier to debug than other types of code, as they typically
follow a clear and structured sequence of steps. This can make it easier to identify and fix
errors or bugs in the code.
6. Scalability: Algorithms can be designed to handle large or complex inputs, making them
suitable for applications that need to process large amounts of data or perform complex
computations.
Disadvantages of Algorithms
1. Complexity: Some algorithms can be very complex, which can make them difficult to
understand and modify. This can increase the time and effort required to develop,
test, and maintain the code.
2. Limitations: Algorithms are designed to solve specific types of problems, and they may
not be suitable for all situations. If the problem is too complex or does not fit the
algorithmic approach, it may be necessary to develop a new algorithm or use a
different approach.
3. Overfitting: Algorithms can be overfitted to specific data sets or situations, which
can limit their ability to generalize to other situations. This can result in solutions
that are overly specialized and not useful in broader contexts.
4. Error-prone: Like any code, algorithms can contain errors or bugs that can lead to
unexpected or incorrect results. This can be particularly problematic if the algorithm
is used in critical applications, such as in medical or financial systems.
5. Difficulty of optimization: While algorithms can be designed to be efficient,
optimizing them for performance can be a complex and time-consuming task. It
may require specialized knowledge and tools to achieve optimal performance.
How to Write an Algorithm?
1. Understand the problem: Before writing an algorithm, it is important to have a
clear understanding of the problem that needs to be solved. This involves analyzing
the inputs, outputs, and constraints of the problem, as well as any assumptions or
special cases that need to be considered.
2. Define the problem in terms of inputs and outputs: Based on the understanding of
the problem, define the inputs and outputs of the algorithm. This will help in
determining the logic and steps required to solve the problem.
3. Design a plan: The next step is to design a plan or outline for the algorithm. This
plan should define the sequence of steps required to solve the problem and the
logic involved in each step. Flowcharts, pseudocode, or other visual aids can be
helpful in designing the plan.
4. Write the code: Based on the plan or outline, write the actual code for the
algorithm. This code should be written in a structured and readable manner, with
comments and documentation to make it easy to understand and maintain.
5. Test the algorithm: After writing the code, test the algorithm with different inputs
and scenarios to ensure that it is working correctly. This involves running the
algorithm with various input values and comparing the output to the expected
results.
6. Optimize the algorithm: Finally, optimize the algorithm for performance and
efficiency. This may involve analyzing the code and identifying areas where it can be
improved, such as by reducing the number of steps or optimizing the use of
resources.
Here's a simple example of an algorithm to find the largest number in a list of
integers: Input: a list of integers
Output: the largest integer in the list
Algorithm:
Step1: Set a variable called "largest" to the first integer in the list.
Step2: Loop through each integer in the list, starting from the second integer. Step3: If the
current integer is larger than the "largest" variable, update the "largest" variable to be the
current integer.
Step4: When the loop is finished, the "largest" variable will contain the largest integer in the
list. Step5: Return the "largest" variable as the output.
For example, if the input list is [5, 3, 8, 2, 7], the algorithm would find that the largest integer
is 8 and return it as the output.
Algorithm Complexity:
What is algorithm complexity?
Algorithm complexity is a way of measuring how much time and/or space an algorithm
requires to solve a problem, as the size of the problem input grows. In simpler terms,
it's a measure of how efficient an algorithm is.
The time complexity of an algorithm refers to the amount of time it takes to run the
algorithm, and is often expressed as a function of the size of the input.
The space complexity of an algorithm refers to the amount of memory it requires to run
the algorithm, and is also often expressed as a function of the size of the input.
Suppose, an algorithm (A) and the size of input data (n), the time and space used by
the algorithm A are the two main factors, which decide the efficiency of A.
Time Factor − Time is measured by counting the number of key operations such as
comparisons in the sorting algorithm. The space required by an algorithm is equal to the sum
of the following two components : 1) A fixed part that is a space required to store certain
data and variables, that are independent of the size of the problem. 2) A variable part is a
space required by variables, whose size depends on the size of the problem. For example,
dynamic memory allocation.
Space Factor − Space is measured by counting the maximum memory space required by
the algorithm.
The complexity of an algorithm f(n) gives the running time and/or the storage space
required by the algorithm given n (the size of input data).
Example: A simple example of calculating the time and space complexity of finding
the maximum value in an array of n integers.
Algorithm:
1. Set max_value = array[0]
2. Loop through the array from index 1 to n-1
a. If array[i] > max_value,
b. set max_value = array[i]
3. Return max_value
Time Complexity Calculation:
∙ Step 1 takes constant time, O(1).
∙ Step 2 takes n-1 iterations, so its time complexity is O(n).
∙ Step 3 takes constant time, O(1).
Therefore, the total time complexity of the algorithm is O(n).
Space Complexity Calculation:
∙ We only need to store the value of max_value, which is a constant space, O(1).
Therefore, the space complexity of the algorithm is also O(1).
In summary, the time complexity of this algorithm is linear with the size of the input array
(n), while the space complexity is constant regardless of the size of the input array.
ALGORITHM ANALYSIS:
Efficiency of an algorithm can be analyzed at two different stages, 1) before
implementation and 2) after implementation.
A Priori Analysis or Performance or Asymptotic Analysis (before implementation) −
This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured
by assuming
that all other factors, for example, processor speed, are constant and have no
effect on the implementation.
A Posterior Analysis or Performance Measurement ( after implementation) − This is an
empirical analysis of an algorithm. The selected algorithm is implemented using
programming language. This is then executed on target computer machine.
Types of Analysis
The efficiency of some algorithms may vary for inputs of the same size. For such
algorithms, we need to differentiate between the worst case, average case and best
case efficiencies.
Best Case Analysis: If an algorithm takes the least amount of time to execute a
specific set of input, then it is called the best case time complexity.
Average Case Analysis : If the time complexity of an algorithm for certain sets of inputs
are on an average, then such a time complexity is called average case time
complexity.
Worst Case Analysis: If an algorithm takes maximum amount of time to execute for a
specific set of input, then it is called the worst case time complexity.
