UNIT 1-ALGORITHM
What is an algorithm?
• Algorithm can be defined as: “A finite step by step list of well defined-instructions
for solving a particular problem.” .
• There may be more than one way to solve a problem, so there may be more than one
algorithm for a problem.
• An algorithm can also be defined as: “A sequence of activities to be processed for
getting desired output from a given input.”
• Achieving the specified output is crucial once the algorithm is executed. For this to
happen, the algorithm must terminate after a finite amount of time.
• Additionally, the steps within the algorithm must be clearly defined to ensure that it is
unambiguous.
Different approaches to designing an algorithm
• In the context of data structures, there are two fundamental approaches used for
designing algorithms:
1. Top -down approach
2. Bottom -up approach
1. Top-down approach:
▪ The process begins by dividing the complex algorithm into one or more high-level
modules
▪ Each module can be further broken down into smaller sub-modules, and this
decomposition continues until the desired level of complexity is reached.
▪ This method follows a stepwise refinement approach, where we start with the topmost
module and incrementally add the modules it calls.
▪ We begin with an abstract design and refine it at each step, gradually turning it into more
concrete levels.
▪ The process continues until a point is reached where no further refinement is needed, and
the sub-modules are simple enough to be implemented.
Different approaches to designing an algorithm contd..
▪ Example of Top-Down Approach:
▪ In recursive algorithms like Merge Sort or Quick Sort, we start
by dividing the problem into smaller parts and solving them
step by step.
▪ Applications:
▪ Typically used in recursive algorithms, where we divide the
problem into sub-problems and solve them individually (e.g.,
Tree Traversals, Divide and Conquer algorithms).
Different approaches to designing an algorithm
2. Bottom-Up Approach:
▪ In the bottom-up approach, the process starts by designing the most basic or concrete
modules.
▪ After designing the basic modules, we proceed towards designing higher-level
modules.
▪ Higher-level modules are implemented using the operations performed by the lower-
level modules.
▪ Sub-modules are grouped together to form a higher-level module.
▪ All higher-level modules are combined to form even higher-level modules.
▪ This process is repeated until the complete design of the algorithm is obtained.
Different approaches to designing an algorithm contd..
▪ Example of Bottom-Up Approach:
▪ In Dynamic Programming (e.g., Fibonacci sequence), we start
with the base cases and build up to the final solution by solving
smaller sub-problems iteratively.
▪ Applications:
• The bottom-up approach is commonly used in iterative
algorithms and Dynamic Programming, where the solution is built
step by step by solving smaller sub-problems first.
Top-down vs bottom-up approach
Top-Down Approach Bottom-Up Approach
Follows stepwise refinement by breaking the algorithm into Defines basic modules first, then groups them to form higher-
smaller, manageable modules. level modules.
Appreciated for ease in documenting modules, generating Allows information hiding by identifying what to encapsulate
test cases, implementing code, and debugging. within a module and defining abstract interfaces.
Criticized for analyzing sub-modules in isolation without Can be challenging to implement strictly, as some top-down
focusing on their communication or reusability. activities are needed for defining interfaces.
Little attention is given to data, leading to a lack of focus on Provides abstract module boundaries, but strict bottom-up
information hiding. strategy can be hard to follow.
Best suited for designing complex problems through Useful for building modular systems that focus on
decomposition and refinement. encapsulation and information hiding.
Focuses on top-level design and refines it progressively into Focuses on creating simple, basic components first and then
smaller components. integrates them into a complete system.
Requires more attention to how modules communicate and Better suited for situations where modularity and abstract
interact with each other. interfaces are a priority.