Algorithms Study Guide - Complete Syllabus

Coverage

Author: Manus AI

Date: January 8, 2025

Purpose: Comprehensive exam preparation covering all topics with detailed explanations

Table of Contents
1. UNIT-I: Introduction and Fundamentals
2. UNIT-II: Divide-and-Conquer
3. UNIT-III: Greedy Method and Traversal Techniques
4. UNIT-IV: Dynamic Programming and Backtracking
5. UNIT-V: Advanced Topics

UNIT-I: Introduction and Fundamentals

What is an Algorithm?
An algorithm is a step-by-step procedure or set of rules designed to solve a specific problem
or perform a particular task. Think of it as a recipe that tells you exactly what to do, in what
order, to achieve a desired result. Just like a cooking recipe has ingredients and steps, an
algorithm has inputs and a sequence of operations.
Key Characteristics of Algorithms
Every algorithm must have five important properties that make it effective and reliable:
Finiteness: An algorithm must always terminate after a finite number of steps. It cannot run
forever. For example, when searching for a number in a list, the algorithm must eventually
either find the number or conclude that it's not there.
Definiteness: Each step of the algorithm must be precisely defined and unambiguous.
There should be no confusion about what needs to be done at each step. The instructions
should be clear enough that anyone following them would perform the same actions.
Input: An algorithm should have zero or more inputs. These are the data or values that the
algorithm works with. For instance, a sorting algorithm takes a list of numbers as input.
Output: An algorithm must produce at least one output. This is the result or solution that
the algorithm generates. Using the sorting example, the output would be the sorted list of
numbers.
Effectiveness: Each step of the algorithm must be basic enough to be carried out by a
person using paper and pencil. The operations should be simple and executable.
Types of Algorithms
Algorithms can be classified into several categories based on their approach and purpose:
Sequential Algorithms: These algorithms execute one step after another in a linear fashion.
Most basic algorithms fall into this category, such as simple searching or basic arithmetic
operations.
Parallel Algorithms: These algorithms can perform multiple operations simultaneously,
taking advantage of multiple processors or cores. They are designed to solve problems
faster by dividing the work among different processing units.
Deterministic Algorithms: These algorithms always produce the same output for the same
input. Every step is predetermined, and there's no randomness involved. Traditional sorting
algorithms like bubble sort are deterministic.
Randomized Algorithms: These algorithms make random choices during their execution.
They might produce different outputs for the same input, but they often provide good
average-case performance. Examples include randomized quicksort and Monte Carlo
methods.
Algorithm Representation
Algorithms can be represented in various ways, each serving different purposes:
Natural Language: Describing the algorithm in plain English or any spoken language. This
is good for understanding but can be ambiguous.
Pseudocode: A high-level description that uses programming-like syntax but is
independent of any specific programming language. It's more precise than natural language
but easier to understand than actual code.
Flowcharts: Visual representations using symbols and arrows to show the flow of the
algorithm. They're excellent for understanding the logic and decision points.
Programming Language: The actual implementation of the algorithm in a specific
programming language like C, Java, or Python.
Importance of Algorithms
Algorithms are fundamental to computer science and have practical applications in every
aspect of computing. They help us solve complex problems efficiently and systematically.
Without algorithms, computers would be unable to perform even the simplest tasks. From
the moment you wake up and check your phone to when you use GPS navigation or search
the internet, algorithms are working behind the scenes to make these technologies
possible.
In the business world, algorithms help companies optimize their operations, from managing
supply chains to recommending products to customers. In science and engineering,
algorithms help researchers analyze data, simulate complex systems, and make discoveries.
Understanding algorithms is essential for anyone working with computers or data, as it
provides the foundation for solving problems systematically and efficiently.
Algorithm Specification
Algorithm specification is the process of clearly defining and describing an algorithm in a
formal or semi-formal manner. It involves documenting the algorithm's purpose, inputs,
outputs, and the exact steps needed to solve the problem. Proper specification is crucial
because it ensures that the algorithm can be understood, implemented, and verified
correctly.
Components of Algorithm Specification
Problem Statement: This is a clear description of what problem the algorithm is supposed
to solve. It should specify the conditions under which the algorithm operates and what
constitutes a valid solution. For example, "Sort a list of integers in ascending order" is a
clear problem statement.
Input Specification: This describes the data that the algorithm receives as input. It should
specify the type, format, and any constraints on the input data. For instance, "Input: An
array A of n integers where n ≥ 1" clearly defines what the algorithm expects to receive.
Output Specification: This describes what the algorithm produces as output. It should
specify the format and properties of the output. Continuing the sorting example, "Output:
The same array A with elements arranged in non-decreasing order" clearly states what the
algorithm should produce.
Preconditions: These are conditions that must be true before the algorithm starts
executing. They specify assumptions about the input or the environment. For example, "The
input array must not be null" is a precondition.
Postconditions: These are conditions that will be true after the algorithm completes
successfully. They describe the relationship between input and output. For the sorting
algorithm, a postcondition might be "For all i, 0 ≤ i < n-1, A[i] ≤ A[i+1]."
Specification Methods
Formal Specification: This uses mathematical notation and logic to precisely define the
algorithm. It's unambiguous but can be difficult to understand for those not familiar with
mathematical notation. Formal methods like Z notation or VDM (Vienna Development
Method) are used for critical systems where correctness is paramount.
Semi-formal Specification: This combines natural language with some formal elements
like pseudocode or mathematical expressions. It strikes a balance between precision and
readability. Most algorithm textbooks use this approach.
Informal Specification: This uses natural language to describe the algorithm. While easy to
understand, it can be ambiguous and may lead to different interpretations.
Pseudocode Conventions
Pseudocode is one of the most popular ways to specify algorithms because it's precise yet
readable. Here are common conventions used in pseudocode:
Assignment: Use ← or = to assign values to variables. For example, "x ← 5" means assign
the value 5 to variable x.
Control Structures: Use familiar programming constructs like if-then-else, while, for, and
repeat-until to control the flow of execution.
Comments: Use // or /* */ to add explanatory comments that don't affect the algorithm's
execution.
Indentation: Use consistent indentation to show the structure and nesting of control
statements.
Data Structures: Clearly specify how data is organized and accessed. For arrays, use A[i] to
access the i-th element.
Example: Binary Search Specification
Let's look at a complete specification for the binary search algorithm:
Problem Statement: Find the position of a target value in a sorted array, or determine that
the value is not present.
Input:
• An array A of n elements sorted in ascending order
 • A target value x to search for
• n ≥ 1 (the array is not empty)
Output:
• An integer index i such that A[i] = x, if x is found
• -1 if x is not found in the array
Preconditions:
• Array A is sorted in non-decreasing order
• n is the actual size of array A
Postconditions:
• If the algorithm returns i ≥ 0, then A[i] = x
• If the algorithm returns -1, then x is not present in A
This specification completely defines what the binary search algorithm should do, making it
possible for different programmers to implement it correctly and consistently.
Benefits of Proper Specification
Good algorithm specification provides several important benefits. It reduces ambiguity and
misunderstanding, making it easier for teams to work together on implementing the
algorithm. It serves as documentation that helps maintain and modify the algorithm later. It
enables verification and testing by providing clear criteria for correctness. It facilitates
communication between different stakeholders, including programmers, testers, and users.
Proper specification also helps in analyzing the algorithm's complexity and performance
characteristics. When the inputs and outputs are clearly defined, it becomes easier to
determine how the algorithm's running time and space requirements scale with input size.

Performance Analysis - Space Complexity

When we talk about the performance of an algorithm, we usually consider two main
aspects: how fast it runs (time complexity) and how much memory it uses (space
complexity). Space complexity is a measure of the amount of temporary storage an
algorithm needs to run to completion. It's about how much extra memory, beyond the input
itself, the algorithm requires.
Understanding Space Complexity
Space complexity is typically expressed using Big O notation, just like time complexity. It
describes the growth rate of the memory usage as the size of the input (n) increases. We are
interested in the auxiliary space, which is the extra space used by the algorithm during its
execution, not including the space taken by the input data itself. However, sometimes the
total space (input space + auxiliary space) is also considered.
Components of Space Complexity:
1. Instruction Space: This is the space required to store the compiled version of the
program instructions. This is usually fixed and doesn't change with input size, so it's
often ignored in Big O analysis. It's a constant amount of space.
2. Data Space: This includes:
• Constants: Fixed values used in the program (e.g., PI = 3.14 ). These take constant
space.
• Variables: Space for simple variables (e.g., int x , char c ). These also take constant
space.
• Arrays/Data Structures: Space for data structures like arrays, linked lists, trees, or
hash tables. The space taken by these can vary with the input size n .
• Dynamic Allocation: Space allocated during the program's execution (e.g., using
malloc or new ). This space also depends on the input size.
3. Environmental Stack Space: This is the space used for function calls, including return
addresses, local variables, and parameters for each function call. In recursive
algorithms, this can grow significantly with the depth of recursion.
Calculating Space Complexity
To calculate space complexity, we identify all variables and data structures that consume
memory and determine how their memory usage scales with the input size n .
Examples:
• Constant Space (O(1)): An algorithm that uses a fixed amount of memory regardless of
the input size. For example, a function that swaps two numbers only needs a few
variables to hold the numbers and a temporary variable for swapping. This space does
not grow with the input.
• Linear Space (O(n)): An algorithm whose memory usage grows linearly with the input
size. For example, if you need to create an auxiliary array of the same size as the input
array to store results, the space complexity would be O(n).
• Logarithmic Space (O(log n)): Algorithms that divide the problem into smaller
subproblems, often seen in recursive algorithms where the recursion depth is
logarithmic. For example, binary search uses O(log n) space due to the recursion stack.
• Quadratic Space (O(n^2)): Algorithms that use memory proportional to the square of
the input size. This often happens when dealing with 2D arrays or matrices where
dimensions depend on n .
Importance of Space Complexity
While time complexity often gets more attention, space complexity is equally important,
especially in environments with limited memory, such as embedded systems, mobile
devices, or large-scale data processing where memory can be a bottleneck.
Reasons why space complexity matters:
1. Resource Constraints: In systems with limited RAM, an algorithm with high space
complexity might not even run, or it might run very slowly due to excessive swapping
between RAM and disk (thrashing).
2. Scalability: For large inputs, an algorithm with high space complexity might quickly
exhaust available memory, making it impractical for real-world applications. An
algorithm that scales well in terms of space can handle larger datasets.
 3. Efficiency: Even if memory is abundant, excessive memory usage can lead to slower
execution times because accessing data from memory takes time, and larger memory
footprints can lead to more cache misses.
4. Cost: In cloud computing environments, memory usage directly translates to cost.
Optimizing space complexity can lead to significant cost savings.
Trade-offs Between Time and Space
Often, there's a trade-off between time complexity and space complexity. An algorithm
might be designed to run faster by using more memory (e.g., pre-calculating and storing
results in a lookup table), or it might use less memory at the cost of longer execution time
(e.g., re-calculating values instead of storing them). The choice depends on the specific
requirements and constraints of the problem.
For example, dynamic programming often uses extra space (a table) to store intermediate
results to avoid redundant calculations, thereby improving time complexity. Conversely,
some in-place sorting algorithms like Heap Sort achieve O(1) auxiliary space complexity but
might have a slightly higher time complexity constant factor compared to algorithms that
use O(n) auxiliary space like Merge Sort.
Understanding space complexity helps developers choose the most appropriate algorithm
for a given problem, considering both execution speed and memory footprint.

Performance Analysis - Time Complexity

Time complexity is a measure of how long an algorithm takes to run as a function of the size
of its input. It doesn't measure the actual time in seconds or minutes, because that can vary
depending on the computer's speed, programming language, and other factors. Instead, it
measures the number of elementary operations an algorithm performs. An elementary
operation is a basic computation that takes a fixed amount of time, like an arithmetic
operation (addition, subtraction), a comparison, an assignment, or accessing an element in
an array.
Why Time Complexity Matters
Understanding time complexity is crucial for several reasons:
1. Predicting Performance: It allows us to predict how an algorithm will behave for large
inputs without actually running it. This is especially important for large-scale data
processing.
2. Comparing Algorithms: It provides a standardized way to compare the efficiency of
different algorithms designed to solve the same problem. An algorithm with lower time
complexity is generally preferred for larger inputs.
3. Scalability: It helps determine how well an algorithm will scale as the input size grows.
An algorithm with a good time complexity will remain efficient even with very large
datasets.
How to Analyze Time Complexity
To analyze time complexity, we typically count the number of elementary operations
performed by an algorithm and express this count as a function of the input size, n . We
then use Asymptotic Notation (like Big O notation) to describe the growth rate of this
function, focusing on its behavior for very large n .
Steps to Analyze Time Complexity:
1. Identify Input Size: Determine what constitutes the 'input size' ( n ). For arrays, it's
usually the number of elements. For graphs, it might be the number of vertices or
edges.
2. Count Operations: Count the number of elementary operations performed by the
algorithm. This often involves looking at loops, recursive calls, and conditional
statements.
3. Express as a Function of n : Write the total count of operations as a mathematical
function T(n) .
4. Apply Asymptotic Notation: Simplify T(n) using Big O, Big Omega, or Big Theta
notation to represent its growth rate.
Common Time Complexities
Let's look at some common time complexities and what they mean:
• Constant Time (O(1)): The number of operations remains constant regardless of the
input size. This is the most efficient time complexity.
• Example: Accessing an element in an array by its index.
• Logarithmic Time (O(log n)): The number of operations grows very slowly as the input
size increases. Typically seen in algorithms that repeatedly divide the problem size in
half.
• Example: Binary Search.
• Linear Time (O(n)): The number of operations grows proportionally to the input size. If
the input doubles, the time taken roughly doubles.
• Example: Searching for an element in an unsorted array (linear search).
• Linearithmic Time (O(n log n)): The number of operations grows as n multiplied by
log n . This is common in efficient sorting algorithms.
• Example: Merge Sort, Quick Sort (average case).
• Quadratic Time (O(n^2)): The number of operations grows proportionally to the
square of the input size. Often seen in algorithms with nested loops where each loop
iterates n times.
• Example: Bubble Sort, Selection Sort, Insertion Sort.
• Cubic Time (O(n^3)): The number of operations grows proportionally to the cube of the
input size. Common in algorithms with three nested loops.
• Example: Matrix Multiplication of two n x n matrices.
• Exponential Time (O(2^n)): The number of operations doubles with each additional
element in the input. These algorithms are usually impractical for even moderately
sized inputs.
• Example: Finding all subsets of a set, solving the Traveling Salesperson Problem
using brute force.
 • Factorial Time (O(n!)): The number of operations grows extremely rapidly. These
algorithms are only feasible for very small inputs.
• Example: Generating all permutations of a list.

Best, Worst, and Average Case Analysis

For many algorithms, the time taken can vary depending on the specific input, even if the
input size n is the same. This leads to different types of time complexity analysis:
• Worst-Case Time Complexity: This is the maximum time an algorithm will take for any
input of a given size n . It provides an upper bound on the running time and is often
the most important for guarantees.
• Example: For linear search, the worst case is when the target element is at the very
end of the array or not present at all. This requires n comparisons, so O(n).
• Best-Case Time Complexity: This is the minimum time an algorithm will take for any
input of a given size n . It's often not very useful in practice because the best case
might be rare.
• Example: For linear search, the best case is when the target element is the first
element in the array. This requires only 1 comparison, so O(1).
• Average-Case Time Complexity: This is the average time an algorithm will take for a
typical input of a given size n . It requires making assumptions about the distribution
of inputs.
• Example: For linear search, on average, we might expect to find the element in the
middle of the array, requiring n/2 comparisons. This is still O(n).
When discussing time complexity, unless specified otherwise, it usually refers to the worst-
case time complexity, as it provides a guarantee on the algorithm's performance.
Space-Time Trade-off
As mentioned in space complexity, there's often a trade-off between time and space. An
algorithm can sometimes be made faster (better time complexity) by using more memory
(higher space complexity), or it can be made to use less memory (better space complexity)
at the cost of being slower (higher time complexity). The optimal choice depends on the
specific constraints and requirements of the problem you are trying to solve.
For instance, if you need to perform many lookups on a dataset, you might pre-process it
and store it in a hash table (which uses more space) to achieve O(1) average-case lookup
time. If memory is very limited, you might opt for a data structure that uses less space but
has a slower lookup time, like a sorted array with binary search (O(log n) time, O(1) auxiliary
space).
Understanding time complexity is fundamental to designing efficient algorithms and
choosing the right solution for a given computational problem. It allows developers to build
scalable and performant software systems.

Performance Analysis - Amortized Complexity

Amortized analysis is a method for analyzing the time complexity of a sequence of
operations, where the average cost of an operation is considered over a series of operations,
rather than focusing on the worst-case cost of a single operation. While a single operation
might be very expensive, if it happens rarely and is offset by many cheap operations, the
amortized cost per operation can be low.
Why Amortized Analysis?
Traditional worst-case analysis can sometimes be too pessimistic. For example, if an
operation takes O(n) time in the worst case but only O(1) time most of the time, and the O(n)
case happens very infrequently, then saying each operation is O(n) might not accurately
reflect the overall performance over a long sequence of operations. Amortized analysis
provides a more realistic average performance guarantee.
Key Concepts
Sequence of Operations: Amortized analysis always applies to a sequence of operations,
not just a single one.
Average Cost: It calculates the average cost per operation over the entire sequence.
Worst-Case for the Sequence: The result of an amortized analysis is a worst-case bound on
the total cost of a sequence of m operations. If the total cost is T(m) , then the amortized
cost per operation is T(m)/m .
Methods of Amortized Analysis
There are three main methods for performing amortized analysis:
1. Aggregate Method:
• Concept: This is the simplest method. You determine the total cost of a sequence of
m operations and then divide by m to get the amortized cost per operation.
• How it works: Calculate the total cost T(m) for m operations. The amortized cost
per operation is T(m) / m .
• Example: Dynamic Array (e.g., Python List, Java ArrayList)
Consider an array that doubles its size when it becomes full. Appending an element
usually takes O(1) time. However, when the array is full, appending requires creating
a new, larger array and copying all existing elements to it. If the array has k
elements, this copy operation takes O(k) time.
• Operations 1, 2, 3, ..., n .
• Doubling occurs at sizes 1, 2, 4, 8, ..., 2^k .
• The cost of copying when resizing from 2^(i-1) to 2^i is 2^(i-1) .
• Total cost for n operations (assuming n is a power of 2 for simplicity, say n =
2^k ):
Total Cost = (1) + (2) + (4) + ... + (n/2) + n (cost of copying) + n (cost of individual
appends)
Total Cost = (1 + 2 + 4 + ... + n/2) + n (copying) + n (appends)
The sum 1 + 2 + 4 + ... + n/2 is approximately n-1 .
So, Total Cost ≈ (n-1) + n = 2n - 1 .
• Therefore, the total cost for n operations is O(n).
 • The amortized cost per operation is O(n) / n = O(1) .
This shows that even though some append operations are expensive, the average
cost over a sequence of operations is constant.
2. Accounting Method (or Banker's Method):
• Concept: Assigns a specific
cost to each operation, some of which might be more than its actual cost. The excess cost is
stored as 'credit' and can be used to pay for future expensive operations.
* How it works: Each operation is assigned an amortized cost. If the actual cost is less than
the amortized cost, the difference is saved as credit. If the actual cost is more, the difference
is paid for by the accumulated credit. The total credit must never be negative.
* Example: Dynamic Array (e.g., Python List, Java ArrayList)
Let the amortized cost of an append operation be 3 units.
* When an element is appended to a non-full array, its actual cost is 1 unit. We charge 3
units, so 2 units of credit are saved.
* When the array is full and needs to be resized (doubled), say from size k to 2k :
* The actual cost is k (for copying k elements) + 1 (for appending the new element) =
k+1 .
* Where does the k cost come from? Each of the k elements that were previously
appended contributed 2 units of credit (total 2k credit). We use k of these credits to pay
for the copy operation.
* The remaining k credits are still available.
* Since we always have enough credit to pay for the expensive copy operations, and each
operation is charged a constant amortized cost (3 units), the total cost for n operations is
3n , which is O(n). Thus, the amortized cost per operation is O(1).
1. Potential Method (or Physicist's Method):
• Concept: This is the most formal method. It defines a 'potential function' that maps
the state of the data structure to a non-negative real number. The potential
represents the amount of 'prepaid work' that can be used for future operations.
• How it works: Let D_0 be the initial state of the data structure, and D_i be the
state after the i -th operation. Let c_i be the actual cost of the i -th operation, and
 Φ(D_i) be the potential function for state D_i . The amortized cost a_i of the i -th
operation is defined as:
a_i = c_i + Φ(D_i) - Φ(D_{i-1})
The total amortized cost for m operations is Σ a_i = Σ c_i + Φ(D_m) - Φ(D_0) .
If Φ(D_m) ≥ Φ(D_0) and Φ(D_i) ≥ 0 for all i , then Σ a_i ≥ Σ c_i . This means the total
amortized cost is an upper bound on the total actual cost.
• Example: Dynamic Array (e.g., Python List, Java ArrayList)
Let num be the number of elements in the array, and size be the current capacity
of the array.
Define the potential function Φ(D) = 2 * num - size .
• Initially, num = 0 , size = 0 (or some small initial capacity), so Φ(D_0) = 0 .
• When num <= size / 2 , Φ(D) is non-negative.
• Consider an append operation:
• Case 1: No resize. num increases by 1. size remains the same. Actual cost
c_i = 1 .
a_i = c_i + Φ(D_i) - Φ(D_{i-1}) = 1 + (2 * (num+1) - size) - (2 * num - size) = 1 + 2 = 3 .
• Case 2: Resize occurs. num increases by 1. size doubles from k to 2k .
Actual cost c_i = k + 1 (copy k elements, append 1).
Before resize: num = k , size = k . Φ(D_{i-1}) = 2k - k = k .
After resize: num = k+1 , size = 2k . Φ(D_i) = 2(k+1) - 2k = 2k + 2 - 2k = 2 .
a_i = c_i + Φ(D_i) - Φ(D_{i-1}) = (k+1) + 2 - k = 3 .
• In both cases, the amortized cost a_i is 3. Therefore, the total amortized cost for
n operations is 3n , which means the amortized cost per operation is O(1).

Applications of Amortized Analysis

Amortized analysis is particularly useful for analyzing data structures that occasionally
perform expensive operations to maintain their properties, but these expensive operations
are infrequent when averaged over a long sequence. Common applications include:
 • Dynamic Arrays: As seen in the example, append operations have an amortized O(1)
cost.
• Hash Tables: Operations like insertion and deletion have an amortized O(1) cost, even
with occasional rehashing (resizing the underlying array).
• Disjoint Set Union (DSU): Operations like union and find have a nearly constant
amortized time complexity (inverse Ackermann function).
• Splay Trees: Operations like insert , delete , and find have an amortized logarithmic
time complexity.
Advantages and Disadvantages
Advantages:
• More Realistic Performance Bounds: Provides a tighter and more accurate upper
bound on the average performance of an operation over a sequence, compared to a
simple worst-case analysis.
• Guaranteed Performance: Unlike average-case analysis (which relies on assumptions
about input distribution), amortized analysis provides a worst-case guarantee on the
total time for a sequence of operations.
• Useful for Data Structures: Particularly well-suited for analyzing data structures where
occasional expensive operations are necessary for overall efficiency.
Disadvantages:
• Not for Single Operations: It does not provide a guarantee for the worst-case time of a
single operation. If a single operation must always meet a strict time limit, amortized
analysis is not sufficient.
• Complexity: Can be more complex to perform than simple worst-case analysis,
especially the potential method, which requires finding a suitable potential function.
• Sequence Dependence: The analysis is valid only for a sequence of operations, not for
isolated operations.
In summary, amortized complexity provides a powerful tool for understanding the practical
performance of algorithms and data structures that exhibit occasional spikes in cost but
maintain overall efficiency over time. It helps in designing and choosing data structures that
perform well in real-world scenarios where operations are part of a continuous stream.

Performance Analysis - Asymptotic Notation (O, Ω, Ɵ)

Asymptotic notation is a mathematical tool used to describe the limiting behavior of a
function when the argument tends towards a particular value or infinity. In the context of
algorithms, it describes the performance (time or space) of an algorithm as the input size
( n ) grows very large. It allows us to classify algorithms based on their growth rates,
ignoring constant factors and lower-order terms, which become insignificant for large
inputs.
Why Asymptotic Notation?
• Machine Independence: It provides a way to analyze algorithm efficiency that is
independent of specific hardware, programming languages, or compilers. An algorithm
that is O(n) will generally perform better than an O(n^2) algorithm for large n ,
regardless of the machine.
• Focus on Growth Rate: It focuses on how the running time or space requirements grow
with the input size, which is crucial for understanding scalability.
• Simplification: It simplifies the analysis by ignoring less significant terms and constant
factors, making it easier to compare algorithms.
Types of Asymptotic Notation
There are three primary types of asymptotic notation:
1. Big O Notation (O): Upper Bound
• Definition: Big O notation describes the upper bound or the worst-case scenario of
an algorithm's running time. It tells us that an algorithm will take at most a certain
amount of time to complete.
 • Formal Definition: A function f(n) is O(g(n)) if there exist positive constants c
and n_0 such that 0 ≤ f(n) ≤ c * g(n) for all n ≥ n_0 .
• Meaning: g(n) is an asymptotic upper bound for f(n) . This means that for
sufficiently large n , f(n) will not grow faster than c * g(n) .
• Example: If an algorithm has a time complexity of T(n) = 3n^2 + 2n + 5 , we say T(n) is
O(n^2) . This is because for large n , the n^2 term dominates, and we can find
constants c and n_0 such that 3n^2 + 2n + 5 ≤ c * n^2 .
• Use Case: Most commonly used to describe the worst-case performance of an
algorithm, providing a guarantee that the algorithm will not exceed this time.
2. Big Omega Notation (Ω): Lower Bound
• Definition: Big Omega notation describes the lower bound or the best-case scenario
of an algorithm's running time. It tells us that an algorithm will take at least a certain
amount of time to complete.
• Formal Definition: A function f(n) is Ω(g(n)) if there exist positive constants c
and n_0 such that 0 ≤ c * g(n) ≤ f(n) for all n ≥ n_0 .
• Meaning: g(n) is an asymptotic lower bound for f(n) . This means that for
sufficiently large n , f(n) will grow at least as fast as c * g(n) .
• Example: If an algorithm takes T(n) = 3n^2 + 2n + 5 time, we can say T(n) is Ω(n^2) .
This is because for large n , 3n^2 + 2n + 5 will always be greater than or equal to c *
n^2 for some c .
• Use Case: Used to describe the best-case performance or to prove that an algorithm
cannot be faster than a certain bound.
3. Big Theta Notation (Ɵ): Tight Bound
• Definition: Big Theta notation describes the tight bound or the average-case
scenario of an algorithm's running time. It tells us that an algorithm's running time is
bounded both above and below by the same function, up to constant factors.
 • Formal Definition: A function f(n) is Ɵ(g(n)) if there exist positive constants c1 ,
c2 , and n_0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n_0 .
• Meaning: g(n) is an asymptotically tight bound for f(n) . This means that f(n)
grows at the same rate as g(n) .
• Relationship to O and Ω: If f(n) is Ɵ(g(n)) , then f(n) is both O(g(n)) and Ω(g(n)) .
Conversely, if f(n) is O(g(n)) and f(n) is Ω(g(n)) , then f(n) is Ɵ(g(n)) .
• Example: If an algorithm has a time complexity of T(n) = 3n^2 + 2n + 5 , we can say
T(n) is Ɵ(n^2) . This is because n^2 is both an upper and lower bound for T(n) .
• Use Case: Used when the best-case and worst-case complexities are the same, or
when describing the average-case performance if it's consistently within certain
bounds.
Properties of Asymptotic Notations
• Transitivity: If f(n) = O(g(n)) and g(n) = O(h(n)) , then f(n) = O(h(n)) .
• Reflexivity: f(n) = O(f(n)) , f(n) = Ω(f(n)) , f(n) = Ɵ(f(n)) .
• Symmetry: f(n) = Ɵ(g(n)) if and only if g(n) = Ɵ(f(n)) .
• Transpose Symmetry: f(n) = O(g(n)) if and only if g(n) = Ω(f(n)) .
Little O Notation (o) and Little Omega Notation (ω)
These are less commonly used than Big O, Big Omega, and Big Theta, but they provide
stricter bounds:
• Little O Notation (o): Strict Upper Bound
• Definition: f(n) is o(g(n)) if f(n) grows strictly slower than g(n) . This means lim
(n→∞) f(n)/g(n) = 0 .
• Meaning: f(n) becomes insignificant relative to g(n) as n approaches infinity.
• Example: 2n = o(n^2) because lim (n→∞) 2n/n^2 = 0 .
 • Little Omega Notation (ω): Strict Lower Bound
• Definition: f(n) is ω(g(n)) if f(n) grows strictly faster than g(n) . This means lim
(n→∞) f(n)/g(n) = ∞ .
• Meaning: f(n) becomes arbitrarily larger than g(n) as n approaches infinity.
• Example: n^2 = ω(n) because lim (n→∞) n^2/n = ∞ .

Hierarchy of Growth Rates

Understanding the common growth rates is essential for comparing algorithms:
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
Algorithms with lower growth rates are generally more efficient for large inputs. For
example, an O(n log n) algorithm will outperform an O(n^2) algorithm for sufficiently large
n , even if the O(n^2) algorithm has a smaller constant factor for small n .

Practical Implications
Asymptotic notation helps in making informed decisions about algorithm selection. When
designing software, especially for systems that handle large amounts of data, choosing an
algorithm with a better asymptotic complexity can lead to significant performance
improvements and better scalability. It allows developers to focus on the fundamental
efficiency of an algorithm rather than being distracted by minor implementation details or
hardware specifics. It's a powerful abstraction that helps computer scientists reason about
the ultimate limits and capabilities of computational solutions.

Practical Complexities
While asymptotic notation provides a powerful theoretical framework for analyzing
algorithm efficiency, it's important to understand that it describes the growth rate for very
large input sizes. In real-world scenarios, other factors, often referred to as 'practical
complexities,' can significantly influence an algorithm's actual performance. These factors
include constant factors, lower-order terms, hardware specifics, and implementation
details.
Beyond Asymptotic Analysis
Asymptotic notation (Big O, Omega, Theta) simplifies analysis by ignoring constant factors
and lower-order terms. For example, an algorithm with T(n) = 100n and another with T(n) =
2n are both O(n) . Theoretically, they have the same growth rate. However, in practice, the
second algorithm will be 50 times faster. Similarly, an algorithm with T(n) = 2n^2 + 1000n +
5000 is O(n^2) . For small n , the 1000n term might dominate, but for very large n , the
2n^2 term will eventually take over.
Key Practical Considerations:
1. Constant Factors: The hidden constant factor c in c * g(n) can be very large or very
small. An algorithm with a theoretically worse asymptotic complexity might outperform
one with a better asymptotic complexity for small input sizes if its constant factor is
significantly smaller.
• Example: A simple O(n^2) algorithm might be faster than a complex O(n log n)
algorithm for small n if the O(n log n) algorithm has a very large constant factor
due to overhead (e.g., complex data structures, function call overhead).
2. Lower-Order Terms: For small to medium input sizes, the lower-order terms in the
complexity function can have a noticeable impact. Asymptotic analysis focuses on the
dominant term, which only truly matters when n is extremely large.
• Example: T(n) = n^2 + 100n . For n=10 , T(10) = 100 + 1000 = 1100 . Here, the 100n term
is larger. For n=1000 , T(1000) = 1,000,000 + 100,000 = 1,100,000 . Here, n^2 dominates.
The crossover point where the dominant term takes over can be quite large.
3. Input Distribution: The actual performance of an algorithm can vary significantly
based on the characteristics of the input data. Best-case, worst-case, and average-case
analyses provide bounds, but real-world data might not conform to the assumptions of
average-case analysis.
• Example: Quicksort has an average-case time complexity of O(n log n) but a worst-
case of O(n^2) . If the input data is always sorted or nearly sorted (which can happen
in some practical scenarios), Quicksort might consistently hit its worst case unless
specific pivot selection strategies are used.
4. Hardware and System Architecture:
• Cache Performance: Modern CPUs have multiple levels of cache memory (L1, L2,
L3). Algorithms that exhibit good locality of reference (accessing data that is
physically close in memory) can perform much faster because data is retrieved from
faster cache rather than slower main memory.
• Memory Hierarchy: Accessing data from registers is fastest, followed by cache, then
main memory (RAM), and finally disk (SSD/HDD). An algorithm that minimizes disk
I/O and maximizes cache hits will be faster in practice.
• Parallelism: The ability of an algorithm to be parallelized and run on multiple cores
or processors can drastically reduce wall-clock time, even if its sequential asymptotic
complexity is higher.
• Instruction Set Architecture: Different CPUs have different instruction sets. Some
operations might be faster on one architecture than another.
5. Programming Language and Compiler/Interpreter:
• Language Overhead: High-level languages (like Python) often have more overhead
than low-level languages (like C++). This can lead to larger constant factors.
• Compiler Optimizations: Optimizing compilers can significantly improve the
performance of compiled code by reordering instructions, eliminating dead code,
and making other improvements.
• Garbage Collection: Languages with automatic garbage collection (Java, Python,
C#) can introduce pauses during execution when the garbage collector runs, affecting
real-time performance.
6. Operating System and Environment:
• Context Switching: If an algorithm frequently interacts with the operating system
(e.g., file I/O, network operations), the overhead of context switching between the
application and the OS can impact performance.
• Resource Contention: Other processes running on the system can compete for CPU,
memory, and I/O resources, affecting the algorithm's observed performance.
 7. Data Structures and Libraries: The choice of underlying data structures and the
efficiency of library implementations can have a significant practical impact. Using a
highly optimized library function can often outperform a custom implementation, even
if both have the same asymptotic complexity.
Example of Practical vs. Asymptotic
Consider two sorting algorithms:
• Insertion Sort: O(n^2) worst-case, O(n) best-case. Very simple to implement, small
constant factors.
• Merge Sort: O(n log n) worst-case and average-case. More complex to implement,
larger constant factors due to recursion and merging overhead.
For very small arrays (e.g., n < 15-20 ), Insertion Sort often outperforms Merge Sort due to its
smaller constant factors and less overhead. However, as n grows, Merge Sort's superior
asymptotic complexity ( n log n vs. n^2 ) quickly makes it the faster choice. This is why
hybrid sorting algorithms (like Timsort, used in Python and Java) often switch to Insertion
Sort for small sub-arrays.
Conclusion on Practical Complexities
While asymptotic analysis is indispensable for understanding the scalability and
fundamental efficiency of algorithms, practical complexities remind us that real-world
performance is a nuanced issue. Developers must consider a holistic view, combining
theoretical understanding with empirical testing and an awareness of the specific hardware,
software, and data characteristics of their target environment. For critical applications,
profiling and benchmarking are essential to identify bottlenecks and optimize actual
performance, rather than relying solely on theoretical bounds. The goal is not just to find an
algorithm that is asymptotically optimal, but one that performs best under the given
practical constraints and typical input scenarios.

Performance Measurement
Performance measurement, also known as benchmarking or profiling, is the empirical
process of determining how an algorithm or program actually performs in a real-world
environment. Unlike theoretical analysis (like time and space complexity), which provides
abstract bounds, performance measurement gives concrete data on execution time,
memory usage, CPU cycles, and other metrics on a specific system with specific inputs. It
complements theoretical analysis by validating assumptions and identifying bottlenecks
that might not be apparent from asymptotic notation alone.
Why Measure Performance?
1. Validation of Theoretical Analysis: To confirm if the theoretical time and space
complexities hold true in practice, especially for large inputs.
2. Identification of Bottlenecks: To pinpoint specific parts of the code that consume the
most resources (time or memory), allowing for targeted optimization.
3. Comparison of Implementations: To compare different implementations of the same
algorithm or different algorithms for the same problem on a given hardware/software
stack.
4. Tuning and Optimization: To guide the process of fine-tuning parameters, optimizing
code, or choosing appropriate data structures for real-world scenarios.
5. Capacity Planning: To understand how a system will perform under expected loads
and to plan for future resource requirements.
6. Debugging Performance Issues: To diagnose and fix performance regressions or
unexpected slowdowns.
Key Metrics for Performance Measurement
• Execution Time (Wall-Clock Time/CPU Time):
• Wall-Clock Time: The total time elapsed from the start to the end of a program or
algorithm, as measured by a clock on the wall. This includes CPU time, I/O time, and
time spent waiting for other processes.
 • CPU Time: The actual time the CPU spends executing the program's instructions,
excluding time spent waiting for I/O or other processes. This is often a more accurate
measure of an algorithm's computational work.
• Memory Usage: The amount of RAM consumed by the program during its execution.
This can include heap memory, stack memory, and static memory.
• CPU Utilization: The percentage of time the CPU is busy executing instructions for the
program.
• I/O Operations: The number of read/write operations to disk or network, and the time
spent on these operations.
• Throughput: The number of operations or tasks completed per unit of time.
• Latency: The delay between a request and a response.
Tools and Techniques for Measurement
1. Timing Functions/Libraries: Most programming languages provide built-in functions
or libraries to measure execution time.
• Python: time module ( [Link]() , time.perf_counter() ), timeit module for precise
timing of small code snippets.
• C++/Java: std::chrono (C++), [Link]() (Java).
• Usage: Record the start time before the algorithm runs and the end time after it
completes. The difference is the execution time.
2. Profiling Tools: Profilers are sophisticated tools that analyze program execution to
identify where time and memory are being spent. They can show function call counts,
execution times for each function, and memory allocations.
• Python: cProfile , line_profiler , memory_profiler .
• Java: VisualVM, JProfiler, YourKit.
• C/C++: Gprof, Valgrind (for memory and performance analysis).
 • Operating System Tools: top , htop , perf (Linux), Activity Monitor (macOS), Task
Manager (Windows) provide system-wide resource usage.
3. Benchmarking Frameworks: These frameworks allow for systematic testing and
comparison of algorithms under various conditions.
• They often provide features for running tests multiple times, averaging results, and
generating reports.
Best Practices for Performance Measurement
1. Use Representative Data: Test with input data that is typical of real-world scenarios,
including edge cases and large datasets. Small inputs might not reveal the true
asymptotic behavior.
2. Run Multiple Trials: Execute the algorithm multiple times and average the results to
account for system noise, background processes, and cache effects. Discard outliers.
3. Warm-up Period: For languages with Just-In-Time (JIT) compilers (like Java) or systems
with caching, run the algorithm a few times before starting the actual measurement to
allow the system to warm up and caches to fill.
4. Isolate the Code: Measure only the part of the code you are interested in. Avoid
including setup, I/O, or other unrelated operations in your timing measurements unless
they are part of the algorithm being evaluated.
5. Control the Environment: Minimize background processes and other applications
running on the system during measurement to ensure consistent results.
6. Use High-Resolution Timers: Use timers that provide sufficient precision (e.g.,
nanoseconds) for accurate measurements, especially for very fast operations.
7. Consider Different Input Sizes: Measure performance across a range of input sizes to
observe how the algorithm scales and to validate its theoretical complexity class.
8. Profile, Don't Guess: Avoid making assumptions about where performance
bottlenecks lie. Use profiling tools to gather concrete evidence.
 9. Document Results: Keep detailed records of your measurements, including system
specifications, input data characteristics, and the exact code version used.
Limitations of Performance Measurement
• System Dependence: Results are specific to the hardware, operating system,
programming language, and compiler/interpreter used. They may not be transferable to
other environments.
• Input Dependence: Performance can vary greatly with different input datasets, even of
the same size.
• Measurement Overhead: The act of measuring performance can sometimes affect the
performance itself (e.g., profiling tools add overhead).
• Difficulty with Small Differences: It can be challenging to accurately measure and
distinguish between algorithms with very small performance differences, especially if
they are within the margin of measurement error.
In conclusion, performance measurement is an essential practical step in algorithm analysis
and optimization. While theoretical analysis provides a fundamental understanding of an
algorithm's efficiency, empirical measurement provides the real-world data needed to make
informed decisions about implementation, deployment, and optimization in specific
computational environments. It bridges the gap between theory and practice, ensuring that
algorithms not only scale well theoretically but also perform efficiently in actual use.

Randomized Algorithms: An Informal Description

Traditional algorithms are deterministic, meaning that for a given input, they will always
produce the same output and follow the same sequence of steps. Randomized algorithms,
on the other hand, make use of random choices (like flipping a coin or rolling a dice) during
their execution. This randomness can sometimes lead to better performance, simpler
algorithms, or the ability to solve problems that are difficult for deterministic algorithms.
How Randomness Helps
The introduction of randomness might seem counter-intuitive for an algorithm, as we
usually seek predictability. However, randomness can help in several ways:
1. Breaking Worst-Case Scenarios: Many deterministic algorithms have specific worst-
case inputs that cause them to perform very poorly. Randomization can often avoid
these worst-case inputs by making choices that are unlikely to align with any particular
bad input structure.
2. Simplicity: Sometimes, a randomized algorithm can be much simpler to design and
implement than its deterministic counterpart, even if the deterministic one is
theoretically faster.
3. Efficiency: For some problems, the fastest known algorithms are randomized. They can
achieve better average-case performance or even provide probabilistic guarantees on
correctness or running time.
4. Approximation: In some cases, randomized algorithms are used to find approximate
solutions to problems that are too hard to solve exactly.
Types of Randomized Algorithms
Randomized algorithms are broadly classified into two main types based on their
guarantees:
1. Las Vegas Algorithms:
• Guarantee: Always produce the correct output. The randomness affects only the
running time.
• Behavior: The running time is a random variable. In the worst case, it might run for a
very long time, but the expected (average) running time is usually good.
• Example: Randomized Quicksort. It always sorts the array correctly, but the time it
takes depends on the random pivot choices.
2. Monte Carlo Algorithms:
• Guarantee: Always run within a specified time bound. The randomness affects the
correctness of the output.
 • Behavior: There is a probability that the algorithm might produce an incorrect
output. The probability of error can often be reduced by running the algorithm
multiple times.
• Example: Primality Testing (like Miller-Rabin). It quickly tells you if a number is
composite, but if it says the number is prime, there's a small probability it might be
wrong.
Identifying the Repeated Element
Consider the problem of finding a repeated element in an array where one element appears
more than n/2 times (a majority element). A deterministic approach might involve sorting
the array (O(n log n)) or using a hash map (O(n) time, O(n) space). A simple randomized
approach can be very efficient.
Randomized Approach:
1. Pick a random element: Choose an index i uniformly at random from 0 to n-1 .
2. Check if it's the majority: Count how many times array[i] appears in the array.
3. If it's the majority, return it.
4. Repeat: If it's not the majority, repeat the process.
Why this works: Since the majority element appears more than n/2 times, the probability
of picking it in any single random draw is greater than 1/2 . If you repeat this process k
times, the probability of not picking the majority element in any of the k trials decreases
exponentially. For example, after 10 trials, the probability of not finding it is less than
(1/2)^10 = 1/1024 . This is a Monte Carlo algorithm if you set a fixed number of trials, or a Las
Vegas algorithm if you keep trying until you find it.
Primality Testing
Primality testing is the problem of determining whether a given number is prime (divisible
only by 1 and itself) or composite (has other divisors). For very large numbers, deterministic
primality tests can be computationally expensive. Randomized algorithms offer a much
faster, though probabilistic, solution.
Miller-Rabin Primality Test (Monte Carlo Algorithm):
This is one of the most widely used randomized primality tests. It works by checking a
property that all prime numbers satisfy. If a number n fails this property for a randomly
chosen base a , then n is definitely composite. If n passes the test for a , then n is
probably prime. The more times n passes the test with different random bases, the higher
the probability that n is indeed prime.
Informal Steps:
1. Input: A large integer n to test for primality, and a number k (number of iterations).
2. Decomposition: Write n-1 as 2^s * d , where d is an odd number.
3. Repeat k times:
a. Choose a random base a : Pick a random integer a such that 1 < a < n-1 .
b. Compute x = a^d mod n : If x = 1 or x = n-1 , then n passes this round of the test.
Continue to the next round.
c. Iterate s-1 times: For r from 1 to s-1 :
i. Compute x = x^2 mod n : If x = n-1 , then n passes this round. Continue to the next
round.
ii. If x = 1 (and it wasn't 1 in the previous step), then n is composite. Return
false (composite).
d. If none of the above conditions are met after all iterations, then n is composite.
Return false (composite).
4. If n passes all k rounds, then n is probably prime. Return true (probably prime).
Probability of Error: For each iteration, if n is composite, it will pass the test with
probability at most 1/4 . So, after k iterations, the probability that a composite number is
declared prime is at most (1/4)^k . This probability can be made arbitrarily small by
increasing k .
Advantages and Disadvantages of Randomized Algorithms
Advantages:
 1. Simplicity: Often, randomized algorithms are much simpler to understand, design, and
implement compared to their deterministic counterparts. This can lead to fewer bugs
and faster development times.
2. Efficiency (Average Case): For many problems, randomized algorithms offer
significantly better average-case performance than the best known deterministic
algorithms. They can often avoid the worst-case scenarios that plague deterministic
algorithms.
3. Breaking Worst-Case Inputs: Randomness can effectively
randomize the input, making it highly unlikely to encounter the specific input that causes a
deterministic algorithm to perform poorly. This is particularly useful in adversarial
scenarios.
4. Space Efficiency: Sometimes, randomized algorithms can achieve better time
complexity with less space compared to deterministic algorithms.
5. Solving Intractable Problems: For some problems where no efficient deterministic
algorithm is known, randomized algorithms can provide a practical solution, even if it
comes with a small probability of error.
6. Parallelism: Randomness can sometimes be exploited to design efficient parallel
algorithms.
Disadvantages:
1. Lack of Deterministic Guarantee (Monte Carlo): For Monte Carlo algorithms, there is a
non-zero probability of producing an incorrect result. While this probability can be
made very small, it might not be acceptable for applications requiring absolute
certainty (e.g., financial transactions, safety-critical systems).
2. Unpredictable Running Time (Las Vegas): For Las Vegas algorithms, the running time
is a random variable. While the expected running time might be good, there is always a
chance (though small) that the algorithm could take an extremely long time to
complete in a particular run.
3. Need for Good Random Number Generators: Randomized algorithms rely on high-
quality random number generators. Poor quality or predictable random numbers can
compromise the algorithm's effectiveness and security.
 4. Difficulty in Debugging: The non-deterministic nature of randomized algorithms can
make them harder to debug and test compared to deterministic ones, as the same input
might lead to different execution paths.
5. Theoretical vs. Practical: While theoretically powerful, the constant factors involved in
randomized algorithms might sometimes make them slower than simpler deterministic
algorithms for small input sizes.
Despite these disadvantages, randomized algorithms are a powerful tool in computer
science, widely used in areas like cryptography, network routing, machine learning, and
scientific simulations, where their advantages often outweigh their drawbacks.

Sets and Disjoint Set Union

Introduction to Sets
In mathematics and computer science, a set is a well-defined collection of distinct objects,
considered as an object in its own right. The objects within a set are called its elements or
members. Key characteristics of sets include:
• Unordered: The order of elements in a set does not matter. {1, 2, 3} is the same set as
{3, 1, 2} .
• Unique Elements: Each element in a set must be distinct. There are no duplicate
elements. If an element is listed multiple times, it is still considered only once.
Sets are fundamental in many areas of computer science, including data structures,
algorithms, and database theory. They are used to represent collections of items where
membership is the primary concern, and the order or multiplicity of items is irrelevant.
Disjoint Sets
Two sets are said to be disjoint if they have no elements in common. That is, their
intersection is the empty set. For example, the set of even numbers and the set of odd
numbers are disjoint. A collection of sets is called a disjoint-set collection or partition if
every element of the universal set belongs to exactly one set in the collection.
Disjoint Set Union (DSU) Data Structure
A Disjoint Set Union (DSU) data structure, also known as a Union-Find data structure, is a
data structure that keeps track of a set of elements partitioned into a number of disjoint
(non-overlapping) subsets. It provides two primary operations:
1. Find (or FindSet ): Determines which subset a particular element belongs to. It
returns a
representative (usually the root) of the set containing the element. This representative can
be used to check if two elements are in the same set (by comparing their representatives).
1. Union (or UnionSets ): Merges two subsets into a single subset. If the two elements
are already in the same set, nothing is done. Otherwise, the two sets are combined.
DSU is widely used in algorithms that involve grouping elements, such as finding connected
components in a graph, Kruskal's algorithm for Minimum Spanning Trees, and solving
network connectivity problems.
Representation of Disjoint Sets
Disjoint sets are typically represented using a forest of trees, where each tree represents a
set, and the root of each tree is the representative of that set. Each node in the tree stores a
pointer to its parent. The root node points to itself (or has a null parent).
Example:
Consider elements {0, 1, 2, 3, 4, 5}. Initially, each element is in its own set:
Set 0: {0}
Set 1: {1}
Set 2: {2}
Set 3: {3}
Set 4: {4}
Set 5: {5}
This can be represented as an array parent , where parent[i] stores the parent of element
i . Initially, parent[i] = i for all i .
 parent = [0, 1, 2, 3, 4, 5]

Union and Find Operations

1. Find Operation
The Find(i) operation returns the representative (root) of the set containing element i . It
does this by traversing up the parent pointers until it reaches a node that is its own parent
(the root).
Basic Find Implementation:
Plain Text
Function Find(i):
If parent[i] == i:
Return i // i is the root of its set
Else:
Return Find(parent[i]) // Recursively find the root of the parent

Optimization: Path Compression

The basic Find operation can be slow if the trees become tall. Path compression is an
optimization that flattens the tree structure during a Find operation. When Find(i) is
called, it makes every node on the path from i to the root point directly to the root. This
significantly speeds up future Find operations on any of these nodes.
Find with Path Compression:
Plain Text
Function Find(i):
If parent[i] == i:
Return i
parent[i] = Find(parent[i]) // Path compression: set parent[i] to the
root
Return parent[i]

2. Union Operation
The Union(i, j) operation merges the sets containing elements i and j . It first finds the
representatives (roots) of the sets containing i and j . If they are different, it makes one
root the parent of the other.
Basic Union Implementation:
Plain Text
Function Union(i, j):
root_i = Find(i)
root_j = Find(j)
If root_i != root_j:
parent[root_i] = root_j // Make root_j the parent of root_i

Optimization: Union by Rank (or Union by Size)

The basic Union operation can create tall, unbalanced trees, which can degrade the
performance of Find . To keep the trees flat, we use a heuristic called
Union by Rank (or Union by Size).
Union by Rank:
This optimization aims to keep the trees balanced by always attaching the root of the
smaller tree to the root of the larger tree. To do this, we maintain an array rank (or
height ), where rank[i] stores an upper bound on the height of the tree rooted at i .
Plain Text
Function Union(i, j):
root_i = Find(i)
root_j = Find(j)

If root_i != root_j:
If rank[root_i] < rank[root_j]:
parent[root_i] = root_j
Else if rank[root_i] > rank[root_j]:
parent[root_j] = root_i
Else: // Ranks are equal
parent[root_j] = root_i
rank[root_i] = rank[root_i] + 1 // Increment rank of the new root
Union by Size:
Similar to Union by Rank, this optimization uses the size (number of nodes) of the tree
instead of its height. It always attaches the root of the smaller tree to the root of the larger
tree. We maintain an array size , where size[i] stores the number of nodes in the tree
rooted at i .
Plain Text
Function Union(i, j):
root_i = Find(i)
root_j = Find(j)

If root_i != root_j:
If size[root_i] < size[root_j]:
parent[root_i] = root_j
size[root_j] = size[root_j] + size[root_i]
Else:
parent[root_j] = root_i
size[root_i] = size[root_i] + size[root_j]

Time Complexity of DSU Operations

When both path compression and union by rank/size optimizations are used, the
amortized time complexity for a sequence of m Union and Find operations on n
elements is nearly constant. It is O(α(n)) , where α(n) is the inverse Ackermann function.
The Ackermann function grows extremely rapidly, so its inverse α(n) grows extremely
slowly. For all practical values of n (even larger than the number of atoms in the
observable universe), α(n) is less than 5. This means that for practical purposes, the
amortized time complexity of Union and Find operations is effectively constant, making
DSU a highly efficient data structure.
Applications of Disjoint Set Union
DSU is a powerful data structure with numerous applications:
1. Connected Components in a Graph: DSU can efficiently determine if two vertices are
in the same connected component and can be used to find all connected components
 in a graph. When processing edges, if an edge connects two vertices in different
components, Union them. If they are already in the same component, adding the edge
creates a cycle.
2. Kruskal's Algorithm for Minimum Spanning Tree (MST): Kruskal's algorithm builds an
MST by adding edges in increasing order of weight. DSU is used to efficiently check if
adding an edge creates a cycle (i.e., if the two vertices are already in the same set) and
to merge components when an edge is added.
3. Network Connectivity: Used to model and solve problems related to network
connectivity, such as determining if a network is fully connected or identifying isolated
segments.
4. Image Processing: Used in algorithms for image segmentation, where connected pixels
with similar properties are grouped into components.
5. Percolation Theory: In physics and materials science, DSU can be used to model
percolation, where connections are formed between sites in a grid, and one wants to
determine if a path exists across the grid.
6. Compiler Design: Used in type inference and unification algorithms.
In summary, the Disjoint Set Union data structure is an elegant and highly efficient solution
for managing partitions of elements into disjoint sets, providing near-constant time
operations for merging sets and finding set representatives. Its optimized versions make it
indispensable for a wide range of graph and connectivity problems.

UNIT-II: Divide-and-Conquer
General Method
Divide-and-Conquer is a powerful algorithmic paradigm (a general approach to solving
problems) that involves breaking down a problem into smaller, more manageable
subproblems, solving each of these subproblems independently, and then combining their
solutions to solve the original problem. This strategy is often used for problems that are
naturally recursive in nature.
The three steps of the Divide-and-Conquer paradigm are:
1. Divide: The original problem is divided into several smaller subproblems that are
similar to the original problem but smaller in size. This division continues recursively
until the subproblems become small enough to be solved directly (these are called base
cases or trivial cases).
2. Conquer: The subproblems are solved recursively. If the subproblem is small enough
(the base case), it is solved directly. Otherwise, it is further divided.
3. Combine: The solutions to the subproblems are combined to form the solution to the
original problem. This step often involves merging or integrating the results from the
conquered subproblems.
When to use Divide-and-Conquer:
• When a problem can be naturally broken down into smaller, independent subproblems.
• When the subproblems are of the same type as the original problem.
• When combining the solutions of subproblems is relatively straightforward.
Advantages of Divide-and-Conquer:
• Efficiency: Often leads to algorithms with significantly better time complexity
compared to naive approaches (e.g., O(n log n) for sorting instead of O(n^2)).
• Parallelism: Subproblems can often be solved independently, making them suitable for
parallel processing.
• Memory Hierarchy: Can be designed to make efficient use of memory caches by
processing data in smaller, contiguous blocks.
• Conceptual Simplicity: For many problems, the divide-and-conquer approach is
intuitive and easier to understand and implement recursively.
Disadvantages of Divide-and-Conquer:
• Overhead of Recursion: Recursive calls involve overhead (function call stack, saving
context), which can sometimes make them slower than iterative solutions for small
 problem sizes.
• Stack Overflow: Deep recursion can lead to stack overflow errors if the recursion depth
exceeds the system's limit.
• Not Always Applicable: Not all problems can be efficiently broken down into
independent subproblems that can be easily combined.
Recurrence Relations
The running time of a divide-and-conquer algorithm is often described by a recurrence
relation. A recurrence relation is an equation or inequality that describes a function in terms
of its values on smaller inputs. For a divide-and-conquer algorithm, if a problem of size n
is divided into a subproblems, each of size n/b , and the divide and combine steps take
f(n) time, the recurrence relation is typically:
T(n) = aT(n/b) + f(n)
Where:
• T(n) is the time complexity for a problem of size n .
• a is the number of subproblems.
• n/b is the size of each subproblem.
• f(n) is the cost of dividing the problem and combining the solutions.
This recurrence relation can often be solved using methods like the Master Theorem,
substitution method, or recursion tree method to find the asymptotic time complexity.
Examples of Divide-and-Conquer Algorithms
Many well-known algorithms use the divide-and-conquer strategy:
• Binary Search: Divides the search space in half in each step.
• Merge Sort: Divides the array into two halves, sorts them, and then merges the sorted
halves.
 • Quicksort: Divides the array into two partitions around a pivot, and then recursively
sorts the partitions.
• Strassen's Matrix Multiplication: Divides matrices into sub-matrices to reduce the
number of multiplications.
Let's explore some of these in detail.
Defective Chess Board (Tiling Problem)
The Defective Chess Board problem is a classic example that beautifully illustrates the
divide-and-conquer paradigm. The problem is to tile a 2^n x 2^n chessboard with one
square missing (defective) using L-shaped trominoes. An L-shaped tromino is a 2x2 square
with one square removed.
Problem Statement: Given a 2^n x 2^n chessboard with exactly one square removed, tile
the remaining (2^n)^2 - 1 squares using L-shaped trominoes.
The Divide-and-Conquer Approach:
1. Divide: Divide the 2^n x 2^n board into four 2^(n-1) x 2^(n-1) sub-boards. This creates
four quadrants.
2. Conquer (Recursive Step):
• Identify which of the four quadrants contains the defective square. This quadrant is a
2^(n-1) x 2^(n-1) defective board, which can be solved recursively.
• For the other three quadrants (which are currently complete 2^(n-1) x 2^(n-1)
boards), place a single L-shaped tromino at the center of the original 2^n x 2^n
board such that it covers one square from each of these three non-defective
quadrants. This effectively makes one square in each of these three quadrants
the 'defective' square for the purpose of the recursive call. Now, all four quadrants are
effectively 2^(n-1) x 2^(n-1) defective boards, each with one missing square.
1. Combine: The combination step is implicit. Once all four 2^(n-1) x 2^(n-1) sub-boards
are tiled, the entire 2^n x 2^n board is tiled. The L-tromino placed in the center acts as
the combining piece.
Base Case: The base case is a 2x2 board with one defective square. This can always be
tiled with a single L-shaped tromino.
Example Walkthrough (2x2 board):
Imagine a 2x2 board with the top-left square missing:
Plain Text
_ X
X X

This is a base case, and it can be tiled directly with one L-tromino:
Plain Text
L L
L _

Example Walkthrough (4x4 board):

Consider a 4x4 board with a defective square, say at (0,0) (top-left).
1. Divide: Split the 4x4 board into four 2x2 quadrants.
2. Conquer (Recursive Step):
• Q1 is a 2x2 board with a defective square. This will be solved recursively.
• For Q2, Q3, and Q4, place an L-tromino at the center of the 4x4 board, covering one
square from each of Q2, Q3, and Q4. This effectively makes a square in Q2, Q3, and Q4
defective for the recursive calls.
Plain Text
```
_ X | L X
X X | L L
---+---
X L | X X
X X | X X
 ```

Now, we have four 2x2 defective boards:

* Q1: Defective at (0,0) (original defect).
* Q2: Defective at (1,1) (from the central tromino).
* Q3: Defective at (2,1) (from the central tromino).
* Q4: Defective at (2,2) (from the central tromino).

3. Combine: Each of these 2x2 defective boards can be tiled with a single L-tromino (the
base case). Once all four are tiled, the entire 4x4 board is tiled.
Time Complexity:
The recurrence relation for this problem is T(n) = 4T(n/2) + O(1) , where n is the size of the
board ( 2^k x 2^k ). The O(1) term represents the constant time work of placing the central
tromino. Using the Master Theorem, this solves to T(n) = O(n^2) , which is optimal because
we need to visit every square on the board to place a tile.
Binary Search
Binary search is a classic and highly efficient searching algorithm that works on sorted
arrays. It follows the divide-and-conquer strategy by repeatedly dividing the search interval
in half.
Problem Statement: Given a sorted array A and a target value x , find the index of x in
A , or determine that x is not in A .
The Divide-and-Conquer Approach:
1. Divide: Compare the target value x with the middle element of the array, A[mid] .
• If x == A[mid] , the search is complete.
• If x < A[mid] , the search space is reduced to the left half of the array.
• If x > A[mid] , the search space is reduced to the right half of the array.
2. Conquer: Recursively search the appropriate sub-array (left or right half).
3. Combine: There is no explicit combine step. The result of the recursive call is directly
returned.
Base Case: The base case is when the search interval becomes empty (e.g., low > high ). In
this case, the target value is not in the array.
Recursive Implementation:
Plain Text
Function BinarySearch(A, low, high, x):
If low > high:
Return -1 // Base case: not found

mid = low + (high - low) / 2 // Avoid potential overflow

If A[mid] == x:
Return mid // Found
Else if x < A[mid]:
Return BinarySearch(A, low, mid - 1, x) // Search left half
Else:
Return BinarySearch(A, mid + 1, high, x) // Search right half

Iterative Implementation:
Binary search is often implemented iteratively to avoid the overhead of recursion and the
risk of stack overflow for very large arrays.
Plain Text
Function BinarySearchIterative(A, x):
low = 0
high = length(A) - 1

While low <= high:

mid = low + (high - low) / 2

If A[mid] == x:
Return mid
Else if x < A[mid]:
high = mid - 1
Else:
low = mid + 1

Return -1 // Not found

Time Complexity:
The recurrence relation for binary search is T(n) = T(n/2) + O(1) , where n is the size of the
array. The O(1) term represents the constant time work of comparing with the middle
element. Using the Master Theorem, this solves to T(n) = O(log n) . This logarithmic time
complexity makes binary search extremely efficient for large datasets.
Space Complexity:
• Recursive Version: O(log n) due to the recursion stack depth.
• Iterative Version: O(1) as it only uses a few variables.
Limitations:
• Requires a Sorted Array: The primary requirement for binary search is that the input
array must be sorted. If the array is not sorted, the algorithm will not work correctly.
• Not Suitable for Linked Lists: Binary search requires random access to elements (to
get the middle element in O(1) time), which is not efficient for linked lists.
Finding the Maximum and Minimum
Problem Statement: Given an array of n numbers, find the maximum and minimum
elements in the array.
Naive Approach:
A simple approach is to iterate through the array twice, once to find the maximum and once
to find the minimum. This would require 2(n-1) comparisons. A slightly better approach is
to iterate once, keeping track of both the maximum and minimum found so far. This would
require 2(n-1) comparisons in the worst case (e.g., a sorted array).
Divide-and-Conquer Approach:
1. Divide: Divide the array into two halves.
2. Conquer: Recursively find the maximum and minimum elements in each half.
3. Combine: Compare the maximums of the two halves to find the overall maximum, and
compare the minimums of the two halves to find the overall minimum. This requires
two comparisons.
Recursive Implementation:
Plain Text
Function FindMaxMin(A, low, high):
// Base case: one element
If low == high:
Return (A[low], A[low])

// Base case: two elements

If high == low + 1:
If A[low] > A[high]:
Return (A[low], A[high])
Else:
Return (A[high], A[low])

// Recursive step
mid = (low + high) / 2
(max1, min1) = FindMaxMin(A, low, mid)
(max2, min2) = FindMaxMin(A, mid + 1, high)

// Combine
final_max = max(max1, max2)
final_min = min(min1, min2)

Return (final_max, final_min)

Time Complexity Analysis:

The recurrence relation for the number of comparisons is T(n) = 2T(n/2) + 2 . The +2 comes
from the two comparisons in the combine step.
• If n is a power of 2, n = 2^k :
T(n) = 2T(n/2) + 2
= 2(2T(n/4) + 2) + 2 = 4T(n/4) + 4 + 2
= 4(2T(n/8) + 2) + 6 = 8T(n/8) + 8 + 6
...
= 2^k T(1) + 2(2^k - 1)
Since T(1) = 0 (no comparisons for one element), T(n) = 2(n-1) = 2n - 2 .
Wait, this is not better than the naive approach. Let's re-examine the base case. For
T(2) , we need 1 comparison. So T(n) = 2T(n/2) + 2 with T(2)=1 gives T(n) = 3n/2 - 2
comparisons.
This is better than the 2n-2 comparisons of the naive approach. For example, if n=8 , the
divide-and-conquer approach needs 3(8)/2 - 2 = 10 comparisons, while the naive approach
needs 2(8)-2 = 14 comparisons.
Space Complexity: O(log n) due to the recursion stack depth.
Merge Sort
Merge Sort is a classic sorting algorithm that perfectly embodies the divide-and-conquer
paradigm. It is known for its stability and guaranteed O(n log n) time complexity.
The Divide-and-Conquer Approach:
1. Divide: Divide the n -element array into two sub-arrays of n/2 elements each.
2. Conquer: Recursively sort the two sub-arrays using Merge Sort.
3. Combine: Merge the two sorted sub-arrays to produce a single sorted array. This is
done by a Merge procedure.
Base Case: The base case is an array with 0 or 1 element, which is already sorted.
Recursive Implementation:
Plain Text
Function MergeSort(A, low, high):
If low < high:
mid = (low + high) / 2
MergeSort(A, low, mid) // Sort left half
MergeSort(A, mid + 1, high) // Sort right half
Merge(A, low, mid, high) // Merge the two halves

The Merge Procedure:

The Merge procedure is the heart of Merge Sort. It takes two sorted sub-arrays and merges
them into a single sorted array. It does this by creating temporary arrays for the two halves
and then iterating through them, picking the smaller element at each step and placing it
into the original array.
 Plain Text
Function Merge(A, low, mid, high):
// Create temporary arrays
n1 = mid - low + 1
n2 = high - mid
L = new Array of size n1
R = new Array of size n2

// Copy data to temporary arrays

For i from 0 to n1-1:
L[i] = A[low + i]
For j from 0 to n2-1:
R[j] = A[mid + 1 + j]

// Merge the temporary arrays back into A

i = 0 // Initial index of first subarray
j = 0 // Initial index of second subarray
k = low // Initial index of merged subarray

While i < n1 and j < n2:

If L[i] <= R[j]:
A[k] = L[i]
i = i + 1
Else:
A[k] = R[j]
j = j + 1
k = k + 1

// Copy remaining elements of L[], if any

While i < n1:
A[k] = L[i]
i = i + 1
k = k + 1

// Copy remaining elements of R[], if any

While j < n2:
A[k] = R[j]
j = j + 1
k = k + 1

Time Complexity:
The recurrence relation for Merge Sort is T(n) = 2T(n/2) + O(n) . The O(n) term comes from
the Merge procedure, which takes linear time to merge two sub-arrays of total size n .
Using the Master Theorem, this solves to T(n) = O(n log n) . This holds for the best, worst, and
average cases, making Merge Sort very reliable.
Space Complexity: O(n) because of the temporary arrays created during the Merge
procedure. This is a significant drawback of Merge Sort, especially for large datasets where
memory is a concern.
Properties of Merge Sort:
• Stable: It preserves the relative order of equal elements, which can be important in
some applications.
• Not In-Place: It requires extra space proportional to the input size.
• External Sorting: Its sequential nature and need for extra space make it well-suited for
external sorting (sorting data that doesn't fit into main memory).
Quicksort
Quicksort is another highly efficient sorting algorithm that uses the divide-and-conquer
strategy. It is often faster in practice than Merge Sort, despite having a worst-case time
complexity of O(n^2) .
The Divide-and-Conquer Approach:
1. Divide: Choose an element from the array, called the pivot. Partition the array into two
sub-arrays: one containing elements less than or equal to the pivot, and another
containing elements greater than the pivot. The pivot is now in its final sorted position.
2. Conquer: Recursively sort the two sub-arrays using Quicksort.
3. Combine: No explicit combine step is needed. The array is sorted in-place.
Recursive Implementation:
Plain Text
Function QuickSort(A, low, high):
If low < high:
// pi is partitioning index, A[pi] is now at right place
pi = Partition(A, low, high)
 QuickSort(A, low, pi - 1) // Before pi
QuickSort(A, pi + 1, high) // After pi

The Partition Procedure:

The Partition procedure is the key to Quicksort. There are several ways to implement it
(e.g., Lomuto partition scheme, Hoare partition scheme). The goal is to rearrange the array
such that all elements smaller than the pivot are on its left, and all elements greater are on
its right.
Lomuto Partition Scheme (common choice):
This scheme typically chooses the last element as the pivot.
Plain Text
Function Partition(A, low, high):
pivot = A[high]
i = low - 1 // Index of smaller element

For j from low to high - 1:

// If current element is smaller than or equal to pivot
If A[j] <= pivot:
i = i + 1
Swap(A[i], A[j])

Swap(A[i + 1], A[high])

Return (i + 1)

Time Complexity:
• Best and Average Case: O(n log n) . This occurs when the pivot choice consistently
divides the array into roughly equal halves.
• Worst Case: O(n^2) . This occurs when the pivot choice consistently results in highly
unbalanced partitions (e.g., picking the smallest or largest element as the pivot in a
sorted array). This leads to a recurrence of T(n) = T(n-1) + O(n) .
Space Complexity: O(log n) on average (due to recursion stack depth), and O(n) in the
worst case.
Improving Quicksort:
• Randomized Pivot: To avoid the worst-case scenario, choose a random element as the
pivot. This makes it highly unlikely that the worst-case input will be encountered.
• Median-of-Three Pivot: Choose the pivot as the median of the first, middle, and last
elements of the array. This also helps in avoiding worst-case scenarios.
• Hybrid with Insertion Sort: For small sub-arrays, switch to Insertion Sort, which is
faster for small inputs due to less overhead.
Properties of Quicksort:
• In-Place: It sorts the array without requiring significant extra space (unlike Merge Sort).
• Unstable: It does not preserve the relative order of equal elements.
• Fast in Practice: Due to its in-place nature and good cache performance, it is often
faster than other O(n log n) algorithms in practice.
Selection
Problem Statement: Given an unsorted array A and an integer k , find the k -th
smallest element in the array. This is also known as the selection problem or order
statistic problem.
• If k=1 , it's finding the minimum.
• If k=n , it's finding the maximum.
• If k = (n+1)/2 , it's finding the median.
Naive Approach: Sort the array and then return the element at index k-1 . This takes O(n
log n) time.
Divide-and-Conquer Approach (Quickselect):
This algorithm is very similar to Quicksort. It uses the same Partition procedure.
1. Divide: Choose a pivot and partition the array around it. Let the pivot's final position be
p.
 2. Conquer:
• If p == k-1 , the pivot is the k -th smallest element. Return it.
• If p > k-1 , the k -th smallest element must be in the left sub-array. Recursively
search for the k -th smallest element in the left sub-array.
• If p < k-1 , the k -th smallest element must be in the right sub-array. Recursively
search for the (k - p - 1) -th smallest element in the right sub-array.
Recursive Implementation (Quickselect):
Plain Text
Function Quickselect(A, low, high, k):
If low <= high:
pi = Partition(A, low, high)

If pi == k - 1:
Return A[pi]
Else if pi > k - 1:
Return Quickselect(A, low, pi - 1, k)
Else:
Return Quickselect(A, pi + 1, high, k)

Time Complexity:
• Best and Average Case: O(n) . The recurrence relation is T(n) = T(n/2) + O(n) , which
solves to O(n) . This is because we only recurse on one side of the partition.
• Worst Case: O(n^2) . Similar to Quicksort, this happens with bad pivot choices.
Median-of-Medians Algorithm (Worst-Case Linear Time Selection):
There exists a more complex version of the selection algorithm that guarantees O(n) time
complexity in the worst case. It does this by choosing the pivot more carefully using a
deterministic method to find a good pivot. This algorithm is known as the Median-of-
Medians algorithm. While its worst-case complexity is O(n) , its constant factor is quite
large, so Quickselect (with randomized pivot) is often preferred in practice for its better
average-case performance.
Strassen's Matrix Multiplication
Strassen's algorithm is a classic example of how the divide-and-conquer paradigm can lead
to asymptotically faster algorithms, even for problems that seem to have obvious O(n^3)
solutions. It provides a way to multiply two n x n matrices in O(n^log2(7)) time, which is
approximately O(n^2.807) , an improvement over the standard O(n^3) algorithm.
Problem Statement: Given two n x n matrices, A and B , compute their product C = A x
B.
Standard Matrix Multiplication (O(n^3)):
The traditional way to multiply two n x n matrices A and B to get C is defined as:
C[i][j] = Σ (A[i][k] * B[k][j]) for k from 1 to n .
This involves three nested loops, each running n times, resulting in n^3 multiplications
and n^3 additions. Thus, its time complexity is O(n^3) .
Divide-and-Conquer Approach (Standard, O(n^3)):
One might try to apply divide-and-conquer by dividing each n x n matrix into four n/2 x
n/2 sub-matrices:
A = [[A11, A12], [A21, A22]]
B = [[B11, B12], [B21, B22]]
C = [[C11, C12], [C21, C22]]
Where:
C11 = A11*B11 + A12*B21
C12 = A11*B12 + A12*B22
C21 = A21*B11 + A22*B21
C22 = A21*B12 + A22*B22
This approach requires 8 recursive calls for matrix multiplications and 4 matrix additions.
The recurrence relation would be T(n) = 8T(n/2) + O(n^2) (where O(n^2) is for matrix
additions). By the Master Theorem, this still solves to T(n) = O(n^3) . So, a simple divide-and-
conquer doesn't improve the asymptotic complexity.
Strassen's Insight:
Strassen discovered a way to compute the product of two 2x2 matrices using only 7
multiplications instead of 8. This seemingly small improvement, when applied recursively,
leads to a significant asymptotic speedup.
The 7 Multiplications (for 2x2 matrices):
Let A and B be two 2x2 matrices.
A = [[a, b], [c, d]]
B = [[e, f], [g, h]]
Instead of computing ae+bg , af+bh , ce+dg , cf+dh directly, Strassen computes 7
intermediate products:
P1 = a(f - h)
P2 = (a + b)h
P3 = (c + d)e
P4 = d(g - e)
P5 = (a + d)(e + h)
P6 = (b - d)(g + h)
P7 = (a - c)(e + f)
Then, the elements of the product matrix C are:
C11 = P5 + P4 - P2 + P6
C12 = P1 + P2
C21 = P3 + P4
C22 = P5 + P1 - P3 - P7
This method uses 7 multiplications and 18 additions/subtractions (compared to 8
multiplications and 4 additions for the standard method). The reduction in multiplications
is key.
Strassen's Algorithm (General n x n Matrices):
 1. Divide: Divide the n x n matrices A and B into four n/2 x n/2 sub-matrices. (If n is
not a power of 2, pad the matrices with zeros to make them 2^k x 2^k ).
2. Conquer: Recursively compute the 7 products P1, P2, ..., P7 using Strassen's algorithm
on the n/2 x n/2 sub-matrices.
3. Combine: Compute the four sub-matrices C11, C12, C21, C22 using the 18
additions/subtractions as defined above.
Time Complexity:
The recurrence relation for Strassen's algorithm is T(n) = 7T(n/2) + O(n^2) . The O(n^2) term
comes from the additions and subtractions of n/2 x n/2 matrices. Using the Master
Theorem, this solves to T(n) = O(n^log2(7)) , which is approximately O(n^2.807) .
Advantages:
• Asymptotically Faster: For sufficiently large n , Strassen's algorithm is faster than the
standard O(n^3) algorithm.
Disadvantages:
• Constant Factor: The constant factor hidden in the O notation is larger than that of
the standard algorithm due to the increased number of additions/subtractions and the
overhead of managing sub-matrices.
• Numerical Stability: It can be less numerically stable than the standard algorithm for
certain types of matrices due to the increased number of additions and subtractions.
• Space Complexity: It requires more auxiliary space than the standard algorithm due to
the need to store the intermediate sub-matrices.
• Crossover Point: For practical implementations, the standard O(n^3) algorithm is
often faster for small matrices (typically n < 100 to 200 ) because of Strassen's larger
constant factor and overhead. Hybrid approaches are often used, switching to the
standard algorithm for sub-matrices below a certain size.
Despite its practical limitations for smaller matrices, Strassen's algorithm was a significant
theoretical breakthrough, showing that matrix multiplication could be done faster than
 O(n^3) , and it opened the door for further research into even faster matrix multiplication
algorithms.
Convex Hull
The Convex Hull problem is a fundamental problem in computational geometry. It involves
finding the smallest convex polygon that encloses a given set of points in a plane.
Problem Statement: Given a set S of n points in a plane, find the convex hull of S .
Definition of Convex Hull: The convex hull of a set of points S is the smallest convex
polygon P such that every point in S is either on the boundary of P or in its interior.
Visualizing Convex Hull: Imagine a set of nails hammered into a board. If you stretch a
rubber band around all the nails and let it snap, the shape formed by the rubber band is the
convex hull.
Applications:
• Pattern Recognition: Identifying the shape or boundary of a cluster of data points.
• Image Processing: Object recognition and shape analysis.
• Computer Graphics: Collision detection, object simplification.
• Geographic Information Systems (GIS): Finding the smallest region enclosing a set of
locations.
• Statistics: Outlier detection.
Divide-and-Conquer Approach (e.g., Quickhull or Merge Hull):
While there are several algorithms for finding the convex hull (e.g., Graham Scan, Jarvis
March, Monotone Chain), some efficient ones use the divide-and-conquer strategy. Let's
consider a general approach similar to Quickhull.
1. Divide: Find the points with the minimum and maximum x-coordinates. These two
points must be part of the convex hull and define a line segment. This line segment
divides the set of points into two subsets: those above the line and those below the line.
 2. Conquer: Recursively find the convex hull for the points in each subset. For the upper
subset, find the point furthest from the line segment. This point, along with the two
endpoints of the segment, forms a triangle. The points inside this triangle can be
discarded. The problem then reduces to finding the hull for points outside this triangle,
divided by the new segments. Repeat this for the lower subset.
3. Combine: The convex hull is formed by combining the hulls found for the upper and
lower subsets.
Algorithm Steps (Quickhull-like):
1. Find the points P_min and P_max with the minimum and maximum x-coordinates,
respectively. These two points are part of the convex hull.
2. Draw a line segment connecting P_min and P_max . This line divides the remaining
points into two sets: S_upper (points above the line) and S_lower (points below the
line).
3. Recursively call a function FindHull(P1, P2, S) for S_upper (with P1=P_min , P2=P_max )
and S_lower (with P1=P_max , P2=P_min ).
Time Complexity:
• Worst Case: O(n^2) . This occurs when many points lie on the hull, and the selection of
the furthest point repeatedly involves checking a large subset of points.
• Average Case: O(n log n) . This is often achieved in practice when the points are well-
distributed.
Space Complexity: O(n) for storing points and recursion stack.
Comparison with other Convex Hull Algorithms:
• Graham Scan: O(n log n) . Sorts points by angle, then uses a stack to build the hull.
Generally robust and efficient.
• Jarvis March (Gift Wrapping): O(nh) , where h is the number of points on the hull.
Can be O(n^2) in the worst case (all points on the hull) but efficient for small h .
 • Monotone Chain (Andrew's Algorithm): O(n log n) . Sorts points by x-coordinate, then
builds upper and lower hulls separately. Often simpler to implement than Graham Scan.
The choice of algorithm depends on the specific requirements, such as the expected
distribution of points, the number of points on the hull, and implementation complexity.
For general cases, O(n log n) algorithms like Graham Scan or Monotone Chain are preferred.
Quickhull is competitive in average cases.

UNIT-III: Greedy Method and Traversal Techniques

The General Method (Greedy Algorithms)
The Greedy Method is an algorithmic paradigm that builds a solution to a problem piece by
piece, always choosing the next piece that offers the most obvious and immediate benefit. It
makes locally optimal choices in the hope that these choices will lead to a globally optimal
solution. The greedy approach is often simple to implement and can be very efficient, but it
does not always produce the optimal solution for every problem.
Key Characteristics of Greedy Algorithms:
1. Optimal Substructure: A globally optimal solution can be achieved by combining
locally optimal solutions to subproblems. This means that an optimal solution to the
problem contains optimal solutions to its subproblems.
2. Greedy Choice Property: A globally optimal solution can be reached by making a
locally optimal (greedy) choice. This means that once a greedy choice is made, it never
needs to be reconsidered. The choice made at each step is the best choice at that
moment, without regard for future consequences.
When to use Greedy Algorithms:
• When the problem exhibits both the optimal substructure and greedy choice properties.
• When a simple, efficient, and often good (though not always optimal) solution is
acceptable.
Advantages of Greedy Algorithms:
• Simplicity: Often much simpler to design and implement than dynamic programming
or other complex algorithms.
• Efficiency: Typically have lower time complexity compared to other approaches,
making them suitable for large datasets.
• Intuitive: The logic behind greedy choices is often straightforward and easy to
understand.
Disadvantages of Greedy Algorithms:
• Not Always Optimal: The biggest drawback is that a greedy approach does not
guarantee a globally optimal solution for all problems. It only works for problems that
exhibit the greedy choice property.
• Proof of Correctness: Proving that a greedy algorithm yields an optimal solution can
be challenging. It often requires demonstrating that the greedy choice property holds.
Elements of a Greedy Strategy
To apply the greedy method, you typically need to define:
1. Candidate Set: A set of items from which to choose a solution.
2. Selection Function: A function that chooses the best candidate to add to the solution
at each step.
3. Feasibility Function: A function that checks if a candidate can be added to the solution
(i.e., if it satisfies constraints).
4. Objective Function: A function that assigns a value to a solution or partial solution,
which the algorithm tries to optimize (maximize or minimize).
5. Solution Function: A function that indicates when a complete solution has been found.
Examples of Greedy Algorithms
Let's explore some classic problems where the greedy method is applied.
Container Loading
Problem Statement: You have a ship with a maximum weight capacity C . You are given
n containers, each with a specific weight w_i . The goal is to load as many containers as
possible onto the ship without exceeding its capacity.
Greedy Approach: To maximize the number of containers, it makes intuitive sense to load
the lightest containers first. This leaves more capacity for subsequent containers.
1. Sort: Sort the containers in non-decreasing order of their weights.
2. Iterate and Load: Iterate through the sorted containers. For each container, if adding it
to the ship does not exceed the remaining capacity, load it and update the remaining
capacity.
Algorithm:
Plain Text
Function ContainerLoading(weights, capacity):
Sort(weights) // Sort weights in ascending order
current_weight = 0
loaded_containers = 0

For each weight in weights:

If current_weight + weight <= capacity:
current_weight = current_weight + weight
loaded_containers = loaded_containers + 1
Else:
Break // Cannot load more containers

Return loaded_containers

Proof of Optimality: This greedy strategy is optimal for maximizing the number of
containers. Suppose there is an optimal solution that does not include the lightest
container. We can replace any container in that optimal solution with the lightest container
(if it fits) and still have a valid solution with at least as many containers, and possibly more
remaining capacity. By repeatedly applying this logic, we can transform any optimal
solution into the greedy solution without decreasing the number of loaded containers.
Time Complexity: O(n log n) due to sorting, plus O(n) for iteration, so overall O(n log n) .
Knapsack Problem (Fractional Knapsack)
There are two main types of Knapsack problems: 0/1 Knapsack and Fractional Knapsack.
The greedy approach works for the Fractional Knapsack problem, but not for the 0/1
Knapsack problem (which requires dynamic programming).
Problem Statement (Fractional Knapsack): You have a knapsack with a maximum weight
capacity W . You are given n items, each with a weight w_i and a value v_i . You can
take fractions of items. The goal is to maximize the total value of items in the knapsack.
Greedy Approach: To maximize the total value, it makes sense to prioritize items that give
the most value per unit of weight. This is known as the value-to-weight ratio.
1. Calculate Ratios: For each item, calculate its value-to-weight ratio ( v_i / w_i ).
2. Sort: Sort the items in non-increasing (descending) order of their value-to-weight
ratios.
3. Iterate and Fill: Iterate through the sorted items. For each item:
• If the entire item fits in the remaining capacity, take the whole item.
• If only a fraction of the item fits, take that fraction to fill the knapsack completely.
Algorithm:
Plain Text
Function FractionalKnapsack(items, capacity):
// Each item is a pair (weight, value)
// Calculate value-to-weight ratio for each item
For each item in items:
[Link] = [Link] / [Link]

Sort(items by [Link] in descending order)

current_weight = 0
total_value = 0

For each item in items:

If current_weight + [Link] <= capacity:
// Take the whole item
current_weight = current_weight + [Link]
 total_value = total_value + [Link]
Else:
// Take a fraction of the item
remaining_capacity = capacity - current_weight
fraction = remaining_capacity / [Link]
total_value = total_value + (fraction * [Link])
current_weight = capacity // Knapsack is full
Break

Return total_value

Proof of Optimality: This greedy strategy is optimal for the Fractional Knapsack problem.
Suppose there is an optimal solution that includes less of an item with a higher value-to-
weight ratio and more of an item with a lower ratio. We could swap a small amount of the
lower-ratio item for an equal weight of the higher-ratio item, increasing the total value
without exceeding capacity. This contradicts the assumption of optimality, proving the
greedy choice is optimal.
Time Complexity: O(n log n) due to sorting, plus O(n) for iteration, so overall O(n log n) .
Tree Vertex Splitting (This topic is less common in standard algorithms
curricula, but can be approached greedily if the objective is well-
defined. Assuming a common interpretation related to minimizing cuts
or maximizing components.)
This problem name is not standard. It might refer to a specific problem variant or a general
concept. If it refers to partitioning a tree into components by removing vertices to optimize
some metric, a greedy approach might involve iteratively removing vertices that yield the
best immediate improvement according to the objective function.
Possible Interpretation: Minimum Vertex Cover on Trees (related to splitting/removing
vertices)
A vertex cover of a graph is a set of vertices such that every edge of the graph is incident to
at least one vertex in the set. The goal is to find a vertex cover of minimum size. For general
graphs, this is NP-hard, but for trees, it can be solved efficiently using dynamic
programming or a greedy approach.
Greedy Approach for Minimum Vertex Cover on Trees:
 1. Start from the leaves of the tree.
2. If a leaf node u is not covered (i.e., its parent edge is not covered), then its parent v
must be in the vertex cover. Add v to the cover and mark v and all its incident edges
as covered.
3. Continue this process upwards.
This greedy strategy works for trees because of their specific structure. Each time you add a
parent of an uncovered leaf, you cover that leaf and potentially other edges connected to
the parent, making a locally optimal choice that contributes to a global optimum.
Time Complexity: O(V+E) for a tree, as it involves a traversal.
Job Sequencing with Deadlines
Problem Statement: You are given a set of n jobs. Each job i has a deadline d_i (by
which it must be completed) and a profit p_i (earned if completed by its deadline). Each
job takes one unit of time to complete. You can only perform one job at a time. The goal is to
select a subset of jobs and schedule them to maximize the total profit.
Greedy Approach: To maximize total profit, it makes sense to prioritize jobs that offer the
highest profit. However, deadlines must also be considered.
1. Sort: Sort the jobs in non-increasing (descending) order of their profits.
2. Schedule: Iterate through the sorted jobs. For each job, try to schedule it as late as
possible but before its deadline, and in an available time slot. If multiple slots are
available, choose the latest possible slot to keep earlier slots open for jobs with earlier
deadlines.
Algorithm:
Plain Text
Function JobSequencing(jobs):
// Each job is a tuple (id, deadline, profit)
Sort(jobs by profit in descending order)

max_deadline = 0
 For each job in jobs:
max_deadline = max(max_deadline, [Link])

// Create a time slot array, initialized to empty

// slot[i] will store the job scheduled at time i
slots = new Array of size (max_deadline + 1)
For i from 0 to max_deadline:
slots[i] = null

total_profit = 0

For each job in jobs:

// Try to place the job in the latest possible free slot before its
deadline
For t from [Link] down to 1:
If slots[t] is null:
slots[t] = [Link]
total_profit = total_profit + [Link]
Break // Job scheduled, move to next job

Return total_profit, slots

Proof of Optimality: This greedy strategy is optimal. The proof relies on an exchange
argument: if an optimal solution exists that doesn't include a high-profit job that could have
been scheduled, we can swap it with a lower-profit job (or add it if a slot is free) to get a
solution that is at least as good, or better.
Time Complexity: O(n log n) for sorting. The nested loop for scheduling can be O(n *
max_deadline) in a naive implementation. With a Disjoint Set Union (DSU) data structure to
manage free slots, it can be optimized to O(n log n) or O(n log max_deadline) .
Minimum-Cost Spanning Trees (MST)
A spanning tree of a connected, undirected graph is a subgraph that is a tree and connects
all the vertices together. A graph can have many spanning trees. A Minimum-Cost Spanning
Tree (MST) is a spanning tree with the lowest possible total edge weight.
Two classic greedy algorithms solve the MST problem:
1. Kruskal's Algorithm:
 • Greedy Choice: At each step, add the edge with the smallest weight that does not
form a cycle with the already added edges.
• Algorithm:
1. Sort all edges in non-decreasing order of their weights.
2. Initialize a forest where each vertex is in its own set (using DSU).
3. Iterate through the sorted edges:
a. For each edge (u, v) with weight w :
b. If u and v are in different sets (checked using Find operation of DSU), add
the edge (u, v) to the MST and Union the sets containing u and v .
c. Stop when V-1 edges have been added (where V is the number of vertices).
• Time Complexity: O(E log E) or O(E log V) (since E can be at most V^2 , log E is
O(log V) ). The sorting dominates, and DSU operations are nearly constant time.
2. Prim's Algorithm:
• Greedy Choice: Start with an arbitrary vertex. At each step, add the cheapest edge
that connects a vertex already in the MST to a vertex not yet in the MST.
• Algorithm:
1. Initialize an empty MST and a set of visited vertices.
2. Start with an arbitrary vertex, add it to the MST and mark it visited.
3. Maintain a priority queue of edges connecting visited vertices to unvisited vertices,
ordered by weight.
4. While the MST does not include all vertices:
a. Extract the minimum-weight edge (u, v) from the priority queue, where u is
visited and v is unvisited.
b. Add (u, v) to the MST and mark v as visited.
c. For all edges (v, x) where x is unvisited, add them to the priority queue.
 • Time Complexity: O(E log V) or O(E + V log V) with a Fibonacci heap. With a binary
heap, it's O(E log V) .
Proof of Optimality for MST Algorithms: Both Kruskal's and Prim's algorithms are proven
to be optimal. The proof relies on the
cut property and cycle property of MSTs, which show that their greedy choices lead to a
global optimum.
Optimal Storage on Tapes
Problem Statement: You have n programs of lengths l_1, l_2, ..., l_n that need to be
stored on a tape. When a program is retrieved, the tape is positioned at the beginning, and it
spins forward until the desired program is found. The time it takes to retrieve a program is
proportional to its length plus the lengths of all programs stored before it on the tape. The
goal is to arrange the programs on the tape such that the mean retrieval time (or total
retrieval time) is minimized.
Greedy Approach: To minimize the total retrieval time, it makes intuitive sense to place the
shortest programs first. This ensures that the most frequently accessed (or simply, the
earliest accessed) programs are retrieved quickly, and their shorter lengths contribute less
to the retrieval time of subsequent programs.
1. Sort: Sort the programs in non-decreasing (ascending) order of their lengths.
2. Arrange: Place the programs on the tape in this sorted order.
Algorithm:
Plain Text
Function OptimalTapeStorage(program_lengths):
Sort(program_lengths) // Sort lengths in ascending order

total_retrieval_time = 0
current_prefix_sum = 0

For each length in program_lengths:

current_prefix_sum = current_prefix_sum + length
total_retrieval_time = total_retrieval_time + current_prefix_sum
 Return total_retrieval_time

Example:
Programs with lengths: [5, 10, 30]
1. Sorted: [5, 10, 30]
2. Arrangement: Program 5, then Program 10, then Program 30.
• Retrieval time for Program 5: 5
• Retrieval time for Program 10: 5 + 10 = 15
• Retrieval time for Program 30: 5 + 10 + 30 = 45
If we had arranged them differently, say [30, 10, 5] :
Plain Text
* Retrieval time for Program 30: `30`
* Retrieval time for Program 10: `30 + 10 = 40`
* Retrieval time for Program 5: `30 + 10 + 5 = 45`

Total retrieval time: `30 + 40 + 45 = 115`

Mean retrieval time: `115 / 3 = 38.33`

Clearly, the greedy approach yields a better (lower) total and mean retrieval time.
Proof of Optimality: This greedy strategy is optimal. Suppose there is an optimal
arrangement where a longer program L comes before a shorter program S . If we swap
L and S , the retrieval times for programs before S and after L remain unchanged.
However, the retrieval time for S decreases, and the retrieval time for L increases. Since
S is shorter than L , the decrease in S 's retrieval time is greater than the increase in
L 's retrieval time, leading to a net reduction in total retrieval time. This contradicts the
assumption of optimality, proving that the shortest-first arrangement is optimal.
Time Complexity: O(n log n) due to sorting, plus O(n) for calculating total retrieval time,
so overall O(n log n) .
Optimal Merge Patterns
Problem Statement: You are given n sorted files of different lengths (number of records).
You want to merge these files into a single sorted file. Merging two sorted files of lengths p
and q takes p + q time (or cost). The goal is to find an optimal merge pattern (the order in
which to merge the files) that minimizes the total cost of merging.
Greedy Approach: To minimize the total merge cost, it makes sense to always merge the
two smallest files available. This ensures that smaller files are merged early, and their
lengths contribute less to the cost of subsequent, larger merges.
This problem can be solved using a Huffman Coding-like approach or a min-priority
queue.
1. Initialize: Create a min-priority queue and insert all file lengths into it.
2. Iterate and Merge: While there is more than one file in the priority queue:
a. Extract the two smallest file lengths ( l1 and l2 ) from the priority queue.
b. Calculate the merge cost for these two files: cost = l1 + l2 .
c. Add cost to the total merge cost.
d. Insert the new merged file length ( l1 + l2 ) back into the priority queue.
3. Result: The total merge cost accumulated is the minimum possible.
Algorithm:
Plain Text
Function OptimalMergePattern(file_lengths):
// Use a min-priority queue
PQ = new MinPriorityQueue()
For each length in file_lengths:
[Link](length)

total_merge_cost = 0

While [Link]() > 1:

l1 = [Link]()
l2 = [Link]()

merge_cost_current = l1 + l2
total_merge_cost = total_merge_cost + merge_cost_current
 [Link](merge_cost_current)

Return total_merge_cost

Example:
File lengths: [20, 30, 10, 5]
1. Initial PQ: [5, 10, 20, 30]
2. Merge 1: Extract 5, 10. Cost = 5 + 10 = 15 . Total cost = 15 . Insert 15. PQ: [15, 20, 30]
3. Merge 2: Extract 15, 20. Cost = 15 + 20 = 35 . Total cost = 15 + 35 = 50 . Insert 35. PQ: [30,
35]
4. Merge 3: Extract 30, 35. Cost = 30 + 35 = 65 . Total cost = 50 + 65 = 115 . Insert 65. PQ:
[65]
Total optimal merge cost = 115 .
Proof of Optimality: This greedy strategy is optimal. The proof is similar to Huffman coding.
By always merging the two smallest files, we ensure that the smallest files (which are
accessed most frequently in the merge process) are combined early, minimizing their
contribution to the overall cost. Any other choice would lead to a higher total cost.
Time Complexity: If there are n files, we perform n-1 merge operations. Each operation
involves two ExtractMin and one Insert on a priority queue. If the priority queue is
implemented using a binary heap, these operations take O(log k) time, where k is the
number of elements in the queue. Since k goes from n down to 1, the total time
complexity is O(n log n) .
Single-Source Shortest Paths (Dijkstra's Algorithm)
Problem Statement: Given a weighted, directed graph and a source vertex s , find the
shortest paths from s to all other vertices in the graph. The edge weights must be non-
negative.
Greedy Approach (Dijkstra's Algorithm): Dijkstra's algorithm is a classic greedy algorithm.
It works by maintaining a set of vertices for which the shortest path from the source has
already been finalized. At each step, it greedily selects the unvisited vertex that has the
smallest known distance from the source.
1. Initialization:
• Set the distance to the source vertex s as 0 ( dist[s] = 0 ).
• Set the distance to all other vertices as infinity ( dist[v] = ∞ for v ≠ s ).
• Maintain a set of visited vertices (initially empty).
• Use a min-priority queue to store (distance, vertex) pairs, initially containing (0, s) .
2. Iteration: While the priority queue is not empty:
a. Extract the vertex u with the minimum distance from the priority queue.
b. If u has already been visited, continue (this handles duplicate entries in PQ).
c. Mark u as visited.
d. For each neighbor v of u :
i. If v is not visited and dist[u] + weight(u, v) < dist[v] :
* Update dist[v] = dist[u] + weight(u, v) .
* Insert/update (dist[v], v) in the priority queue.
Algorithm:
Plain Text
Function Dijkstra(Graph, source):
dist = new Array of size V, initialized to infinity
dist[source] = 0
visited = new Set, initially empty
PQ = new MinPriorityQueue()
[Link]((0, source)) // (distance, vertex)

While PQ is not empty:

(d, u) = [Link]()

If u is in visited:
Continue

Add u to visited
 For each neighbor v of u:
If v is not in visited:
If dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
[Link]((dist[v], v))

Return dist

Proof of Optimality: Dijkstra's algorithm is optimal for graphs with non-negative edge
weights. The proof relies on the fact that when a vertex u is extracted from the priority
queue, its distance dist[u] is guaranteed to be the shortest possible distance from the
source. This is because any other path to u would have to go through an unvisited vertex,
and all unvisited vertices currently have distances greater than or equal to dist[u] (due to
the greedy selection from the priority queue).
Time Complexity:
• Adjacency Matrix Representation: O(V^2) (where V is the number of vertices). This
is because finding the minimum distance vertex takes O(V) time in each of V
iterations.
• Adjacency List Representation with Binary Heap: O(E log V) or O(E + V log V) . E
insertions/updates and V ExtractMin operations. Each ExtractMin takes O(log V) .
Each decrease-key (update) takes O(log V) . In the worst case, all E edges might lead
to decrease-key operations.
• Adjacency List Representation with Fibonacci Heap: O(E + V log V) . This is the
theoretically fastest for dense graphs, but Fibonacci heaps have high constant factors
and are rarely used in practice.
Limitations:
• Non-Negative Edge Weights: Dijkstra's algorithm does not work correctly with negative
edge weights. For graphs with negative weights, algorithms like Bellman-Ford or SPFA
must be used.
Basic Traversal and Search Techniques
Graph traversal algorithms are systematic procedures for visiting all the nodes (vertices) and
edges of a graph. They are fundamental to many graph algorithms.
Techniques for Binary Trees
Binary trees are hierarchical data structures where each node has at most two children,
referred to as the left child and the right child. Common traversal methods for binary trees
are:
1. Inorder Traversal (Left, Root, Right):
• Process: Recursively traverse the left subtree, visit the root node, then recursively
traverse the right subtree.
• Use Case: For Binary Search Trees (BSTs), inorder traversal visits nodes in non-
decreasing order of their values, which is useful for printing sorted elements.
• Example: For a BST, Inorder(Root) :
1. Inorder([Link])
2. Print [Link]
3. Inorder([Link])
2. Preorder Traversal (Root, Left, Right):
• Process: Visit the root node, then recursively traverse the left subtree, then
recursively traverse the right subtree.
• Use Case: Useful for creating a copy of the tree, or for expressing a tree structure
(e.g., in an XML-like format).
• Example: Preorder(Root) :
1. Print [Link]
2. Preorder([Link])
3. Preorder([Link])
 3. Postorder Traversal (Left, Right, Root):
• Process: Recursively traverse the left subtree, then recursively traverse the right
subtree, then visit the root node.
• Use Case: Useful for deleting a tree (delete children first, then parent), or for
evaluating expression trees.
• Example: Postorder(Root) :
1. Postorder([Link])
2. Postorder([Link])
3. Print [Link]
4. Level Order Traversal (Breadth-First Traversal):
• Process: Visit nodes level by level, from left to right. Uses a queue data structure.
• Algorithm:
1. Create an empty queue and enqueue the root node.
2. While the queue is not empty:
a. Dequeue a node.
b. Process (visit) the dequeued node.
c. Enqueue its left child (if exists).
d. Enqueue its right child (if exists).
• Use Case: Finding the shortest path in an unweighted tree, or for visualizing the tree
level by level.
Techniques for Graphs
Graph traversal algorithms systematically explore the vertices and edges of a graph. The
two most common are Breadth-First Search (BFS) and Depth-First Search (DFS).
1. Breadth-First Search (BFS):
 • Concept: Explores a graph level by level. It starts at a source vertex, visits all its
immediate neighbors, then all their unvisited neighbors, and so on.
• Data Structure: Uses a queue to keep track of vertices to visit.
• Algorithm:
1. Create a queue Q and enqueue the starting vertex s .
2. Mark s as visited.
3. While Q is not empty:
a. Dequeue a vertex u .
b. Process u .
c. For each unvisited neighbor v of u :
i. Mark v as visited.
ii. Enqueue v .
• Time Complexity: O(V + E) (where V is number of vertices, E is number of edges)
for both adjacency list and adjacency matrix representations.
• Use Cases: Finding the shortest path in an unweighted graph, finding connected
components, crawling web pages, peer-to-peer networks.
2. Depth-First Search (DFS):
• Concept: Explores as far as possible along each branch before backtracking. It goes
deep into the graph before exploring other branches.
• Data Structure: Uses a stack (explicitly or implicitly via recursion) to keep track of
vertices to visit.
• Algorithm (Recursive):
1. DFS(u) :
a. Mark u as visited.
b. Process u .
c. For each unvisited neighbor v of u :
i. DFS(v)
 • Time Complexity: O(V + E) for both adjacency list and adjacency matrix
representations.
• Use Cases: Finding connected components, topological sorting, cycle detection,
pathfinding, solving mazes.
Connected Components and Spanning Trees
Connected Components
• Definition: A connected component of an undirected graph is a subgraph in which any
two vertices are connected to each other by paths, and which is connected to no
additional vertices in the supergraph. A graph can have one or more connected
components.
• Finding Connected Components: Both BFS and DFS can be used to find connected
components.
• Start a traversal (BFS or DFS) from an arbitrary unvisited vertex. All vertices reachable
from this starting vertex form one connected component.
• Repeat the process from another unvisited vertex until all vertices have been visited.
• Time Complexity: O(V + E) to find all connected components.
Spanning Trees
• Definition: A spanning tree of a connected, undirected graph G = (V, E) is a subgraph
that is a tree and connects all the vertices in V together. It contains all V vertices and
exactly V-1 edges.
• Relationship to Traversal: Both BFS and DFS naturally produce spanning trees:
• BFS Spanning Tree: The edges used during a BFS traversal to reach unvisited
vertices form a BFS spanning tree. This tree has the property that the path from the
root to any node is the shortest path in terms of number of edges.
• DFS Spanning Tree: The edges used during a DFS traversal to explore new vertices
form a DFS spanning tree. This tree can be very deep and narrow.
 • Minimum Spanning Tree (MST): As discussed earlier, an MST is a spanning tree with
the minimum possible total edge weight. Kruskal's and Prim's algorithms are used to
find MSTs.
Biconnected Components and DFS
Biconnected Components
• Definition: A connected graph is biconnected if it remains connected even after
removing any single vertex. If a graph is not biconnected, the vertices whose removal
disconnects the graph are called articulation points (or cut vertices).
• A biconnected component (BCC) is a maximal biconnected subgraph. This means it's a
subgraph that is biconnected, and you cannot add any more vertices or edges to it and
still have it be biconnected.
• Importance: Identifying articulation points and biconnected components is crucial in
network reliability. If an articulation point fails, the network might become
disconnected.
Finding Biconnected Components using DFS
Biconnected components can be found efficiently using a single Depth-First Search (DFS)
traversal. The algorithm involves keeping track of discovery times and low-link values for
each vertex.
Key Concepts:
• Discovery Time ( disc[u] ): The time (or order) at which vertex u is first visited during
DFS.
• Low-Link Value ( low[u] ): The lowest discovery time reachable from u (including u
itself) through the DFS tree edges and at most one back-edge.
Algorithm Steps (High-Level):
1. Perform a DFS traversal starting from an arbitrary vertex.
2. During DFS, maintain disc[u] and low[u] for each vertex u .
 3. For each vertex u and its child v in the DFS tree:
a. If v is not visited, recursively call DFS on v .
b. After the recursive call returns, update low[u] = min(low[u], low[v]) .
c. If low[v] >= disc[u] , then u is an articulation point (unless u is the root of the DFS
tree and has only one child). The subtree rooted at v (including the edge (u,v) ) forms
a biconnected component with u .
d. If v is already visited and v is not the parent of u (i.e., (u,v) is a back-edge),
update low[u] = min(low[u], disc[v]) .
4. Edges are pushed onto a stack as they are traversed. When an articulation point u is
found (or the DFS returns from a child v such that low[v] >= disc[u] ), all edges from the
stack until (u,v) (inclusive) form a biconnected component.
Time Complexity: O(V + E) because it involves a single DFS traversal.
This concludes the discussion on Greedy Methods and Basic Traversal Techniques. These
algorithms form the backbone of many solutions in graph theory and optimization.

UNIT-IV: Dynamic Programming and Backtracking

The General Method (Dynamic Programming)
Dynamic Programming (DP) is a powerful algorithmic technique for solving optimization
problems by breaking them down into simpler overlapping subproblems and storing the
solutions to these subproblems to avoid recomputing them. It is particularly effective for
problems that exhibit two key properties:
1. Optimal Substructure: An optimal solution to the problem contains optimal solutions
to its subproblems. This means that if you have an optimal solution to the overall
problem, then the parts of that solution must also be optimal solutions to their
respective subproblems.
2. Overlapping Subproblems: The same subproblems are encountered and solved
repeatedly by a recursive algorithm. Dynamic programming solves each subproblem
 only once and stores its solution, typically in a table or array, so that it can be looked up
when needed again.
Contrast with Divide-and-Conquer:
While both Dynamic Programming and Divide-and-Conquer break problems into
subproblems, the key difference lies in how they handle subproblems:
• Divide-and-Conquer: Subproblems are independent. Once a subproblem is solved, its
solution is combined, and it's not typically revisited. (e.g., Merge Sort, Quick Sort).
• Dynamic Programming: Subproblems are overlapping. The same subproblems appear
multiple times. DP solves each unique subproblem once and stores the result.
Two Approaches to Dynamic Programming:
1. Top-Down (Memoization):
• This is a recursive approach. You write the recursive solution to the problem.
• Before computing a subproblem, check if its solution is already stored in a lookup
table (memo). If yes, return the stored value.
• If not, compute the solution, store it in the memo, and then return it.
• This approach is intuitive as it directly follows the recursive definition of the problem.
2. Bottom-Up (Tabulation):
• This is an iterative approach. You solve the smallest subproblems first and then build
up solutions to larger subproblems using the solutions of smaller ones.
• You typically fill a table (or array) in a specific order, ensuring that all necessary
subproblem solutions are available when needed.
• This approach avoids recursion overhead and can be more space-efficient in some
cases.
Steps to Design a Dynamic Programming Solution:
 1. Characterize Optimal Substructure: Show that an optimal solution to the problem
contains optimal solutions to subproblems.
2. Define a Recursive Solution: Define the value of an optimal solution recursively in
terms of optimal solutions to subproblems.
3. Compute the Optimal Solution (Bottom-Up or Top-Down): Compute the value of an
optimal solution. If using bottom-up, determine the order in which to fill the table.
4. Construct an Optimal Solution (Optional): If needed, reconstruct the actual optimal
solution, not just its value.
Multistage Graphs
Problem Statement: A multistage graph is a directed acyclic graph (DAG) where the vertices
are partitioned into k stages, V = V1 ∪ V2 ∪ ... ∪ Vk , such that if (u, v) is an edge, then u ∈
Vi and v ∈ Vi+1 for some stage i . The cost of an edge (u, v) is c(u, v) . The problem is to
find a minimum-cost path from a source s (in V1 ) to a sink t (in Vk ).
Example: Finding the shortest path from stage 1 to stage k .
Dynamic Programming Approach:
This problem exhibits optimal substructure: the shortest path from s to t passing
through a vertex u at stage i must contain a shortest path from s to u and a shortest
path from u to t .
We can solve this using either a forward or backward approach.
Forward Approach (from source to sink):
Let cost[i] be the minimum cost to reach vertex i from the source s .
• cost[s] = 0
• For all other vertices v , cost[v] = ∞ .
Iterate stage by stage from V1 to Vk .
For each vertex u in stage i :
For each edge (u, v) where v is in stage i+1 :
cost[v] = min(cost[v], cost[u] + c(u, v))
Backward Approach (from sink to source):
Let cost[i] be the minimum cost to reach the sink t from vertex i .
• cost[t] = 0
• For all other vertices u , cost[u] = ∞ .
Iterate stage by stage from Vk-1 down to V1 .
For each vertex u in stage i :
For each edge (u, v) where v is in stage i+1 :
cost[u] = min(cost[u], c(u, v) + cost[v])
The final answer will be cost[s] (from the backward approach) or cost[t] (from the forward
approach).
Time Complexity: O(V + E) , where V is the number of vertices and E is the number of
edges. This is because each vertex and edge is processed a constant number of times.
All Pairs Shortest Paths (Floyd-Warshall Algorithm)
Problem Statement: Given a weighted, directed graph, find the shortest paths between all
pairs of vertices. Edge weights can be positive or negative, but no negative cycles.
Dynamic Programming Approach:
The Floyd-Warshall algorithm uses dynamic programming. It considers intermediate
vertices on paths. Let dist[i][j][k] be the shortest path from vertex i to vertex j using only
vertices from {1, 2, ..., k} as intermediate vertices.
• Base Case: dist[i][j][0] is the weight of the direct edge from i to j (or infinity if no
direct edge).
• Recursive Relation:
dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])
This means the shortest path from i to j using intermediate vertices up to k is either:
1. The shortest path from i to j using intermediate vertices up to k-1 (i.e., k is not an
intermediate vertex).
2. The shortest path from i to k using intermediate vertices up to k-1 , plus the
shortest path from k to j using intermediate vertices up to k-1 (i.e., k is an
intermediate vertex).
We can optimize space by removing the k dimension, as dist[i][j][k] only depends on
dist[i][j][k-1] , dist[i][k][k-1] , and dist[k][j][k-1] .
Algorithm (Iterative):
Plain Text
Function FloydWarshall(graph):
n = number of vertices
dist = new n x n matrix, initialized with direct edge weights

For k from 0 to n-1: // k is the intermediate vertex

For i from 0 to n-1:
For j from 0 to n-1:
If dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]

Return dist

Time Complexity: O(V^3) due to the three nested loops, where V is the number of
vertices.
Space Complexity: O(V^2) to store the distance matrix.
Limitations: Cannot handle negative cycles. If dist[i][i] becomes negative after the
algorithm, it indicates a negative cycle.
Single-Source Shortest Paths: General Weights (Bellman-Ford
Algorithm)
Problem Statement: Given a weighted, directed graph and a source vertex s , find the
shortest paths from s to all other vertices. Edge weights can be positive or negative. The
graph must not contain any negative cycles reachable from the source.
Dynamic Programming Approach:
The Bellman-Ford algorithm uses dynamic programming to relax edges repeatedly. It works
by making V-1 passes over all edges. In each pass, it tries to improve the shortest path
estimates to all vertices.
Let dist[v] be the shortest distance from the source s to vertex v .
• Initialization:
• dist[s] = 0
• dist[v] = ∞for all v ≠ s
• Relaxation: For each edge (u, v) with weight w :
dist[v] = min(dist[v], dist[u] + w)
Algorithm:
Plain Text
Function BellmanFord(graph, source):
n = number of vertices
dist = new Array of size n, initialized to infinity
dist[source] = 0

// Relax all edges V-1 times

For count from 1 to n-1:
For each edge (u, v) with weight w in graph:
If dist[u] != infinity and dist[u] + w < dist[v]:
dist[v] = dist[u] + w

// Check for negative cycles

For each edge (u, v) with weight w in graph:
If dist[u] != infinity and dist[u] + w < dist[v]:
Return

Error: Graph contains a negative cycle

 Return dist

Time Complexity: O(V * E) , where V is the number of vertices and E is the number of
edges. This is because there are V-1 passes, and in each pass, all E edges are relaxed.
Space Complexity: O(V) to store distances.
Advantages:
• Can handle negative edge weights.
• Can detect negative cycles.
Disadvantages:
• Slower than Dijkstra's algorithm for graphs with non-negative edge weights.

Optimal Binary Search Trees

Problem Statement: Given a sorted sequence of n keys k1 < k2 < ... < kn , and for each key
ki , a probability pi that a search will be for ki . Also, for each interval between keys (ki,
ki+1) (including (-∞, k1) and (kn, ∞) ), a probability qi that a search will be for a value
not in the set of keys, but within that interval. The goal is to construct a Binary Search Tree
(BST) that minimizes the expected search cost.
Expected Search Cost: The expected search cost is Σ (depth(ki) + 1) * pi + Σ (depth(di) + 1) * qi ,
where depth(ki) is the depth of internal node ki and depth(di) is the depth of external
node di (representing dummy nodes for intervals).
Dynamic Programming Approach:
This problem exhibits optimal substructure. If a key kr is the root of an optimal BST for
keys ki...kj , then its left subtree must be an optimal BST for keys ki...kr-1 and its right
subtree must be an optimal BST for keys kr+1...kj . The subproblems are defined by ranges
of keys (i, j) .
Let cost[i][j] be the minimum expected search cost for a BST containing keys ki...kj .
 • Base Cases:
• cost[i][i-1] = qi-1 (cost of an empty tree, only dummy node)
• cost[i][i] = pi + qi-1 + qi (cost of a tree with one key ki as root)
• Recursive Relation: To compute cost[i][j] , we try every possible key r (where i ≤ r ≤
j ) as the root. The cost for kr as root is cost[i][r-1] (left subtree) + cost[r+1][j] (right
subtree) + sum_probabilities(i, j) (cost of accessing the root and all nodes in its subtree).
Algorithm (Bottom-Up):
1. Initialize a 2D array cost[n+1][n] and root[n+1][n] .
2. Initialize base cases for cost[i][i-1] and cost[i][i] .
3. Iterate for chain length L from 2 to n :
For i from 1 to n - L + 1 :
j=i+L-1
cost[i][j] = infinity
W = sum_probabilities(i, j)
For r from i to j (try each kr as root):
current_cost = cost[i][r-1] + cost[r+1][j] + W
If current_cost < cost[i][j] :
cost[i][j] = current_cost
root[i][j] = r
Time Complexity: O(n^3) due to three nested loops (for L , i , and r ).
Space Complexity: O(n^2) for cost and root tables.
String Editing (Edit Distance / Levenshtein Distance)
Problem Statement: Given two strings, str1 and str2 , find the minimum number of
operations required to transform str1 into str2 . The allowed operations are:
• Insertion: Insert a character.
• Deletion: Delete a character.
 • Substitution: Replace a character.
Each operation has a cost (usually 1).
Dynamic Programming Approach:
This problem exhibits optimal substructure. The edit distance between two strings can be
found by considering the edit distance of their prefixes. Let dp[i][j] be the minimum edit
distance between str1[0...i-1] (prefix of length i ) and str2[0...j-1] (prefix of length j ).
• Base Cases:
• dp[i][0] = i (to transform a prefix of str1 into an empty string, i deletions are
needed).
• dp[0][j] = j (to transform an empty string into a prefix of str2 , j insertions are
needed).
• Recursive Relation: For i > 0 and j > 0 :
• If str1[i-1] == str2[j-1] (characters match):
dp[i][j] = dp[i-1][j-1] (no cost for this character)
• If str1[i-1] != str2[j-1] (characters don't match):
dp[i][j] = 1 + min(dp[i-1][j], // Deletion from str1
dp[i][j-1], // Insertion into str1 (or deletion from str2)
dp[i-1][j-1]) // Substitution
Algorithm (Bottom-Up):
1. Create a (m+1) x (n+1) table dp , where m is length of str1 and n is length of str2 .
2. Initialize the first row and first column with base cases.
3. Fill the rest of the table using the recursive relation.
Plain Text
Function EditDistance(str1, str2):
m = length(str1)
n = length(str2)
 dp = new (m+1) x (n+1) 2D array

For i from 0 to m:
dp[i][0] = i
For j from 0 to n:
dp[0][j] = j

For i from 1 to m:
For j from 1 to n:
If str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1]
Else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Return dp[m][n]

Time Complexity: O(m * n) , where m and n are the lengths of the two strings.
Space Complexity: O(m * n) for the dp table. Can be optimized to O(min(m, n)) by only
keeping track of the previous row/column.
0/1-Knapsack
Problem Statement: You have a knapsack with a maximum weight capacity W . You are
given n items, each with a weight w_i and a value v_i . You cannot take fractions of
items (you either take the whole item or none of it). The goal is to select a subset of items
that maximizes the total value while not exceeding the knapsack's weight capacity.
Dynamic Programming Approach:
This problem exhibits optimal substructure and overlapping subproblems. The decision for
each item (take it or not take it) depends on the remaining capacity and the values of
previous items. Let dp[i][w] be the maximum value that can be obtained from the first i
items with a knapsack capacity of w .
• Base Cases:
• dp[0][w] = 0 for all w (no items, no value).
• dp[i][0] = 0 for all i (no capacity, no value).
• Recursive Relation: For i > 0 and w > 0 :
 • If w_i > w (current item is too heavy for current capacity):
dp[i][w] = dp[i-1][w] (cannot include item i , so value is same as without item i )
• Else (current item can potentially be included):
dp[i][w] = max(dp[i-1][w], // Option 1: Don't include item i
v_i + dp[i-1][w - w_i]) // Option 2: Include item i
Algorithm (Bottom-Up):
1. Create a (n+1) x (W+1) table dp .
2. Initialize the first row and column to 0.
3. Fill the table using the recursive relation.
Plain Text
Function Knapsack01(weights, values, W):
n = length(weights) // Number of items
dp = new (n+1) x (W+1) 2D array

For i from 0 to n:
For w from 0 to W:
If i == 0 or w == 0:
dp[i][w] = 0
Else if weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-
1][w])
Else:
dp[i][w] = dp[i-1][w]

Return dp[n][W]

Time Complexity: O(n * W) , where n is the number of items and W is the knapsack
capacity.
Space Complexity: O(n * W) for the dp table. Can be optimized to O(W) by only keeping
track of the previous row.
Reliability Design
Problem Statement: Consider a system composed of multiple devices connected in series.
Each device i has a certain reliability r_i (probability of not failing) and a cost c_i . To
improve the system's overall reliability, we can add redundant devices in parallel. If we have
m_i identical devices in parallel for device i , the reliability of that stage becomes 1 - (1 -
r_i)^m_i . There is a total budget C for the system. The goal is to determine the number of
redundant devices m_i for each stage i such that the overall system reliability is
maximized, without exceeding the total budget.
Dynamic Programming Approach:
This problem has optimal substructure. The optimal reliability for the entire system can be
built from optimal reliabilities of its sub-systems. Let dp[i][j] be the maximum reliability
that can be achieved for the first i stages with a total cost of j .
• Base Case: dp[0][j] = 1 if j >= 0 (reliability of 0 stages is 1, with any cost). dp[0][j] = 0 if
j < 0 (or negative infinity for log-reliability).
• Recursive Relation: To compute dp[i][j] , we consider adding k redundant devices
for stage i . The cost for stage i with k devices is k * c_i , and its reliability is 1 - (1 -
r_i)^k . The remaining cost j - k * c_i must be used for the previous i-1 stages.
Algorithm (Bottom-Up):
1. Create a (num_stages+1) x (budget+1) table dp (or log_dp ).
2. Initialize dp[0][j] = 1 (or log_dp[0][j] = 0 ).
3. Iterate i from 1 to num_stages :
Iterate j from 0 to budget :
dp[i][j] = 0 (or negative infinity for log_dp )
Iterate k from 1 to max_devices_for_stage_i :
cost_k = k * c_i
If j >= cost_k :
current_reliability = (1 - (1 - r_i)^k)
dp[i][j] = max(dp[i][j], current_reliability * dp[i-1][j - cost_k])
Time Complexity: O(num_stages * budget * max_devices_per_stage) . If max_devices_per_stage is
bounded by a constant, it's O(num_stages * budget) .
Space Complexity: O(num_stages * budget) .
The Traveling Salesperson Problem (TSP)
Problem Statement: Given a list of cities and the distances between each pair of cities, find
the shortest possible route that visits each city exactly once and returns to the origin city.
Nature of the Problem: TSP is a classic NP-hard problem. This means there is no known
polynomial-time algorithm to solve it exactly. However, dynamic programming can solve it
for a relatively small number of cities.
Dynamic Programming Approach (for exact solution):
This approach is often called the Held-Karp algorithm. It uses bitmasking to represent the
set of visited cities.
Let dp[mask][i] be the minimum cost to visit all cities represented by mask , ending at city
i . The mask is a bitmask where the j -th bit is set if city j has been visited.
• Base Case: dp[1 << source_city][source_city] = 0 (cost to visit only the source city, ending at
source, is 0).
• Recursive Relation: To compute dp[mask][i] , we consider all possible previous cities
j that were visited before i in the path represented by mask .
Algorithm (Bottom-Up):
1. Initialize dp table with infinity.
2. Set dp[1 << 0][0] = 0 (assuming city 0 is the source).
3. Iterate mask from 1 to 2^n - 1 (all possible subsets of cities):
For each city i from 0 to n-1 :
If i -th bit is set in mask :
For each city j from 0 to n-1 :
If j != i and j -th bit is set in mask :
 prev_mask = mask ^ (1 << i)
dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])
4. After filling the table, the final answer is min_{i=1 to n-1} (dp[(1 << n) - 1][i] + dist[i]
[source_city]) .
Time Complexity: O(n^2 * 2^n) . There are 2^n possible masks, n possible ending cities,
and n possible previous cities.
Space Complexity: O(n * 2^n) for the dp table.
Limitations: This approach is only feasible for small n (typically up to 20-25 cities) due to
the exponential complexity.
Flow Shop Scheduling
Problem Statement: You have n jobs, and each job must be processed on m machines
in a specific order (e.g., Machine 1, then Machine 2, ..., then Machine m ). Each job j has a
processing time P_ij on machine i . The goal is to find a schedule (the order of jobs) that
minimizes the makespan (the total time required to complete all jobs).
Nature of the Problem: Flow shop scheduling is generally NP-hard for m ≥ 3 machines.
For m=2 machines, Johnson's Rule provides an optimal greedy solution. For m > 2 ,
dynamic programming can be used for smaller instances, or approximation
algorithms/heuristics for larger ones.
Dynamic Programming Approach (for m machines, small n ):
This is a complex problem, and a general DP solution for m machines is often quite
involved. For simplicity, let's consider a common variant or a simplified DP approach.
If we are looking for an optimal permutation of jobs, we can use a state dp[mask][last_job]
representing the minimum makespan for the jobs in mask , with last_job being the last job
processed in that sequence.
• State: dp[mask][last_job] = minimum makespan for the subset of jobs represented by
mask , where last_job is the job that finishes last in the sequence.
 • Recursive Relation: To compute dp[mask][last_job] , we consider all prev_job in mask
(excluding last_job ). The makespan for mask ending with last_job is dp[mask ^ (1 <<
last_job)][prev_job] plus the processing time of last_job on all machines, considering its
start time on each machine.
Time Complexity: O(n! * m) for brute force. The DP approach with bitmasking would be
O(n * 2^n * m) if we can efficiently transition states. However, the state definition and
transitions for m > 2 are complex, making it practically O(n^2 * 2^n * m) or worse.
Space Complexity: O(2^n * m) or O(2^n) depending on state representation.
Backtracking: The General Method
Backtracking is a general algorithmic technique for solving problems that involve searching
for a solution among a set of choices. It systematically explores all possible solutions by
trying to build a solution incrementally, one piece at a time. If a partial solution is found to
be invalid or cannot lead to a complete solution, the algorithm
backtracks (undoes its last choice) and tries another alternative. This process continues
until a valid solution is found or all possibilities have been exhausted.
Key Characteristics of Backtracking:
1. State-Space Tree: Backtracking algorithms can be visualized as searching a state-space
tree. Each node in the tree represents a partial solution, and the children of a node
represent the choices that can be made to extend that partial solution.
2. Depth-First Search (DFS): Backtracking typically uses a depth-first search approach to
explore the state-space tree.
3. Pruning: The core idea of backtracking is to prune branches of the search tree that
cannot possibly lead to a valid solution. This is done by checking constraints at each
step. If a partial solution violates a constraint, the algorithm stops exploring that path
and backtracks.
When to use Backtracking:
• Problems that involve finding all (or some) solutions that satisfy certain constraints.
 • Problems that can be modeled as a sequence of choices.
• Optimization problems where you need to find the best solution among many
possibilities.
General Structure of a Backtracking Algorithm:
Plain Text
Function Solve(current_state):
If current_state is a complete and valid solution:
Add current_state to solutions
Return // Or continue if all solutions are needed

If current_state is invalid or cannot lead to a solution:

Return // Prune this path

For each choice in possible_choices_from(current_state):

Apply choice to current_state (make a move)
Solve(new_state) // Recurse
Undo choice (backtrack) // Revert to previous state for next choice

Advantages of Backtracking:
• Systematic Search: Guarantees finding all solutions (if they exist) or determining that
no solution exists.
• Pruning: Can significantly reduce the search space by eliminating invalid paths early.
• Versatility: Applicable to a wide range of combinatorial problems.
Disadvantages of Backtracking:
• High Time Complexity: Even with pruning, the worst-case time complexity can be
exponential or factorial, making it impractical for very large problem instances.
• Memory Usage: Recursive calls can consume significant stack space.
• Problem-Specific Pruning: The effectiveness of pruning depends heavily on finding
good problem-specific constraints.
The 8-Queens Problem
Problem Statement: Place eight chess queens on an 8x8 chessboard such that no two
queens threaten each other. A queen can attack horizontally, vertically, and diagonally.
Backtracking Approach:
We can try to place queens one by one, column by column (or row by row). For each column,
we try to place a queen in a row. If a placement is safe (doesn't conflict with previously
placed queens), we move to the next column. If no safe row is found in the current column,
we backtrack to the previous column and try a different row for the queen there.
Algorithm:
1. Start with an empty board.
2. Place the first queen in column 0.
3. For each column col from 0 to 7:
a. For each row row from 0 to 7:
i. If placing a queen at (row, col) is safe (i.e., it doesn't conflict with any queen already
placed in columns 0 to col-1 ):
* Place the queen at (row, col) .
* Recursively call the function for col + 1 .
* If the recursive call returns true (meaning a solution was found), then return true.
* Backtrack: If the recursive call returns false (no solution found from this path),
remove the queen from (row, col) and try the next row.
b. If no row in the current col allows a safe placement, return false (triggering
backtracking).
Safety Check: A position (row, col) is safe if:
• No other queen is in the same row .
• No other queen is in the same column (this is handled by placing one queen per
column).
• No other queen is on the same main diagonal ( row - col is constant).
• No other queen is on the same anti-diagonal ( row + col is constant).
Time Complexity: The worst-case time complexity is roughly O(n!) because, in the worst
case, it might explore all n! permutations of queen placements. However, pruning
significantly reduces the actual search space.
Sum of Subsets
Problem Statement: Given a set of positive integers S = {s1, s2, ..., sn} and a target sum D ,
find all subsets of S whose elements sum up to D .
Backtracking Approach:
We can build subsets by considering each element one by one. For each element, we have
two choices: either include it in the current subset or exclude it. We explore both paths
recursively.
Algorithm:
1. Sort the input set S in ascending order (optional but can help with pruning).
2. Start with an empty current subset and a current sum of 0.
3. For each element s_i in S :
a. Include s_i : Add s_i to the current subset. Add s_i to the current sum.
Recursively call the function for the next element.
b. Exclude s_i : Remove s_i from the current subset (if it was added). Subtract s_i
from the current sum (if it was added). Recursively call the function for the next
element.
Pruning Conditions:
• If current_sum == D , a solution is found. Print the current subset.
• If current_sum > D , this path cannot lead to a solution. Backtrack.
• If current_sum + remaining_elements_sum < D , this path cannot lead to a solution (even if
all remaining elements are included, the sum won't reach D ). Backtrack.
Time Complexity: In the worst case, it explores O(2^n) subsets, where n is the number of
elements in the set. Pruning can reduce this significantly.
Graph Coloring
Problem Statement: Given a graph and a number m (number of colors), assign a color to
each vertex such that no two adjacent vertices have the same color. The goal is to find all
possible m -colorings of the graph.
Backtracking Approach:
We try to color vertices one by one. For each vertex, we try assigning each of the m
available colors. If a color assignment is valid (doesn't conflict with already colored adjacent
vertices), we move to the next vertex. If no valid color is found for the current vertex, we
backtrack.
Algorithm:
1. Start with all vertices uncolored.
2. For each vertex v from 0 to V-1 (number of vertices):
a. For each color c from 1 to m :
i. If assigning c to v is safe (i.e., no adjacent vertex u is already colored c ):
* Assign c to v .
* Recursively call the function for v + 1 .
* If the recursive call returns true (a valid coloring was found for the rest of the graph),
then return true.
* Backtrack: If the recursive call returns false, unassign c from v and try the next
color.
b. If no color can be safely assigned to v , return false (triggering backtracking).
Safety Check: A color c can be assigned to vertex v if for every neighbor u of v ,
color[u] != c .
Time Complexity: The worst-case time complexity is O(m^V) , where V is the number of
vertices and m is the number of colors. This is because for each of V vertices, there are
m choices. Pruning helps, but it remains exponential.

Hamiltonian Cycles
Problem Statement: Given a graph, find a Hamiltonian cycle. A Hamiltonian cycle is a cycle
in an undirected or directed graph that visits each vertex exactly once and returns to the
starting vertex.
Backtracking Approach:
We start at an arbitrary vertex and try to build a path by adding adjacent vertices one by
one. We keep track of visited vertices. If we reach a point where no unvisited adjacent vertex
can be added, or if we get stuck, we backtrack.
Algorithm:
1. Start at a chosen source vertex (e.g., vertex 0). Mark it as visited and add it to the current
path.
2. Recursively try to extend the path:
a. For the current vertex u , iterate through all its unvisited neighbors v .
b. If v is a valid next vertex (unvisited and adjacent to u ):
i. Add v to the path. Mark v as visited.
ii. Recursively call the function for v .
iii. If the recursive call returns true (a Hamiltonian cycle was found), return true.
iv. Backtrack: If the recursive call returns false, remove v from the path and mark v
as unvisited.
3. Base Case: If the path length equals the total number of vertices V , check if the last
vertex in the path is adjacent to the starting vertex. If yes, a Hamiltonian cycle is found.
Return true.
4. If no valid next vertex can be found, or if all paths from the current vertex have been
explored without finding a cycle, return false.
Time Complexity: In the worst case, it explores O(V!) paths, which is factorial. This is
highly inefficient for large graphs.
Knapsack Problem (0/1 Knapsack - Revisited with Backtracking)
While the 0/1 Knapsack problem is typically solved using dynamic programming for optimal
efficiency, it can also be approached with backtracking, especially if you need to find all
possible subsets that meet the criteria, or if the constraints are such that a branch-and-
bound approach (an extension of backtracking) is more suitable.
Problem Statement: Same as before: given items with weights and values, and a knapsack
capacity W , select items to maximize total value without exceeding W . Each item can
either be taken or not taken.
Backtracking Approach:
We explore a decision tree where at each node, we decide whether to include the current
item or exclude it. We keep track of the current weight and current value.
Algorithm:
1. Sort items by value-to-weight ratio (optional, but can help pruning).
2. Start with current_weight = 0 , current_value = 0 , and item_index = 0 .
3. Recursively explore choices for each item:
a. Include Item i :
i. If current_weight + weights[i] <= W :
* Add weights[i] to current_weight .
* Add values[i] to current_value .
* Recursively call for item_index + 1 .
* Backtrack: Remove weights[i] and values[i] from current totals.
b. Exclude Item i :
i. Recursively call for item_index + 1 .
Pruning/Optimization:
• Bound Function: To find the maximum value, we need a way to prune branches that
cannot lead to a better solution than the best one found so far. A common bound
function estimates the maximum possible value that can be obtained from the
remaining items if we take them fractionally (like in Fractional Knapsack). If
current_value + estimated_remaining_value <= best_value_found_so_far , then prune this
branch.
• If current_weight > W , this path is invalid. Backtrack.
 • When item_index reaches n , a complete subset has been formed. Update max_value
if current_value is greater.
Time Complexity: In the worst case, it explores O(2^n) subsets, similar to the Sum of
Subsets problem. The effectiveness of pruning depends on the quality of the bound
function and the problem instance. For the 0/1 Knapsack, dynamic programming is
generally preferred for its polynomial time complexity ( O(nW) ), while backtracking is used
when n is small or when combined with branch-and-bound techniques.

UNIT-V: Advanced Topics

Branch-and-Bound: The Method
Branch-and-Bound (B&B) is an algorithmic paradigm, primarily used for solving discrete and
combinatorial optimization problems. These are problems where the goal is to find an
optimal solution among a large (often exponentially large) set of possible solutions. B&B is
an improvement over backtracking, as it not only systematically explores the solution space
but also uses bounding functions to prune branches that cannot possibly lead to an optimal
solution.
Key Concepts:
1. State Space Tree: Similar to backtracking, B&B explores a state-space tree. Each node
in the tree represents a partial solution, and the leaves represent complete solutions.
2. Branching: The process of dividing the problem into smaller subproblems, represented
by the children nodes in the state-space tree. This is the
creation of new subproblems from the current problem.
1. Bounding: The crucial part of B&B. For each partial solution (node in the tree), a lower
bound (for minimization problems) or an upper bound (for maximization problems) on
the cost of any complete solution that can be derived from this partial solution is
calculated. This bound helps in pruning.
 2. Pruning: If the calculated bound for a partial solution is worse than the best solution
found so far (the current
upper bound for minimization, or lower bound for maximization), then that entire branch of
the tree can be pruned. This is because no solution in that branch can be better than the
one already found.
Search Strategies:
Branch-and-Bound is not tied to a specific search strategy. The choice of which node to
explore next can significantly impact performance. Common strategies include:
• FIFO (First-In, First-Out) Branch-and-Bound: Explores nodes in a breadth-first
manner. Uses a queue to store live nodes.
• LIFO (Last-In, First-Out) Branch-and-Bound: Explores nodes in a depth-first manner.
Uses a stack to store live nodes. This is similar to backtracking but with bounding.
• Least-Cost (or Best-First) Branch-and-Bound: Always explores the node with the best
bound (lowest cost for minimization, highest value for maximization). Uses a priority
queue to store live nodes. This strategy often finds the optimal solution faster by
focusing on the most promising branches.
General Algorithm (for a minimization problem):
1. Initialize a priority queue to store live nodes (partial solutions).
2. Initialize upper_bound = infinity (or the cost of a known feasible solution).
3. Start with the root node (representing the initial problem) and add it to the priority
queue.
4. While the priority queue is not empty:
a. Extract the node N with the best (lowest) bound from the priority queue.
b. If the bound of N is greater than or equal to upper_bound , prune this node and
continue.
c. If N represents a complete solution:
i. Update upper_bound with the cost of this solution.
ii. Continue (or stop if only one solution is needed).
 d. Else (if N is a partial solution):
i. Branch on N to create its children nodes (new subproblems).
ii. For each child node C :
* Calculate its bound.
* If the bound of C is less than upper_bound , add C to the priority queue.
Advantages of Branch-and-Bound:
• More Efficient than Backtracking: The use of bounding functions allows for more
aggressive pruning of the search space, often making it much more efficient than simple
backtracking.
• Finds Optimal Solution: Guarantees finding a globally optimal solution.
• Flexible: Can be adapted to a wide range of optimization problems.
Disadvantages of Branch-and-Bound:
• Worst-Case Complexity: In the worst case, it might still have to explore the entire state
space, leading to exponential time complexity.
• Bound Function Quality: The performance of B&B heavily depends on the quality of
the bounding function. A tight bound (close to the true optimal value) leads to more
effective pruning.
0/1 Knapsack Problem (with Branch-and-Bound)
Problem Statement: Same as before: given items with weights and values, and a knapsack
capacity W , select items to maximize total value without exceeding W .
Branch-and-Bound Approach:
We can solve this maximization problem using B&B. We build a state-space tree where each
level corresponds to an item, and each node has two children: one representing including
the item, and the other representing excluding it.
Bounding Function:
To prune branches, we need an upper bound on the maximum possible value that can be
obtained from a given partial solution. A good upper bound can be calculated by solving the
Fractional Knapsack problem for the remaining items and the remaining capacity. Since
the Fractional Knapsack allows taking fractions of items, its solution will always be greater
than or equal to the optimal solution for the 0/1 Knapsack problem.
Algorithm (using Best-First search):
1. Sort items by value-to-weight ratio in descending order. This helps in getting a better
bound.
2. Initialize a priority queue to store live nodes. A node can be represented as
(upper_bound, current_value, current_weight, level) .
3. Initialize max_profit = 0 .
4. Start with a root node (-1, 0, 0, 0) (initial state) and add it to the priority queue.
5. While the priority queue is not empty:
a. Extract the node N with the highest upper_bound .
b. If N.upper_bound <= max_profit , prune this node and continue.
c. Consider the next item at level = [Link] + 1 .
d. Include Item:
i. Calculate new_weight = N.current_weight + weights[level] and new_value = N.current_value +
values[level] .
ii. If new_weight <= W :
* If new_value > max_profit , update max_profit .
* Calculate the upper bound for this new state (by solving Fractional Knapsack for
remaining items).
* If this upper bound is greater than max_profit , add the new node to the priority
queue.
e. Exclude Item:
i. Calculate the upper bound for the state where the current item is excluded.
ii. If this upper bound is greater than max_profit , add the new node (with same value
and weight as N , but at the next level) to the priority queue.
Time Complexity: The worst-case time complexity is still O(2^n) , but with a good
bounding function and well-ordered items, it performs much better in practice than simple
backtracking.
Traveling Salesperson (with Branch-and-Bound)
Problem Statement: Find the shortest possible route that visits each city exactly once and
returns to the origin.
Branch-and-Bound Approach:
We can solve this minimization problem using B&B. The state-space tree represents partial
tours.
Bounding Function:
We need a lower bound on the cost of any complete tour that can be formed from a partial
tour. A simple and effective lower bound can be calculated as follows:
For a partial tour represented by a node N , the lower bound is the sum of:
1. The cost of the edges already in the partial tour.
2. For each city not yet in the tour, the sum of the costs of its two cheapest edges
connecting to other unvisited cities or the endpoints of the partial tour.
A more common approach uses the cost matrix reduction method:
1. Start with the cost matrix dist[i][j] .
2. Reduce the matrix: For each row, subtract the minimum value in that row from all
elements in the row. Then, for each column, subtract the minimum value in that column
from all elements in that column. The sum of all subtracted values is a lower bound on
the total tour cost.
3. When branching (e.g., deciding to include edge (i, j) ), the cost of the partial tour is the
lower bound of the parent plus the cost of edge (i, j) in the reduced matrix. Then, a
new reduced matrix is created for the subproblem (by setting row i and column j to
 infinity, and also edge (j, i) to infinity to prevent sub-tours), and a new lower bound is
calculated.
Algorithm (using Least-Cost search):
1. Initialize a priority queue to store live nodes. A node can be represented as
(lower_bound, partial_tour, reduced_matrix) .
2. Initialize upper_bound = infinity (or the cost of a known tour, e.g., from a greedy heuristic
like Nearest Neighbor).
3. Calculate the initial lower bound for the root node by reducing the original cost matrix.
Add the root node to the priority queue.
4. While the priority queue is not empty:
a. Extract the node N with the lowest lower_bound .
b. If N.lower_bound >= upper_bound , prune this node.
c. If N represents a complete tour, update upper_bound and continue.
d. Else, branch on N by choosing an unvisited city to visit next. For each choice:
i. Create a new partial tour.
ii. Create a new reduced cost matrix.
iii. Calculate the new lower bound.
iv. If the new lower bound is less than upper_bound , add the new node to the priority
queue.
Time Complexity: The worst-case time complexity is still factorial, O(n!) , but it is
significantly more efficient in practice than brute-force enumeration, especially for
moderately sized problems (e.g., up to 20-30 cities).
Efficiency Considerations
The efficiency of Branch-and-Bound algorithms depends on several factors:
• Quality of the Bounding Function: A tighter bound (closer to the true optimal value)
leads to more effective pruning and faster convergence.
• Search Strategy: The choice of search strategy (FIFO, LIFO, Least-Cost) can affect which
parts of the search space are explored first. Least-Cost is often the most efficient in
 finding the optimal solution quickly.
• Branching Strategy: The way a problem is divided into subproblems can influence the
size and structure of the search tree.
• Initial Upper/Lower Bound: Starting with a good initial bound (e.g., from a greedy
heuristic) can help prune many branches early on.
NP-Hard and NP-Complete Problems: Basic Concepts
In computational complexity theory, problems are classified into different complexity
classes based on the resources (time, space) required to solve them. The classes P, NP, NP-
hard, and NP-complete are fundamental to understanding the limits of computation.
Class P (Polynomial Time):
• Definition: The class of decision problems that can be solved by a deterministic
algorithm in polynomial time. This means the running time is O(n^k) for some constant
k , where n is the input size.
• Meaning: These problems are considered
efficiently solvable. Examples include sorting, searching, finding shortest paths in graphs
(Dijkstra, Bellman-Ford), and matrix multiplication (standard).
Class NP (Nondeterministic Polynomial Time):
• Definition: The class of decision problems for which a given solution can be verified in
polynomial time by a deterministic algorithm. It does not mean the problem can be
solved in polynomial time.
• Meaning: If someone gives you a potential answer to an NP problem, you can quickly
check if it's correct. Many important problems fall into this class, including the Traveling
Salesperson Problem, Satisfiability Problem, and Knapsack Problem.
• P vs. NP: One of the most famous unsolved problems in computer science is whether P
= NP. Most computer scientists believe P ≠ NP, meaning there are problems whose
solutions can be quickly verified but not quickly found.
NP-Hard Problems:
• Definition: A problem H is NP-hard if every problem in NP can be reduced to H in
polynomial time. This means that if you had a polynomial-time algorithm for H , you
could use it to solve any problem in NP in polynomial time.
• Meaning: NP-hard problems are at least as hard as the hardest problems in NP. They
don't necessarily have to be in NP themselves (i.e., their solutions might not be
verifiable in polynomial time, or they might not be decision problems at all, e.g.,
optimization problems).
• Examples: The Traveling Salesperson Problem (optimization version), Halting Problem
(undecidable, thus NP-hard).
NP-Complete Problems:
• Definition: A problem C is NP-complete if it is both:
1. In NP (its solutions can be verified in polynomial time).
2. NP-hard (every problem in NP can be reduced to it in polynomial time).
• Meaning: NP-complete problems are the
hardest problems in NP. If you find a polynomial-time algorithm for any NP-complete
problem, then P = NP, and all problems in NP can be solved in polynomial time.
• Examples: Satisfiability Problem (SAT), 3-SAT, Clique Problem, Vertex Cover,
Hamiltonian Cycle, Subset Sum (decision version), 0/1 Knapsack (decision version).
Cook's Theorem
Cook's Theorem (also known as the Cook-Levin Theorem) is a foundational result in
computational complexity theory. It was proven by Stephen Cook in 1971 and
independently by Leonid Levin in 1973.
Statement of the Theorem: The Boolean Satisfiability Problem (SAT) is NP-complete.
Significance:
 • First NP-Complete Problem: Cook's Theorem was the first problem proven to be NP-
complete. This was a monumental achievement because it provided a concrete
example of a problem that was
both in NP and NP-hard. Before this, the concept of NP-completeness was theoretical.
• Foundation for Proving Other NP-Complete Problems: Once SAT was proven NP-
complete, it became a powerful tool. To prove that another problem X is NP-complete,
one only needs to show two things:
1. X is in NP (i.e., a given solution to X can be verified in polynomial time).
2. SAT can be reduced to X in polynomial time. (Or, more generally, any known NP-
complete problem can be reduced to X in polynomial time).
This reduction process is crucial. If SAT can be transformed into X in polynomial time, it
means X is at least as hard as SAT. Since SAT is the
hardest problem in NP (by definition of NP-completeness), then X must also be NP-hard.
Since X is also in NP, it becomes NP-complete.
Cook's Theorem essentially provided the first
link in a long chain of reductions, allowing thousands of other problems to be classified as
NP-complete.
NP-Hard Graph Problems
Many problems in graph theory are NP-hard or NP-complete. These problems are
computationally challenging, meaning no known polynomial-time algorithm exists to solve
them exactly. Here are a few prominent examples:
1. Traveling Salesperson Problem (TSP):
• Problem: Given a list of cities and the distances between each pair of cities, find the
shortest possible route that visits each city exactly once and returns to the origin city.
• Why NP-Hard: As discussed, the decision version (Is there a tour with total cost at
most K?) is NP-complete. The optimization version (find the minimum cost tour) is
 NP-hard. It is one of the most well-known NP-hard problems and has applications in
logistics, manufacturing, and microchip design.
2. Hamiltonian Cycle Problem:
• Problem: Given a graph, determine if it contains a Hamiltonian cycle (a cycle that
visits each vertex exactly once).
• Why NP-Complete: It is in NP (a given cycle can be verified in polynomial time) and
NP-hard (can be reduced from other NP-complete problems like 3-SAT).
3. Clique Problem:
• Problem: Given a graph G and an integer k , determine if G contains a clique of
size at least k . A clique is a subset of vertices where every pair of vertices is
connected by an edge.
• Why NP-Complete: It is in NP (a given subset of vertices can be checked for clique
property in polynomial time) and NP-hard (can be reduced from 3-SAT).
4. Vertex Cover Problem:
• Problem: Given a graph G and an integer k , determine if G has a vertex cover of
size at most k . A vertex cover is a subset of vertices such that every edge in the
graph is incident to at least one vertex in the subset.
• Why NP-Complete: It is in NP (a given subset can be checked for vertex cover
property in polynomial time) and NP-hard (can be reduced from 3-SAT).
5. Graph Coloring Problem:
• Problem: Given a graph G and an integer k , determine if G can be colored with
k colors such that no two adjacent vertices have the same color.
• Why NP-Complete: It is in NP (a given coloring can be verified in polynomial time)
and NP-hard (can be reduced from 3-SAT).
These problems are often tackled using approximation algorithms (which find near-optimal
solutions in polynomial time) or heuristic algorithms (which find good solutions but offer no
guarantees on optimality or running time) for large instances, or exact algorithms like
Branch-and-Bound for smaller instances.
NP-Hard Scheduling Problems
Scheduling problems involve allocating resources over time to perform a set of tasks or
jobs, with the goal of optimizing some objective (e.g., minimizing completion time,
maximizing throughput). Many realistic scheduling problems are NP-hard due to the
combinatorial explosion of possible schedules.
1. Job Shop Scheduling:
• Problem: You have n jobs, and each job consists of a sequence of operations. Each
operation must be performed on a specific machine, and machines can only process
one operation at a time. The goal is to find a schedule that minimizes the makespan
(total time to complete all jobs).
• Why NP-Hard: This is one of the most complex scheduling problems. Even for a small
number of jobs and machines, the number of possible schedules is enormous. It is
NP-hard for m ≥ 3 machines.
2. Flow Shop Scheduling:
• Problem: You have n jobs, and each job must be processed on m machines in the
same fixed order. Each job j has a processing time P_ij on machine i . The goal is
to find a schedule (the order of jobs) that minimizes the makespan.
• Why NP-Hard: As mentioned earlier, this problem is NP-hard for m ≥ 3 machines.
For m=2 , Johnson's Rule provides a polynomial-time optimal solution.
3. Resource-Constrained Project Scheduling Problem (RCPSP):
• Problem: Given a set of activities with precedence constraints, processing times, and
resource requirements, and a set of available resources, schedule the activities to
minimize the project duration (makespan) or maximize resource utilization.
• Why NP-Hard: The combination of precedence constraints and limited resources
makes this problem highly complex and NP-hard.
 4. Bin Packing Problem:
• Problem: Given a set of items of different sizes and a set of bins of a fixed capacity,
pack all items into the minimum number of bins.
• Why NP-Hard: The decision version (Can all items be packed into k bins?) is NP-
complete. This problem has applications in logistics, memory allocation, and
container loading.
These NP-hard scheduling problems are typically addressed using heuristics, metaheuristics
(like genetic algorithms, simulated annealing), or approximation algorithms, as finding
exact optimal solutions is computationally intractable for practical problem sizes.
PRAM Algorithms: Introduction, Computational Model, Fundamental
Techniques and Algorithms, Selection
Introduction to PRAM Algorithms:
PRAM stands for Parallel Random Access Machine. It is a theoretical model of parallel
computation that is used to design and analyze parallel algorithms. Unlike the sequential
RAM (Random Access Machine) model, which assumes a single processor, the PRAM model
assumes multiple processors that can access a shared memory simultaneously. PRAM
algorithms are designed to exploit parallelism to solve problems faster than sequential
algorithms.
Why PRAM?
• Theoretical Foundation: Provides a simplified model for studying the fundamental
limits and capabilities of parallel computation, abstracting away complex issues like
communication overhead and memory contention that exist in real parallel machines.
• Algorithm Design: Helps in designing algorithms that can effectively utilize multiple
processors.
• Performance Analysis: Allows for the analysis of parallel algorithms in terms of parallel
time complexity (how many steps it takes with multiple processors) and work
complexity (total operations performed by all processors).
Computational Model (PRAM):
The PRAM model consists of:
1. Multiple Processors: A set of P identical processors, P1, P2, ..., Pp . Each processor
has its own local memory and can perform standard RAM operations (arithmetic, logic,
memory access).
2. Shared Memory: A single, global shared memory that all processors can access. This is
the key feature that distinguishes PRAM from distributed memory models.
3. Synchronous Operations: All processors operate synchronously, meaning they execute
their instructions in lock-step. In each time step, every active processor can perform one
operation (read from shared memory, perform a computation, or write to shared
memory).
Memory Access Conflict Resolution:
The most critical aspect of the PRAM model is how it handles concurrent access to the same
memory location. There are different PRAM variants based on how read/write conflicts are
resolved:
• EREW (Exclusive Read, Exclusive Write): The most restrictive model. No two
processors can read from the same memory location, and no two processors can write
to the same memory location simultaneously.
• CREW (Concurrent Read, Exclusive Write): Allows multiple processors to read from
the same memory location simultaneously, but only one processor can write to a given
location at any time.
• ERCW (Exclusive Read, Concurrent Write): Allows multiple processors to write to the
same memory location simultaneously, but only one processor can read from a given
location at any time. (Less common).
• CRCW (Concurrent Read, Concurrent Write): The most powerful model. Allows
multiple processors to read from and write to the same memory location
simultaneously. CRCW models further differ in how concurrent writes are resolved:
• Common CRCW: All processors attempting to write to the same location must write
the same value.
 • Arbitrary CRCW: An arbitrary processor among those attempting to write succeeds.
• Priority CRCW: The processor with the highest priority among those attempting to
write succeeds.
• Sum CRCW: The sum of all values written is stored.
CREW and CRCW are the most commonly studied variants, with CRCW being more powerful
but also more complex to implement in real hardware.
Fundamental Techniques and Algorithms in PRAM:
PRAM algorithms often employ specific techniques to leverage parallelism:
1. Prefix Sum (Scan):
• Problem: Given an array A = [a1, a2, ..., an] , compute an array B = [b1, b2, ..., bn] where
bi = a1 + a2 + ... + ai .
• PRAM Algorithm (Example for EREW): Can be done in O(log n) time using O(n)
processors. The idea is to sum elements at increasing distances. For example, in the
first step, a_i adds a_{i-1} . In the second step, a_i adds a_{i-2} , and so on. This
involves log n steps, where in each step, n processors perform additions.
2. Parallel Sorting:
• Problem: Sort an array of n elements.
• PRAM Algorithms: Many parallel sorting algorithms exist. For example, Odd-Even
Merge Sort can be implemented on a PRAM in O(log^2 n) time using O(n)
processors. Bitonic Sort is another example.
3. Parallel Search:
• Problem: Search for an element in an array.
• PRAM Algorithm: For an unsorted array, O(1) time using O(n) processors (each
processor checks one element). For a sorted array, parallel binary search can be done
in O(log n) time using O(1) processors (similar to sequential binary search, but the
comparisons can be done in parallel if multiple targets are searched).
 4. Parallel Graph Algorithms:
• Connected Components: Can be found in O(log n) time on a CRCW PRAM.
• Minimum Spanning Tree: Parallel versions of Prim's or Kruskal's algorithms exist,
often achieving O(log n) or O(log^2 n) time.
Selection in PRAM:
Problem: Given an unsorted array A of n elements, find the k -th smallest element.
PRAM Algorithm for Selection (using CRCW PRAM):
This is a classic example where the power of CRCW PRAM can be demonstrated to achieve
very fast results.
1. Choose a Pivot: Select a pivot element p from the array. This can be done randomly
or deterministically.
2. Parallel Comparison: For each element a_i in the array, in parallel, compare a_i
with p .
• If a_i < p , mark it as
smaller.
* If a_i > p , mark it as larger.
* If a_i = p , mark it as equal.
This step takes O(1) time using O(n) processors.
1. Count Elements: Count the number of elements smaller than p ( count_smaller ) and
the number of elements equal to p ( count_equal ). This can be done using parallel
prefix sums or by writing 1s to specific memory locations and summing them up
(possible on CRCW PRAM).
This step takes O(log n) time using O(n) processors.
2. Recurse:
• If k <= count_smaller , the k -th smallest element is in the set of elements smaller
than p . Recursively solve the problem on this subset.
 • If count_smaller < k <= count_smaller + count_equal , then the k -th smallest element is
p itself. Return p .
• If k > count_smaller + count_equal , the k -th smallest element is in the set of elements
larger than p . Recursively solve the problem on this subset, searching for the (k -
count_smaller - count_equal) -th smallest element.
Time Complexity: With a good pivot selection strategy (e.g., using a parallel median-of-
medians approach), the selection problem can be solved in O(log n) time on a CRCW PRAM
using O(n) processors. This is a significant speedup compared to the O(n) sequential
time.
Challenges with PRAM:
Despite its theoretical elegance and power, the PRAM model is difficult to implement
directly in real hardware due to:
• Shared Memory Bottleneck: Real shared memory systems suffer from contention and
cache coherence issues.
• Synchronization Overhead: Maintaining perfect synchronization among a large
number of processors is challenging.
• Scalability: Building a machine with truly uniform memory access times for a very large
number of processors is difficult.
However, PRAM algorithms serve as a valuable theoretical benchmark and provide insights
into the fundamental parallelism inherent in problems, guiding the design of algorithms for
more realistic parallel architectures.

Conclusion
This comprehensive study guide has covered the fundamental concepts and advanced
topics in algorithms, as outlined in your syllabus. We began with the basics of what an
algorithm is, how to specify it, and how to analyze its performance in terms of time, space,
and amortized complexity, along with the crucial role of asymptotic notation. We then
delved into various algorithmic paradigms, including Divide-and-Conquer, Greedy Methods,
Dynamic Programming, and Backtracking, illustrating each with classic problems and their
solutions.
Key takeaways from this guide include:
• Understanding Efficiency: The ability to analyze and compare algorithms based on
their time and space complexity is paramount for designing scalable and performant
solutions.
• Algorithmic Paradigms: Each paradigm offers a unique approach to problem-solving,
and knowing when and how to apply them is crucial. Divide-and-Conquer excels at
breaking down problems, Greedy methods make locally optimal choices, Dynamic
Programming optimizes problems with overlapping subproblems, and Backtracking
systematically explores solution spaces.
• Problem Classification: Understanding complexity classes like P, NP, NP-hard, and NP-
complete helps in recognizing the inherent difficulty of problems and choosing
appropriate solution strategies (exact, approximation, or heuristic).
• Parallelism: The introduction to PRAM algorithms highlights the theoretical
foundations of parallel computing, which is increasingly relevant in modern multi-core
and distributed systems.
Remember that while theoretical understanding is vital, practical application often involves
considering real-world constraints, constant factors, and specific input characteristics. This
guide provides a solid foundation for your exam and for your continued journey in the
fascinating world of algorithms. Good luck with your exam!

References
No external references were used in the creation of this document. All content is generated
based on the provided syllabus and general knowledge of algorithms and data structures.