ADA Merged

CHAPTER 1: PRINCIPLES OF ANALYZING
ALGORITHMS AND PROBLEMS

By: Ashok Basnet
Course Outline
1. Principles of Analyzing Algorithm and Problems: Space and Time Complexity
2. Review of Abstract Data Types: Stack and Queue
3. Sorting, Selection and Sequencing: Merge sort, Binary search, Job

sequencing with deadlines.
4. Dynamic Programming: Knapsack Problem
5. Graph Traversal and search techniques: Breadth first search, Depth first
search.
6. Backtracking: The 8-queens problem

Chapter 1: Principles of Analyzing
Algorithms and Problems
1. Introduction to 2. Algorithm
Algorithms Specification
3. Performance
4. Randomized
Analysis (Space and
Algorithms
Time Complexity)
What is Algorithm?
Understanding Algorithms
▪ In mathematics and computer science, algorithms are powerful tools for solving
specific problems and automating tasks.
▪ Definition: An algorithm is a precise sequence of instructions designed to tackle

a particular problem or carry out a computation.
▪ Problem Solving: Algorithms serve as blueprints for performing calculations and
processing data efficiently.
▪ Advanced Capabilities: Sophisticated algorithms can automate deductions
(automated reasoning) and guide code execution using mathematical and logical
tests (automated decision-making)
Key Characteristics:
▪ Algorithms consist of finite, well-defined instructions.

▪ Each instruction is understandable and achievable in a finite amount of time.
▪ Regardless of input values, an algorithm always terminates after a finite number
of instructions.
▪ Algorithms are the foundation of computer science and are essential for solving
complex real-world challenges.
Algorithm Criteria:
▪ Input:
- An algorithm may accept zero or more externally provided quantities or data.
- Input should be well-defined and clearly specified for accurate processing.
▪ Output:
- Every algorithm must produce at least one meaningful output or result.
- The output should convey relevant information or serve a purpose.
▪ Definiteness:
- Each instruction within an algorithm must be precise, clear, and free from ambiguity.
- Clarity ensures that the algorithm's actions are well-understood and correctly executed.
Algorithm Criteria:
▪ Finiteness:
- An algorithm must exhibit the property of finiteness, meaning it will complete its execution
within a finite number of well-defined steps.
- It should avoid infinite loops or indeterminate behavior.
▪ Effectiveness:
- Every instruction in the algorithm must be fundamental and executable.
- The instructions should be practical and achievable with available resources.
Example: Multiply two numbers
Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7

Start Get the Declare a, b, c Take input for a Know the Check how to End
knowledge of variables. and b variable problem and find give output,
input. Here we from the user. the solution Here we need to
need 3 variables; using operators, print the output.
a and b will be data structures So write print c
the user input and logic
and c will hold • We need to multiply
the result. a and b variables so
we use * operator
and assign the result
to c.
• That is c <- a * b
Reason for Analysis
Need to recognize limitations of various algorithms for solving a problem.
Need to understand relationship between problem size and running time when is a running
program not good enough?
Need to learn how to analyze an algorithm's running time without coding it.
Need to learn techniques for writing more efficient code.
Need to recognize bottlenecks in code as well as which parts of code are easiest to optimize.
Why do we Analyze Algorithms
Correctness and Efficiency
Decide whether some problems have no solution in

reasonable time
Investigate memory usage as different measure of

efficiency.
Performance of a program
The performance of a program is the amount of computer memory and

time needed to run a program.
We use two approaches to determine the performance of a program.
One is analytical, and the other experimental.
In performance analysis we use analytical methods, while in performance

measurement we conduct experiments.
Time Complexity
▪ The time needed by an algorithm expressed as a function of the size of a problem is

called the time complexity of the algorithm.
▪ The time complexity of a program is the amount of computer time it needs to run to
completion.
▪ The limiting behavior of the complexity as size increases is called the asymptotic time
complexity.
▪ It is the asymptotic complexity of an algorithm, which ultimately determines the size of

problems that can be solved by the algorithm.
Space Complexity
▪ The space complexity of a program is the amount of memory it needs to run to

completion.
▪ The space need by a program has the following components:
▪ Instruction space: Instruction space is the space needed to store the compiled version
of the program instructions. The amount of instructions space that is needed depends
on factors such as:
✓ The compiler used to complete the program into machine code.
✓ The compiler options in effect at the time of compilation
✓ The target computer.
Space Complexity
▪ Data space: Data space is the space needed to store all constant and variable values.
Data space has two components:
✓ Space needed by constants and simple variables in program.
✓ Space needed by dynamically allocated objects such as arrays and class instances.
▪ Environment stack space: The environment stack is used to save information needed
to resume execution of partially completed functions.
Algorithm Design Goals
- The three basic design goals that one should strive for in a program are:
1. Try to save Time
2. Try to save Space
3. Try to save Face
- A program that runs faster is a better program, so saving time is an obvious goal.
- Likewise, a program that saves space over a competing program is

considered desirable.
- We want to “save face” by preventing the program from locking up or generating

reams of garbled data.
Classification of
Algorithms
▪ If ‘n’ is the number of data items to be processed

or degree of polynomial or the size of the file to
be sorted or searched or the number of nodes in
a graph etc.
▪ 1 : If all the instructions of a program have this
property, we say that its running time is a
constant.
O(n)
▪ When the running time of a program is linear, it is

generally the case that a small amount of processing
is done on each input element.
▪ This is the optimal situation for an algorithm that
must process n inputs.
Log n
▪ When the running time of a program is logarithmic,
the program gets slightly slower as n grows.
▪ This running time commonly occurs in programs that
solve a big problem by transforming it into a smaller
problem, cutting the size by some constant fraction.
▪ When n is a million, log n is a doubled. Whenever n
doubles, log n increases by a constant, but log n does
not double until n increases to npow(2).
nlog(n)
▪ This running time arises for algorithms that

solve a problem by breaking it up into smaller
sub-problems, solving then independently,
and then combining the solutions.
▪ When n doubles, the running time more than
doubles.
n^2
▪ When the running time of an algorithm is

quadratic, it is practical for use only on
relatively small problems.
▪ Quadratic running times typically arise in
algorithms that process all pairs of data items
(perhaps in a double nested loop) whenever n
doubles, the running time increases four fold.
2^n
- Few algorithms with exponential running time are likely to be appropriate for
practical use, such algorithms arise naturally as “brute–force” solutions to
problems.
- Whenever n doubles, the running time squares.

Complexity of Algorithms
- The complexity of algorithm M is defined by the function f(n), which
characterizes the algorithm's performance in terms of its execution time and
storage space needs relative to the input data size 'n.'
- Typically, the storage space required by an algorithm is directly proportional to

the size 'n' of the input data.
- It's important to note that the function f(n), which quantifies the algorithm's
running time, relies not only on the input data size 'n' but also on the specific
characteristics of the data being processed.
The complexity function f(n) for certain cases
are:
▪ Best Case (Infrequently Utilized): This refers to the minimal conceivable value of
f(n) and is referred to as the "best case."
▪ Average Case (Seldom Employed): This pertains to the anticipated value of f(n) and
is known as the "average case."
▪ Worst Case (Most Commonly Employed): This signifies the maximum value of f(n)
achievable for any conceivable input and is commonly referred to as the "worst case."
▪ The domain within computer science that delves into the efficiency of algorithms is
formally recognized as the "analysis of algorithms."
Best Case:
▪ This denotes the specific input conditions under which an algorithm exhibits its
most efficient performance, resulting in the shortest possible execution time.
▪ The best case provides a lower bound for the algorithm's time complexity.
▪ For instance, in the case of a linear search, the best case occurs when the
sought-after data is found at the very beginning of a large dataset.
Worst Case
▪ This characterizes the input scenarios in which an algorithm experiences its
most time-consuming execution, resulting in the longest possible time.
▪ The worst case offers an upper bound for the algorithm's time complexity.
▪ As an illustration, in linear search, the worst case transpires when the desired
data is entirely absent from the dataset.
Average Case
▪ In the average case, we consider a spectrum of random input conditions and
calculate the algorithm's execution time for each of these conditions.
▪ Subsequently, we determine the average by summing up the execution times for
all random inputs and dividing it by the total number of inputs.
▪ This provides us with a realistic estimate of the algorithm's expected
performance under typical, random scenarios.
▪ The formula for average case computation is as follows:
▪ Average Case = (Sum of execution times for all random cases) / (Total number of
cases)
Asymptotic Analysis
▪ In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input
size.
▪ We don’t measure the actual running time. We calculate, how the time (or space)
taken by an algorithm increases with the input size.
▪ For example, let us consider the search problem (searching a given item) in a sorted
array.
▪ The solution to above search problem includes:

▪ Linear Search (order of growth is linear)
▪ Binary Search (order of growth is logarithmic).
▪ To understand how Asymptotic Analysis solves the problems mentioned above in analyzing
algorithms,
▪ let us say:
▪ We run the Linear Search on a fast computer A and
▪ Binary Search on a slow computer B and
▪ pick the constant values for the two computers so that it tells us exactly how long it takes
for the given machine to perform the search in seconds.
▪ Let’s say the constant for A is 0.2 and the constant for B is 1000 which means that A is
5000 times more powerful than B.
▪ For small values of input array size n, the fast computer may take less time.
▪ But, after a certain value of input array size, the Binary Search will definitely start taking less
time compared to the Linear Search even though the Binary Search is being run on a slow
machine.
▪ The reason is the order of growth of Binary Search with respect to input size is
logarithmic while the order of growth of Linear Search is linear.
▪ So the machine-dependent constants can always be ignored after a certain

value of input size.
▪ Running times for this example:
▪ Linear Search running time in seconds on A: 0.2 * n
▪ Binary Search running time in seconds on B: 1000*log(n)
Does Asymptotic Analysis always work?
▪ Asymptotic Analysis: A Valuable, Though Simplified, Tool: While not perfect, asymptotic
analysis is the most effective method available for analyzing algorithms.
▪ It provides valuable insights into how algorithms perform as input sizes increase, simplifying
complex performance comparisons.
▪ An Example: Comparing Sorting Algorithms: Consider two sorting algorithms: one with a time
complexity of 1000nlog(n) and another with 2nlog(n). Both share the same asymptotic
complexity (n*log(n)). However, in asymptotic analysis, we disregard constant factors.
▪ Constant Factors Disregarded: Asymptotic analysis doesn't consider constant factors. Thus,
it doesn't allow us to determine which of the two sorting algorithms is better in practice, as
their real-world performance could differ due to these constants.
Big-O Notation
▪ We define an algorithm’s worst-case time complexity by using the Big-O notation.

▪ It explains the maximum amount of time an algorithm requires to consider all input
values.
▪ Scalability: Estimates how an algorithm's performance scales with input size.

▪ Comparisons: Helps in contrasting different algorithms based on their scalability.
▪ Constants Ignored: Simplifies analysis by disregarding constant factors.

▪ Practical Considerations: Real-world performance may vary due to hardware and
implementation details.
Omega Notation
▪ It defines the best case of an algorithm’s time complexity.
▪ It explains the minimum amount of time an algorithm requires to consider all input
values.
▪ Omega notation helps us understand how efficiently an algorithm performs under

favorable conditions.
▪ Unlike Big-O notation, Omega notation acknowledges constant factors and focuses
on the lower bounds of an algorithm's performance.
Theta Notation
▪ It defines the average case of an algorithm’s time complexity, the Theta notation
defines when the set of functions lies in both O(expression) and Omega(expression),
then Theta notation is used.
▪ Theta notation (Θ) is a mathematical notation used to describe the exact and balanced
behavior of an algorithm's time complexity.
▪ It represents both the upper and lower bounds of an algorithm's performance,

providing a tight range within which the algorithm operates.
▪ Theta notation is an essential tool in algorithm analysis and is particularly valuable
when the upper and lower bounds of an algorithm's time complexity are the same or
very close.
Rate of Growth
The following notations are commonly use notations in performance analysis and used
to characterize the complexity of an algorithm:
▪ Big–OH (O)
▪ Big–OMEGA (Ω)
▪ Big–THETA (Θ)
▪ Little–OH (o)
▪ Little Omega (ω)

The order of complexity
▪ Linear search is O (n)

▪ Binary search is O (log n)
▪ Bubble sort is O (n2)

▪ Merge sort is O (n log n)
Theta (Θ) Notation
- Theta notation encloses the function from above and below. Since it represents the upper
and the lower bound of the running time of an algorithm, it is used for analyzing the average-
case complexity of an algorithm.
- Let g and f be the function from the set of natural numbers to itself.
- The function f is said to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0
such that c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0.
Theta (Θ) Notation
- Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤
f(n) ≤ c2 * g(n) for all n ≥ n0}
- The above expression can be described as if f(n) is theta of g(n), then the value f(n) is
always between c1 * g(n) and c2 * g(n) for large values of n (n ≥ n0).
- The definition of theta also requires that f(n) must be non-negative for values of n
greater than n0.
- A simple way to get the Theta notation of an expression is to drop low-order terms
and ignore leading constants.
- For example, Consider the expression 3n3 + 6n2 + 6000 = Θ(n3)

Big-O Notation
- Big-O notation represents the upper bound of the running time of an algorithm.
Therefore, it gives the worst-case complexity of an algorithm.
- If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0.
Big-O Notation
- O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all
n ≥ n0 }.
- The Big-O notation is useful when we only have an upper bound on the time complexity
of an algorithm.
- Many times we easily find an upper bound by simply looking at the algorithm.
Omega Notation (Ω-Notation)
- Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.
- Let g and f be the function from the set of natural numbers to itself. The function f is said to be
Ω(g), if there is a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for all n ≥ n 0
- Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
Randomized Algorithms
▪ An algorithm that uses random numbers to decide what to do next anywhere in its
logic is called Randomized Algorithm.
▪ A randomized algorithm is an algorithm that employs a degree of randomness as

part of its logic or procedure.
▪ Makes use of Randomizer (Random number generator).
▪ Decisions made in the algorithm depends on the output of the randomizer.
▪ Output and Execution time may vary from run to run for the same input.
- A randomized algorithm is an algorithm that incorporates randomness or randomization as a
fundamental part of its design and operation.
- Unlike traditional algorithms, which produce the same output for a given input every time,
randomized algorithms introduce an element of chance into their computations.
- These algorithms use random numbers or random processes to make decisions, perform
computations, or achieve specific goals.
Key characteristics
▪ Probabilistic Behavior:
▪ Randomized algorithms produce results that are probabilistic or statistical in nature.
▪ The outcome of the algorithm may vary each time it is run, but it has a well-defined
probability distribution.
▪ Efficiency and Approximation:

▪ Randomized algorithms are often used to solve problems that are computationally
challenging or difficult to solve deterministically.
▪ They may provide approximate solutions or solutions with high confidence.
Key characteristics
▪ Random Choices:
▪ Randomized algorithms make random choices at various stages of their execution.
▪ These choices may include selecting random elements, flipping coins, or using other sources
of randomness.
▪ Expected Behavior:
▪ When analyzing randomized algorithms, the focus is on the expected or average behavior
over multiple runs.
▪ The goal is to achieve desired outcomes with high probability.
▪ Applications:
▪ Randomized algorithms find applications in various fields, including computer science,
cryptography, optimization, machine learning, and probabilistic data structures.
▪ They are particularly useful in situations where deterministic algorithms are too slow or
impractical.
Examples
▪ Monte Carlo Algorithms:
▪ These algorithms use random sampling to approximate solutions to complex problems, such
as estimating the value of mathematical constants or solving optimization problems.
▪ Las Vegas Algorithms:
▪ These algorithms use randomness to improve efficiency.
▪ They may guarantee that the solution is correct but not bound the running time precisely.
▪ Examples include randomized quicksort and some graph algorithms.

- Algorithm: Find Repeated Element (a, n)
- Description: This algorithm aims to identify a repeated element within an array a, which spans
from index 1 to n.
- Procedure:
- Initialize Loop:
- Enter an infinite loop.
- Generate Random Indices:
- Generate two random indices, i and j.
- i := Random() mod n + 1
- j := Random() mod n + 1
- Check for Repeated Element:
- If i is not equal to j and a[i] is equal to a[j], indicating the presence of a repeated element:
- Return Index:
- Return the value of i, indicating the index of the repeated element.
Chapter 2: Review
of Abstract Data
Types
By: Ashok Basnet
1
Course Outline 1. Stacks
2. Queues
3. Priority Queues
4. Binary Trees
5. Dictionaries
6. Sets and Disjoint Set Union
2
Data Types
▪ Two important things about data types:
• Defines a certain domain of values.
• Defines Operations allowed on those values.
▪ Example: int type
• Takes only integer values
• Operations: addition, subtraction, multiplication, bitwise operations etc.
▪ We cannot perform bitwise and % operations in float.
3
User Defined Data Types
▪ In contrast to primitive data types (int, float, char), there is a concept of a user defined data
types.
▪ The operations and values of user defined data types are not specified in the language
itself but is specified by the user.
▪ Example: Structure in C -> By using structures, we are defining our own type by combining
other data types.
▪ struct student {
int id;
char name[50];
}
4
Abstract Data Types (ADT)
▪ ADTs are like user defined data types which defines operations on values
using functions without specifying what is there inside the function and how
the operation are performed.
▪ An ADT specifies what operations can be performed on a particular data
structure, but it does not prescribe how these operations should be
implemented.
▪ Example: Stack ADT
▪ A stack consists of elements of same type arranged in a sequential order.
5
▪ The idea behind ADTs is to separate the logical view of a data structure
from its implementation details.
▪ This separation allows programmers to focus on the functionality and
behavior of the data structure without worrying about the specific
implementation.
▪ As a result, ADTs provide a way to abstract away the underlying
complexities of data structures and promote modularity and code
reusability.
6
Examples of ADT
▪ Stack: A data structure that follows the Last In, First Out (LIFO) principle,
where elements are added and removed from the same end (top).
▪ Queue: A data structure that follows the First In, First Out (FIFO) principle,
where elements are added at the rear and removed from the front.
▪ List: A collection of elements where each element has a position or index,
and operations can include adding, removing, or accessing elements at a
specific position.
7
Examples of ADT
▪ Set: A collection of unique elements with operations like adding,
removing, and checking for the presence of an element.
▪ Map (or Dictionary): A collection of key-value pairs, where each key is
associated with a value. Operations include inserting, deleting, and
looking up values based on their keys.
▪ Graph: A collection of nodes and edges, where nodes represent entities,
and edges represent relationships between entities.
8
▪ Initialization/Creation:
o Description: Initializes a new instance of the ADT.
o Purpose: Creates a new instance of the data structure.
▪ Insertion/Adding:
o Description: Adds a new element to the data structure.
o Purpose: Increases the size of the data structure by including a new element.
▪ Deletion/Removing:
o Description: Removes an element from the data structure.
o Purpose: Decreases the size of the data structure by eliminating an element.
9
▪ Access/Retrieval:
o Description: Retrieves the value of a specific element in the data structure.
o Purpose: Obtains the value of an element without modifying the data structure.
▪ Search:
o Description: Determines whether a particular element is present in the data
structure.
o Purpose: Checks for the existence of a specific element.
▪ Traversal:
o Description: Visits and processes each element in the data structure.
o Purpose: Iterates through all elements in the data structure. 10
▪ Update/Modification:
o Description: Modifies the value of an existing element in the data structure.
o Purpose: Changes the content of an element without adding or removing it.
▪ Size/Length:
o Description: Returns the number of elements in the data structure.
o Purpose: Provides information about the size or length of the data structure.
11
▪ Emptiness Check:
o Description: Determines whether the data structure is empty.
o Purpose: Indicates whether the data structure contains any elements.
▪ Clear:
o Description: Removes all elements from the data structure.
o Purpose: Resets the data structure to an empty state.
▪ The class provides the implementation details, while the interface defines
the set of operations that can be performed on the ADT.
12
▪ Think of ADT as a black box which hides the inner structure and design of the data
type from the user.
▪ There are multiple ways to implement an ADT.
▪ Example: A stack ADT can be implemented using arrays or linked lists.
▪ The program which uses data structure is called a client program. Client program
has access to the ADT i.e. interface.
▪ The program which implements the data structure is known as the implementation.
13
Stacks
▪ A stack is a linear data structure in which insertions and deletions are allowed
only at the end, called the top of the stack.
▪ When we define a stack as an ADT (or Abstract Data Type), then we are only
interested in knowing the stack operations from the user point of view.
▪ Means we are not interested in knowing the implementation details at this moment.
▪ We are only interested in knowing what types of operations we can perform on
stack.
14
Why Abstract Data Types?
▪ Let say, if someone wants to use the stack in the program, then he can simply use
push and pop operations without knowing its implementation.
▪ Also, if in future, the implementation of stack is changed from array to linked list,
then the client program will work in the same way without being affected.
▪ Hence, ADT provides Abstraction.
15
Primary Stack Operations
▪ push (data) : Inserts data onto stack.
▪ pop ( ) : Deletes the last inserted element from the stack
▪ top ( ) : returns the last inserted element without removing it.
▪ size ( ) : returns the size or the number of elements in the stack.
▪ isEmpty ( ) : returns True if the stack is empty, else returns False.
▪ isFull ( ) : returns True if the stack is full, else returns False.
16
Push and Pop Operation
▪ For the push operation:
• Top is incremented by 1.
• New element is pushed at the position top
▪ For the pop operation:

• The element at the position of top is deleted.
• Top is decremented by 1
17
Pop an element
▪ How to delete the element at index 3?
▪ We cannot simply remove the array element.
▪ Still, we can give the user an illusion that the array element is deleted
by decrementing the top variable.
▪ Top variable always keeps track of the topmost element of the stack.
▪ If the top is decremented by 1 then the user will perceive that the topmost
element is deleted.
18
Queues
▪ A queue is defined as a linear data structure that is open at both ends and
the operations are performed in First In First Out (FIFO) order.
▪ We define a queue to be a list in which all additions to the list are made at
one end, and all deletions from the list are made at the other end.
▪ The element which is first pushed into the order, the operation is first
performed on that.
19
FIFO Principle of ▪ A Queue is like a line waiting to
Queue: purchase tickets, where the first
person in line is the first person
served. (i.e. First come first serve).
20
Queue Representation
Like stacks, Queues can also be represented in an array:
In this representation, the Queue is implemented using the array. Variables used in
this case are
▪ Queue: the name of the array storing queue elements.
▪ Front: the index where the first element is stored in the array representing the
queue.
▪ Rear: the index where the last element is stored in an array representing the
queue.
21
Array implementation of queue
To implement a queue using an array,
▪ create an array: array of size n and
▪ take two variables front and rear both of which will be initialized to 0 which
means the queue is currently empty.
▪ Element
• rear is the index up to which the elements are stored in the array and
• front is the index of the first element of the array.
22
Enqueue
Addition of an element to the queue.
Adding an element will be performed after checking

whether the queue is full or not.
If rear < n which indicates that the array is not full then
store the element at arr[rear] and increment rear by 1
But if rear == n then it is said to be an Overflow

condition as the array is full.
23
Dequeue
▪ Removal of an element from the queue.
▪ An element can only be deleted when there is at least an element to
delete i.e. rear > 0.
▪ Now, the element at array[front] can be deleted but all the remaining
elements have to shift to the left by one position in order for the dequeue
operation to delete the second element from the left on another dequeue
operation.
24
Front and Display
▪ Get the front element from the

queue i.e. arr[front] if the queue
is not empty.
▪ Print all elements of the queue. If
the queue is non-empty, traverse
and print all the elements from
the index front to rear.
25
Priority Queues
26
Priority Queue
▪ Priority Queues are abstract data structures where each data/value in the queue
has a certain priority.
▪ For example, In airlines, baggage with the title “Business” or “First-class” arrives
earlier than the rest.
▪ Various applications of the Priority queue in Computer Science are:
➢ Job Scheduling algorithms, CPU and Disk Scheduling, managing resources that are
shared among different processes, etc.
27
Priority Queue
▪ A priority Queue is an extension of the queue with the following properties:
o Every item has a priority associated with it.
o An element with high priority is dequeued before an element with low
priority.
o If two elements have the same priority, they are served according to their
order in the queue.
28
Priority Queue
In the priority queue, an

element with a maximum
ASCII value will have the
highest priority. The
elements with higher
priority are served first.
29
Insertion Operations of a Priority Queue
▪ Create a new element: Create a new element to be inserted into the queue.
This element should include the data value to be stored in the queue and its
associated priority value.
▪ Add the element to the queue: Append the new element to the end of the
queue. This temporarily violates the heap property of the queue.
▪ Restore the heap property: Perform heapify operations to restore the heap
property of the queue. This involves recursively comparing the newly added
element with its parent nodes and swapping them if their priorities are not in
order.
30
How is Priority assigned?
▪ In a priority queue, generally, the value of an element is considered for
assigning the priority.
▪ For example, the element with the highest value is assigned the highest priority
and the element with the lowest value is assigned the lowest priority.
▪ The reverse case can also be used i.e., the element with the lowest value can be
assigned the highest priority. Also, the priority can be assigned according to our
needs.
31
Deletion Operations of a Priority Queue
▪ Deleting an element from a priority queue involves removing the element with
the highest priority while maintaining the heap property of the queue.
▪ Identify the highest priority element: Locate the element with the highest
priority in the queue. This is typically the root node in a max heap or the last
element in a min heap.
▪ Remove the highest priority element: Extract the identified element from the
queue. This creates an empty slot in the heap structure.
32
Deletion Operations of a Priority Queue
▪ Fill the empty slot: To maintain the heap property, a new element needs to be
placed in the empty slot. This is done by moving the last element of the heap to
the empty slot and then performing heapify operations to ensure that the heap
property is restored.
▪ Heapify: The heapify operation involves recursively comparing the new element
with its parent nodes and swapping them if necessary until the heap property is
restored. This ensures that the heap remains sorted after the deletion.
33
Operations of a Priority Queue
▪ Peek in a Priority Queue
o This operation helps to return the maximum element from Max Heap or the
minimum element from Min Heap without deleting the node from the priority
queue.
34
Types of Priority Queue
▪ Ascending Order Priority Queue: As the name suggests, in ascending order
priority queue, the element with a lower priority value is given a higher priority in
the priority list.
▪ For example, if we have the following elements in a priority queue arranged in
ascending order like 4,6,8,9,10. Here, 4 is the smallest number, therefore, it will
get the highest priority in a priority queue.
35
Types of Priority Queue
▪ Descending order Priority Queue : The root node is the maximum element in a
max heap, as you may know. It will also remove the element with the highest
priority first.
▪ As a result, the root node is removed from the queue. This deletion leaves an
empty space, which will be filled with fresh insertions in the future.
▪ The heap invariant is then maintained by comparing the newly inserted element to
all other entries in the queue.
36
Difference between Priority Queue and
Normal Queue?
▪ In Queue, the oldest element is dequeued first. While, in Priority Queue, an
element based on the highest priority is dequeued.
▪ When elements are popped out of a priority queue the result obtained is either
sorted in Increasing order or in Decreasing Order. While, when elements are
popped from a simple queue, a FIFO order of data is obtained in the result.
37
Tree Data Structure
▪ A Tree is a Data structure in which data
items are connected using references in a
hierarchical manner.
▪ Each Tree consists of a root node from
which we can access each element of the
tree.
▪ Starting from the root node, each node
contains zero or more nodes connected to
it as children.
▪ A simple tree can be depicted as seen in
the following figure.
38
Parts of a Tree Data structure
▪ Root Node: Root node is the topmost node of a tree. It is always the first node created
while creating the tree and we can access each element of the tree starting from the
root node. In the above example, the node containing element 50 is the root node.
▪ Parent Node: The parent of any node is the node which references the current node.
In the above example, 50 is the parent of 20 and 45, 20 is parent of 11, 46 and 15.
Similarly 45 is the parent of 30 and 78.
▪ Child Node: Child nodes of a parent node are the nodes at which the parent node is
pointing using the references. In the example above, 20 and 45 are children of 50. The
nodes 11, 46, and 15 are children of 20 and 30 and 78 are children of 45.
39
Parts of a Tree Data structure
▪ Edge: The reference through which a parent node is connected to a child node is
called an edge. In the above example, each arrow that connects any two nodes is an
edge.
▪ Leaf Node: These are those nodes in the tree which have no children. In the above
example, 11, 46, 15, 30, and 78 are leaf nodes.
▪ Internal Nodes: Internal Nodes are the nodes which have at least one child. In the
above example, 50, 20 and 45 are internal nodes.
40
Binary Trees
▪ Binary Tree is defined as a tree data
structure with at most 2 children.
Since each element in a binary tree
can have only 2 children, we
typically name them the left and
right child.
41
Binary Tree
Representation
▪ A Binary tree is represented by a pointer to

the topmost node of the tree. If the tree is
empty, then the value of the root is NULL.
▪ Binary Tree node contains the following parts:
▪ Data
▪ Pointer to left child
▪ Pointer to right child
42
Binary Tree ▪ A binary tree is a tree data
structure in which each node can
have a maximum of 2 children.
▪ It means that each node in a binary
tree can have either one, or two or
no children.
▪ Each node in a binary tree contains
data and references to its children.
Both the children are named as left
child and the right child according
to their position.
43
Example
44
Basic Operation On Binary Tree
▪ Inserting an element.
▪ Removing an element.
▪ Searching for an element.
▪ Traversing an element.
▪ Auxiliary Operation On Binary Tree:
▪ Finding the height of the tree
▪ Find the level of the tree
▪ Finding the size of the entire tree.
45
Arrays
▪ The array is a collection of the same type of elements at contiguous memory
locations under the same name.
▪ It is easier to access the element in the case of an array.
▪ The size is the key issue in the case of an array which must be known in
advance so as to store the elements in it.
▪ No modification is possible at the runtime after the array is created and
memory wastage can also occur if the size of the array is greater than the
number of elements stored in the array
46
Dictionaries
▪ A dictionary is a collection of data values.
▪ It holds a key: value pair in which we can easily access a value if the key is
known.
▪ It improves the readability of your code and makes it easier to debug.
▪ It is fast as the access of a value through a key is a constant time operation.
▪ A dictionary is also called a hash, a map, a HashMap in different programming
languages.
▪ Keys in a dictionary must be unique an attempt to create a duplicate key will
typically overwrite the existing value for that key.
47
Dictionaries
▪ Dictionary is an abstract data structure that supports the following operations:
▪ Search (K key) (returns the value associated with the given key)
▪ Insert (K key, V value)
▪ Delete (K key)
▪ Each element stored in a dictionary is identified by a key of type K.
▪ Dictionary represents a mapping from keys to values.
▪ Other terms for keyed containers include the names map, table, search
table, associative array, or hash.
48
Comparison Between Array and Dictionary:
S.N. Array Dictionary
1. Stores just a set of objects. Represents the relationship
between pair of objects
2. Lookup time is more in the case of Lookup time is less compared to
array O(N), where N is the size of the an array. Generally, it is O(1)
array.
3. Elements are stored at contagious Elements may or may not be
memory locations. stored at a contagious memory
location.
4. Items are unordered, changeable, Items are ordered, changeable,
and do allow duplicates. and do not allow duplicates.
49
Comparison Between Array and Dictionary:
S.N. Array Dictionary
5. Items are not represented as key: Items are represented as key:
value pair value pair
6. The values in the array are of the The values in dictionary items can
same data type be of any data type
7. Values can be accessed randomly To access a value the key is
without the need for any key required.
50
Sets and disjoint sets union
▪ Set: A set is a collection of distinct elements. The Set can be represented, for
examples, as S1= {1,2,5,10}.
▪ Disjoint Sets: The disjoints sets are those do not have any common element. For
example S1={1,7,8,9} and S2={2,5,10}, then we can say that S1 and S2 are two disjoint
sets.
▪ Two sets are called disjoint sets if they don’t have any element in common, the
intersection of sets is a null set.
▪ Disjoint Set Operations: The disjoint set operations are:
▪ Union
▪ Find 51
Sets and disjoint sets union
▪ Disjoint set Union: If Si and Sj are tow disjoint sets, then their union Si U Sj consists
of all the elements x such that x is in Si or Sj.
▪ Example: S1= {1,7,8,9} and S2= {2,5,10} , so S1 U S2={1,2,5,7,8,9,10}
▪ Find: Given the element I, find the set containing i.
▪ Example:
▪ S1={1,7,8,9} S2={2,5,10} S3={3,4,6}
▪ Find(4)= S3 Find(5)=S2 Find(7)=S1
52
Q1. Briefly Explain the Queue data structure. Write an algorithm
to add and remove an element from the circular queue and
compute the complexity of your algorithm.
53
Queue Data Structure ▪ A Queue is defined as a linear data
structure that is open at both ends
and the operations are performed in
First In First Out (FIFO) order.
▪ We define a queue to be a list in
which all additions to the list are
made at one end, and all deletions
from the list are made at the other
end.
▪ The element which is first pushed
into the order, the operation is first
performed on that.
54
Write an algorithm to add and remove an element
from the circular queue and compute the complexity
of your algorithm.
▪ A circular queue is similar to a linear queue as it is also based on the FIFO (First
In First Out) principle except that the last position is connected to the first
position in a circular queue that forms a circle. It is also known as a Ring Buffer.
▪ The circular queue solves the major limitation of the normal queue. In a normal
queue, after a bit of insertion and deletion, there will be non-usable empty
space.
▪ Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all
elements). This reduces the actual size of the queue.
55
Write an algorithm to add and remove an element from the
circular queue and compute the complexity of your algorithm.
▪ A circular queue is similar to a linear queue as it is also based on the FIFO (First
In First Out) principle except that the last position is connected to the first
position in a circular queue that forms a circle. It is also known as a Ring Buffer.
▪ The circular queue solves the major limitation of the normal queue. In a normal
queue, after a bit of insertion and deletion, there will be non-usable empty
space.
▪ Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all
elements). This reduces the actual size of the queue.
56
The steps of enqueue operation are
given below:
Algorithm to insert
an element in a First, we will check whether the Queue is full
or not.
circular queue
Initially the front and rear are set to -1. When
we insert the first element in a Queue, front
and rear both are set to 0.
When we insert a new element, the rear

gets incremented, i.e., rear=rear+1.
57
Algorithm to insert an element in a circular queue
58
The steps of dequeue operation are given
below:
Algorithm to
First, we check whether the Queue is empty
remove an or not. If the queue is empty, we cannot
element in a perform the dequeue operation.
circular queue
When the element is deleted, the value of
front gets decremented by 1.
If there is only one element left which is to

be deleted, then the front and rear are reset
to -1.
59
Algorithm to remove an element in a circular queue
60
Q1. Briefly Explain the Stack data structure. Write an algorithm
to add and remove an element from the stack and compute the
complexity of your algorithm.
61
Stack Data Structure
▪ Stack is a linear data structure which follows a particular order in which the
operations are performed. The order may be LIFO(Last In First Out) or
FILO(First In Last Out).
▪ Stack operations may involve initializing the stack, using it and then de-
initializing it. Apart from these basic stuffs, a stack is used for the following
two primary operations
▪ push() − Pushing (storing) an element on the stack.
▪ pop() − Removing (accessing) an element from the stack.
62
63
▪ Step 1 − Checks if the stack is full.
▪ Step 2 − If the stack is full, produces
an error and exit.
▪ Step 3 − If the stack is not full,
increments top to point next empty
space.
▪ Step 4 − Adds data element to the
stack location, where top is pointing.
▪ Step 5 − Returns success.
64
Stack Data
Structure
▪ Step 1 − Checks if the stack is empty.

▪ Step 2 − If the stack is empty, produces
an error and exit.
▪ Step 3 − If the stack is not empty,
accesses the data element at which top is
pointing.
▪ Step 4 − Decreases the value of top by 1.
▪ Step 5 − Returns success.
65
66
SORTING,
SELECTION AND By: Ashok Basnet
SEQUENCING
Outline
▪ General method of problem solving: Divide and Conquer Method
▪ Binary Search Technique
▪ Finding the Minimum and Maximum
▪ Merge Sort, Quick Sort and Selection Sort
▪ Strassen's Matrix Multiplication
▪ General method of problem solving: The Greedy Method
▪ Knapsack Problem: Fractional Knapsack Problem
▪ Tree Vertex Splitting
▪ Job Sequencing with Deadlines
▪ Minimum Cost Spanning Tree
▪ Optimal Storage Allocation on Magnetic Tapes
▪ Optimal Merge Patterns
Divide and Conquer Method
• Recursion:
o Divide and Conquer Method relies on recursion, where a problem is recursively
broken down into smaller sub-problems.
• Breaking Down the Problem:
o The algorithm divides the problem into two or more sub-problems, often of the
same or related type.
• Solving Sub-Problems:
o The sub-problems are solved independently, either directly if they are simple
enough or by further breaking them down recursively.
• Combining Solutions:
o The solutions to the sub-problems are combined to produce a solution for the
original problem.
• Efficiency:
o D&C often leads to efficient algorithms because it breaks down complex problems
into simpler, manageable sub-problems.
• Applications: D&C is widely used in solving various types of problems, including:
o Sorting Algorithms: such as Quick Sort and Merge Sort.
o Multiplying Large Numbers: for efficient multiplication.
o Closest Pair of Points: finding the closest pair in a set of points.
o Discrete Fourier Transform (FFT): a fast algorithm for computing the DFT.
• Example Algorithms:
o Quick Sort: Sorts an array by partitioning and recursively sorting sub-arrays.
o Merge Sort: Divides the array into two halves, recursively sorts them, and then
merges them.
Divide and Conquer
Method
▪ Divide the problem into a number of

sub problems
▪ Conquer the sub problems by solving
them recursively.
▪ If the sub problem sizes are small
enough, solve the sub problems
recursively, and then combine these
solutions to create a solution to the
original problem.
▪ DANDC (P) {
if SMALL (P) then return S (p);
else
{
divide p into smaller instances p1, p2, …. Pk, k 1;
apply DANDC to each of these sub problems;
return (COMBINE (DANDC (p1) , DANDC (p2),…., DANDC (pk));
}
}
▪ SMALL (P) is a Boolean valued function which determines whether the input size
is small enough so that the answer can be computed without splitting.
▪ If this is so function ‘S’ is invoked otherwise, the problem ‘p’ into smaller sub problems.
These sub problems p1, p2, . . . , pk are solved by recursive application of DANDC.
Binary Search (Recursive and Iterative)
▪ Binary search is a search algorithm used to find the position of a target value
within a sorted array.
▪ It is a highly efficient algorithm with a time complexity of O(log n), where n is
the number of elements in the array.
▪ The key idea behind binary search is to repeatedly divide the search interval in
half.
▪ Steps:
• Initial Setup:
▪ Start with the entire sorted array.
• Define Search Interval:
▪ Define a search interval, initially the entire array.
• Compare with Midpoint:
▪ Compute the midpoint of the interval.
▪ Compare the target value with the value at the midpoint.
Binary Search (Recursive and Iterative)
▪ Steps:
• Adjust Search Interval:
▪ If the target value is equal to the midpoint value, the search is successful, and
the index is returned.
▪ If the target value is less than the midpoint value, adjust the search interval to
the lower half (discard the upper half).
▪ If the target value is greater than the midpoint value, adjust the search interval
to the upper half (discard the lower half).
• Repeat:
▪ Repeat steps 3-4 until the target value is found or the search interval becomes
empty.
• Result:
▪ If the target value is found, return its index.
▪ If the search interval becomes empty, the target value is not in the array, and -
1 is typically returned.
Binary Search (Recursive)
function recursiveBinarySearch(arr, target, low, high):
if low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return recursiveBinarySearch(arr, target, mid + 1, high)
else:
return recursiveBinarySearch(arr, target, low, mid - 1)
else:
return -1
Binary Search (Iterative)
function iterativeBinarySearch(arr, target):
low = 0
high = length(arr) - 1
while low <= high:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Selection sort
• Selection Sort is a simple comparison-based sorting algorithm that divides the input list
into two parts: a sorted portion and an unsorted portion.
• The algorithm repeatedly selects the smallest (or largest, depending on the sorting
order) element from the unsorted portion and swaps it with the first unsorted
element. This process continues until the entire list is sorted.
• Initialization: The entire list is considered unsorted initially.
• Selection of the Smallest Element: Iterate through the unsorted portion of the list to
find the smallest element.
• Swap: Swap the smallest element found in step 2 with the first element in the unsorted
portion.
• Expansion of the Sorted Portion: Expand the sorted portion to include the element that
was just swapped.
• Repeat: Repeat steps 2-4 for the remaining unsorted portion of the list until the entire
list is sorted.
• Result: The list is now sorted.
Selection sort
Selection sort - Iterative
function selectionSort(array, size):

repeat (size - 1) times:
set the first unsorted element as the minimum
for each of the unsorted elements:
if element < currentMinimum:
set element as new minimum
swap minimum with first unsorted position
end repeat
end function
Selection sort - Recursive
function recursiveSelectionSort(arr, start=0):
n = length(arr)
if start < n - 1:
min_index = start
for i from start + 1 to n - 1:
if arr[i] < arr[min_index]:
min_index = i
swap(arr[start], arr[min_index])
recursiveSelectionSort(arr, start + 1)
end function
Merge sort
• Merge Sort is a divide-and-conquer sorting algorithm that works by dividing the
unsorted list into n sublists, each containing one element (making them inherently
sorted), and then repeatedly merging sublists to produce new sorted sublists until there
is only one sublist remaining – the sorted list.
• Here's a step-by-step overview of the Merge Sort algorithm:
o Divide: Divide the unsorted list into n sublists, each containing one element. This is
the base case of the recursion.
o Conquer: Recursively sort each sublist.
o Merge: Merge the sorted sublists to produce new sorted sublists until there is only
one sublist remaining – the sorted list.
• The key operation in Merge Sort is the merging step, where two sorted sublists are
combined into a single sorted sublist. This process is repeated until the entire list is
sorted.
EXAMPLE
Merge sort
function merge_sort(arr):
if length(arr) > 1:
mid = length(arr) // 2
left_half = arr[0:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
merge(arr, left_half, right_half)

function merge(arr, left, right):
i=j=k=0
while i < length(left) and j < length(right):
if left[i] < right[ j]:
arr[k] = left[i]
i=i+1
else:
arr[k] = right[ j]
j=j+1
k=k+1
while i < length(left):
arr[k] = left[i]
i=i+1
k=k+1
while j < length(right):
arr[k] = right[ j]
j=j+1
k=k+1
Quick sort
• Quick Sort is a highly efficient and widely used sorting algorithm that falls under the
category of divide-and-conquer algorithms.
• The algorithm works by selecting a "pivot" element from the array and partitioning
the other elements into two sub-arrays according to whether they are less than or
greater than the pivot.
• The sub-arrays are then recursively sorted.
• Here's a high-level overview of the Quick Sort algorithm:
• Partitioning:
▪ Choose a pivot element from the array.
▪ Partition the other elements into two sub-arrays: elements less than the pivot and
elements greater than the pivot.
• Recursion:
▪ Recursively apply the Quick Sort algorithm to the two sub-arrays.
• Combine:
▪ The sorted sub-arrays are combined to produce the final sorted array.
Quick sort
Selection Sort, Merge Sort, and Quick Sort
Selection Sort Merge Sort Quick Sort
• Time Complexity: O(n^2) • Time Complexity: O(n log n) • Time Complexity: O(n log n) in
in the worst and average in all cases (worst, average, the average case, O(n^2) in the
cases. and best). worst case (can be mitigated
• In-Place: Yes. • In-Place: No (requires with randomization or careful
• Stability: No. additional space for pivot selection).
• Use Cases: Small datasets, merging). • In-Place: Yes (with the potential
simple implementations, • Stability: Yes. for log n recursion stack in the
and situations where in- • Use Cases: Large datasets, worst case).
place sorting is crucial. situations where stability is • Stability: No.
important, linked lists, and • Use Cases: General-purpose
external sorting. sorting, large datasets,
situations where average-case
performance is crucial.
• Time Complexity:
• Quick Sort has an average-case time complexity of O(n log n), making it more
efficient than Selection Sort for larger datasets. However, Quick Sort's worst-case
time complexity is O(n^2), which can be a concern in certain situations.
• Merge Sort consistently performs at O(n log n) in all cases, making it a reliable choice
when a stable sort is needed.
• Selection Sort consistently has a time complexity of O(n^2), making it less efficient for
large datasets.
• In-Place vs. Extra Space:
• Selection Sort and Quick Sort are in-place algorithms, meaning they don't require
additional memory proportional to the size of the input.
• Merge Sort, on the other hand, requires additional space for merging, proportional to
the size of the input. This can be a drawback in terms of space complexity.
• Stability:
• Quick Sort is not stable, meaning equal elements may not maintain their original
order.
• Selection Sort is not stable.
• Merge Sort is stable.
• Ease of Implementation:
• Selection Sort is straightforward to implement.
• Quick Sort involves partitioning and recursion and can be more challenging to
implement correctly.
• Merge Sort is relatively easy to implement but involves additional memory.
Finding the Maximum and Minimum
• The Max-Min Problem in algorithm analysis is finding the maximum and
minimum value in an array.
• To find the maximum and minimum numbers in a given array numbers[ ] of
size n, the following algorithm can be used.
• naive method
• divide and conquer approach.
Naïve Method
• Naïve method is a basic method to solve any problem. In this method, the
maximum and minimum number can be found separately.
• Algorithm:
• Naive_Max_Min(numbers[ ])
Initialize max_value and min_value to the first element of the array
For each element num in numbers[1:]:
If num > max_value:
update max_value
If num < min_value:
update min_value
Return (max_value, min_value)
• The number of comparison in Naive method is 2n - 2. The number of
comparisons can be reduced using the divide and conquer approach.
Divide and Conquer Approach
• Divide the array into two halves.

• Recursively find the maximum and minimum values in each half.
• Combine the results by taking the maximum of two maxima and the
minimum of two minima.
Divide and Conquer Approach
DivideConquer_Max_Min(numbers, low, high):
If low == high:
return (numbers[low], numbers[low])
If high == low + 1:
compare numbers[low] and numbers[high] to determine max and min
Otherwise:
mid = (low + high) / 2
(max1, min1) = DivideConquer_Max_Min(numbers, low, mid)
(max2, min2) = DivideConquer_Max_Min(numbers, mid + 1, high)
Return (max(max1, max2), min(min1, min2))
STRASSEN'S MATRIX
MULTIPLICATION
Strassen's Matrix Multiplication
• Indeed, Strassen's Matrix Multiplication is a divide-and-conquer-based algorithm
that aims to reduce the time complexity of matrix multiplication compared to the
traditional cubic time complexity (O(n^3)).
• The algorithm operates by dividing each input matrix into four smaller matrices
and recursively multiplying these smaller matrices.
• It involves seven recursive multiplications instead of the traditional eight.
• The time complexity of Strassen's algorithm is approximately O(n^log2(7)),
which is about O(n^2.81).
• This improvement over the naive cubic time complexity is achieved through
clever mathematical manipulations.
Strassen's Matrix
Multiplication
• For larger matrices this approach will
continue until we recurse all the
smaller sub matrices.
• Suppose we have two matrices, A and
B, and we want to multiply them to
form a new matrix, C.
• C=AB, where all A,B,C are square
matrices. We will divide these larger
matrices into smaller sub matrices
n/2.
• Matrix Partitioning:
• Given two matrices A and B, each of size n x n, divide them into four equal-sized
submatrices. Let A be divided into A11, A12, A21, and A22, and B into B11, B12,
B21, and B22.
• Recursive Multiplication:
• Recursively compute seven products using the smaller submatrices:
• P1 = A11 * (B12 - B22)
• P2 = (A11 + A12) * B22
• P3 = (A21 + A22) * B11
• P4 = A22 * (B21 - B11)
• P5 = (A11 + A22) * (B11 + B22)
• P6 = (A12 - A22) * (B21 + B22)
• P7 = (A11 - A21) * (B11 + B12)
• Matrix Combinations:
• Compute the four quadrants of the result matrix using these products:
• C11 = P5 + P4 - P2 + P6
• C12 = P1 + P2
• C21 = P3 + P4
• C22 = P5 + P1 - P3 - P7
• Merge:
• Combine the four quadrants to form the final result matrix C.
▪ Steps of Strassen’s matrix multiplication:
o Divide the matrices A and B into smaller submatrices of the size n/2xn/2.
o Using the formula of scalar additions and subtractions compute smaller matrices
of size n/2.
o Recursively compute the seven matrix products P i = Ai Bi for i=1,2,…7.
o Now compute the r,s,t,u submatrices by just adding the scalars obtained from
above points.
▪ In the above divide and conquer method, the main component for high time
complexity is 8 recursive calls. The idea of Strassen’s method is to reduce the
number of recursive calls to 7.
▪ Exercise
RECURRENCE RELATION
Recurrence Relation
• A recurrence relation is a mathematical expression that defines a sequence recursively in
terms of one or more of its preceding terms. In other words, it is a way of defining the
terms of a sequence based on the values of earlier terms in the sequence.
• A general form of a recurrence relation for a sequence {a_n} is often written as:
an = f (an−1 ,an−2 ,…,an−k )
• Here, an represents the nth term in the sequence, and f is a function that relates the
current term to one or more previous terms (up to k previous terms).
• Recurrence relations are commonly used in various branches of mathematics, computer
science, and other scientific fields to model and analyze processes that evolve over time
in a step-by-step manner.
• For example, the Fibonacci sequence is defined by the recurrence relation:
F (n) = F (n − 1) + F (n − 2)
• with initial conditions F (0)=0 and F (1)=1. This recurrence relation defines each term in
the Fibonacci sequence in terms of the two preceding terms.
Recurrence Relation
• Let's consider a simple example of a recurrence relation. Suppose we have a sequence
defined by the recurrence relation:
an = 2an−1 + 3
• with an initial condition a0 =1.
• Let's use this recurrence relation to find the first few terms of the sequence:
a1 = 2a0 +3= 2×1+3=5
a2 = 2a1 +3= 2×5+3=13
a3 = 2a2 +3= 2×13+3=29
• This recurrence relation expresses each term an in terms of the previous term an−1 and a
constant term (3 in this case). Solving the recurrence relation means finding a closed-
form expression for an in terms of n without referring to previous terms.
• Depending on the specific recurrence relation, this process might involve techniques like
substitution, characteristic equations, or other methods depending on the complexity of
the relation.
Recurrence Relation
• Linear Recurrence Relations:
• The example provided earlier (an = 2an−1 + 3) is a linear recurrence relation because
each term is a linear combination of previous terms.
• Linear recurrence relations are common and often have closed-form solutions.
• Initial Conditions:
• To fully specify a sequence defined by a recurrence relation, you typically need initial
conditions. In the example, a0 = 1 is an initial condition.
• Degree of Recurrence:
• The degree of a recurrence relation is determined by the highest power of the
term an in the relation. In the linear example, the degree is 1.
• Homogeneous and Non-homogeneous Recurrence Relations:
• A homogeneous recurrence relation has no external terms (like constants) on the
right-hand side of the equation. For example, an = 2an−1 is homogeneous.
• A non-homogeneous recurrence relation includes external terms. The previous
example an = 2an−1 + 3 is non-homogeneous.
Setting up a Recurrence Relation
• Recurrence relations are used to reduce complicated problems to an
iterative process based on simpler versions of the problem. An example
problem in which this approach can be used is the Tower of Hanoi puzzle.
• It's not immediately clear that a recursion solution will work for this
problem. However, there are a couple things about this problem that make
it a good candidate to solve with a recurrence relation.
• Identifying a candidate problem to solve with a recurrence relation:
o The problem can be reduced to simpler cases. The Tower of Hanoi puzzle can be
simplified by removing some of the disks.
o There is a numerical value, n, to identify each case. For the Tower of Hanoi puzzle, this
numerical value is the number of disks.
o The problem increases in complexity as the numerical identifier increases. As the
number of disks in the Tower of Hanoi problem increases, it becomes more difficult to
find a solution.
• The goal for this exercise will be to develop a recurrence relation for T
Setting up a Recurrence Relation
• Recurrence relations are used to reduce complicated problems to an
iterative process based on simpler versions of the problem. An example
problem in which this approach can be used is the Tower of Hanoi puzzle.
• The Tower of Hanoi puzzle consists of three vertical pegs and several disks
of various sizes. Each disk has a hole in its center for the pegs to go
through.
• The rules of the puzzle are as follows:
o The puzzle begins with all disks placed on one of the pegs. They are placed in order of
largest to smallest, bottom to top.
o The goal of the puzzle is to move all of the disks onto another peg.
o Only one disk may be moved at a time, and disks are always placed onto pegs.
o Disks may only be moved onto an empty peg or onto a larger disk.
• Let Tn be defined as the minimum number of moves needed to solve a
puzzle with n disks.
Recurrence
Relation • The most simple version of the Tower
of Hanoi puzzle would contain only one
disk.
• In terms of the recurrence relation, n=1.
o T0 =1, because it would only
take 1 move to move all the disks to
another peg.
Recurrence Relation
• Below is the solution to a Tower of Hanoi puzzle with n=2.
• It can be seen from below that T1 =3.
Recurrence Relation
• Below is a solution to a Tower of Hanoi puzzle with n=3.
• It can be seen from above that T2 = 7.
Recurrence Relation
• In terms of n,
o Do Tn−1 moves to get the smaller disks off the largest disk.
o Do 1 move to move the largest disk.
o Do Tn−1 moves to get the smaller disks back onto the largest disk.
• In total, the number of moves for n disks is
o Tn = 2Tn−1 +1
Recurrence Relation
#include <stdio.h>
void Test(int n) {
if (n > 0) {
printf("%d ", n); // Print the value
Test(n - 1); // Recursive call
}
}
int main() {
int n = 5; // You can change this to the desired value of n
Test(n);
return 0;
}
Preparing Recurrence Relation
void Test(int n) { // n
if (n > 0) {
printf("%d ", n); // 1
Test(n - 1); // n-1
}
}
▪ So, T (n) = T (n-1) + 1
▪ Hence, T (n) = 1 for n=0, and T (n-1) + 1 for n>0
Solving Recurrence Relation
• Definition of Recurrence Relation: T (n) = T (n−1)+1
• Initial Condition: T (n) = 1 for n = 0
• Substituting and Simplifying:
▪ T (n) = T (n−1) + 1
▪ T (n−1) = T (n−2) + 1
• Substitute T (n−1) into the first equation: T (n) = T (n−2) + 2
• Continue substituting T (n−k) for k times: T (n) = T (n−k) + k
• Assuming n-k=0: T (n) = T (0) + n = n + 1
void Test(int n) {
if (n > 0) {
for (int i = 1; i < n; i = i + 1) {
printf("%d", n);
}
Test(n - 1);
}
}
▪ So, T (n) = T (n-1) + n

▪ Hence, T (n) = 1 for n=0, and T (n-1) + n for n>0
▪ Solving above recurrence relation:
▪ T (n) = T (n-1) + n
▪ T (n-1) = T (n-2) + (n-1)
▪ Substitute T (n-1), Hence T (n) = T (n-2) + (n-1) + n
▪ T (n) = T (n-3) + (n-2) + (n-1) + n ….. continue for k times
▪ Assume n-k=0, then n=k hence T(n) = 1 + 2 + 3 + ….... + n = n(n+1) / 2
▪ Time complexity = O(n 2)
void Test(int n) {
if (n > 0) {
for (int i = 1; i < n; i = i * 2) {
printf("%d", n);
}
Test(n - 1);
}
}
o So, T (n) = T (n-1) + log(n)
o Hence, T (n) = 1 for n=0, and T (n-1) + log(n) for n>0
o Solving above recurrence relation:
o T (n) = T (n-1) + log(n)
o T (n-1) = T (n-2) + log(n-1)
o Substitute T (n-1), Hence T (n) = T (n-2) + log(n-1) + log(n)
o T (n) = T (n-3) + log(n-2) + log(n-1) + log(n) ….. continue for k times
o T (n) = T (n-k) + log1 + log2 + …... + log(n-1) + log(n)
o Assume n-k=0, then n=k hence T (n) = T (0) + log(n!) = 1 + log(n!)
o Time complexity = O(nlogn)
Recurrence Relation
▪ Hence, from above relations:
o T(n) = T(n-1) + 1 = O(n)
o T(n) = T(n-1) + n = O(n2)
o T(n) = T(n-1) + logn = O(nlogn)
o T(n) = T(n-1) + n2 = O(n3)
Master Theorem
Master Method for recurrence relation
• In master method, the problem is divided into number of subproblems each of
size n/b and need f(n) time to combine and or break the solution.
• T(n) = aT(n/b) + f(n),
• where,
• n = size of input
• a = number of subproblems in the recursion
• n/b = size of each subproblem. All subproblems are assumed to have
the same size.
• f(n) = cost of the work done outside the recursive call, which includes
the cost of dividing the problem and cost of merging the solutions
•
• Here, a ≥ 1 and b > 1 are constants, and f(n) is an asymptotically positive
function.
Example: Master Theorem
Example-1: Binary Search – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 and p = 0
bk = 1. So, a = bk and p > -1 [Case 2.(a)]
T(n) = θ(nlogba logp+1n)
T(n) = θ(logn)
Example-2: Merge Sort – T(n) = 2T(n/2) + O(n)

a = 2, b = 2, k = 1, p = 0
Example bk = 2. So, a = bk and p > -1 [Case 2.(a)]

T(n) = θ(nlogba logp+1n)
T(n) = θ(nlogn)
Example-3: T(n) = 3T(n/2) + n2

a = 3, b = 2, k = 2, p = 0
bk = 4. So, a < bk and p = 0 [Case 3.(a)]
T(n) = θ(nk logpn)
T(n) = θ(n2)
Example-4: T(n) = 3T(n/2) + log2n
a = 3, b = 2, k = 0, p = 2
bk = 1. So, a > bk [Case 1]
T(n) = θ(nlogba )
T(n) = θ(nlog23)
Example-5: T(n) = 2T(n/2) + nlog2n

a = 2, b = 2, k = 1, p = 2
bk = 2. So, a = bk [Case 2.(a)]
Example T(n) = θ(nlogbalogp+1n )
T(n) = θ(nlog22log3n)
T(n) = θ(nlog3n)
Example-6: T(n) = 2nT(n/2) + nn
This recurrence can’t be solved using above
method since function is not of form T(n) = aT(n/b)
+ θ(nk logpn)
THE GREEDY METHOD
The Greedy Method
• The greedy method is a simple strategy of progressively building up a solution,
one element at a time, by choosing the best possible element at each stage.
• At each stage, a decision is made regarding whether or not a particular input is
in an optimal solution. This is done by considering the inputs in an order
determined by some selection procedure.
• If the inclusion of the next input, into the partially constructed optimal solution
will result in an infeasible solution then this input is not added to the
partial solution.
• The selection procedure itself is based on some optimization measure.
Several optimization measures are plausible for a given problem.
• Most of them, however, will result in algorithms that generate sub-
optimal solutions. This version of greedy technique is called subset paradigm.
The Greedy Method
• Some problems like Knapsack, Job sequencing with deadlines and minimum
cost spanning trees are based on subset paradigm.
• For the problems that make decisions by considering the inputs in some order,
each decision is made using an optimization criterion that can be computed
using decisions already made.
• This version of greedy method is ordering paradigm. Some problems
like optimal storage on tapes, optimal merge patterns and single source
shortest path are based on ordering paradigm.
The Greedy Algorithm
The Greedy Algorithm
• Greedy is an algorithmic paradigm that builds up a solution piece by piece,
always choosing the next piece that offers the most obvious and immediate
benefit.
• So, the problems where choosing locally optimal also leads to global
solution are the best fit for Greedy.
• For example consider the Fractional Knapsack Problem. The local optimal
strategy is to choose the item that has maximum value vs weight ratio.
• This strategy also leads to a globally optimal solution because we are allowed to
take fractions of an item.
Fractional Knapsack Problem
• Given the weights and values of N items, in the form of {value, weight} put these items in
a knapsack of capacity W to get the maximum total value in the knapsack.
• In Fractional Knapsack, we can break items for maximizing the total value of the knapsack.
• In the 0-1 Knapsack problem, we are not allowed to break items. We either take the whole
item or don’t take it.
• Input: arr[] = {{60, 10}, {100, 20}, {120, 30}}, W = 50
• Output: 240
• Explanation: By taking items of weight 10 and 20 kg and 2/3 fraction of 30 kg.
• Hence total price will be 60 + 100 + (2/3) (120) = 240
• Input: arr[] = {{500, 30}}, W = 10
• Output: 166.667
Fractional Knapsack Problem
• The basic idea of the greedy approach is to calculate the ratio value/weight for
each item and sort the item on the basis of this ratio.
• Then take the item with the highest ratio and add them until we can’t add the
next item as a whole and at the end add the next item as much as we can. Which
will always be the optimal solution to this problem. It uses following steps:
Calculate the ratio(value/weight) for each item.
sort all the items in decreasing order of the ratio.
initialize result =0, current_capacity = given_capacity.
do the following for every item “i” in the sorted order:
If the weight of the current item is less than or equal to the remaining capacity then add
the value of that item into the result
Else add the current item as much as we can and break out of the loop.
return result.
Knapsack Problem
• Say we have knapsack of capacity(m) = 20
Objects Obj1 Obj2 Obj3
Profit 25 24 15
Weight 18 15 10
1. Greedy about profit : Obj1 have max profit. Now Remaining weight: 2kg. Now
obj2 can only be included 2/15 of obj2. So overall profit = 25 + 24*2/15 = 28.2
2. Greedy about weight: Here we put least profitable object. Minimum weight
object is obj3, we put it in the bag. Then 10/15 of the obj2 is added.
So overall profit: 15 + 24*2/3 = 31
Knapsack Problem
• Say we have knapsack of capacity(m) = 20
Objects Obj1 Obj2 Obj3
Profit 25 24 15
Weight 18 15 10
p/w 1.3 1.6 1.5
• But we are not getting optimal solution from the previous method.
• So compute profit/weight
• So highest proportion is of object 2. We put obj2 in knapsack.
• Remaining capacity: 20-15 = 5kg
• Then we select 5/10th of obj3. So, remaining capacity: 0kg
• Profit = 24 + 15 * ½ = 24+7.5 = 31.5
Knapsack Problem Algorithm
• Knapsack Problem: Algorithm

for i=1 to n:
calculate profit / weight ratio
Sort objects in decreasing order of profit / weight ratio
for i=1 to n:
If m > 0 and wi <= m
m = m - wi
p = p + pi
else break,
if(m > 0)
p = p + pi (m / wi)
Input: n: Number of items, weights[]: Array of item weights, profits[]: Array of item profits, m:
Knapsack capacity
1. Create an array ratio[] to store profit/weight ratios for each item.
2. For i = 1 to n:
a. Calculate profit/weight ratio for each item: ratio[i] = profits[i] / weights[i].
3. Sort objects in decreasing order of profit/weight ratio.
4. Initialize variables:
- totalProfit = 0, remainingCapacity = m
5. For i = 1 to n:
a. If remainingCapacity > 0 and weights[i] <= remainingCapacity:
- Include the entire item in the knapsack.
- remainingCapacity - = weights[i]
- totalProfit += profits[i]
b. Otherwise, break out of the loop.
6. If remainingCapacity > 0:
- Include a fraction of the next item to fill the remaining capacity.
- totalProfit += (remainingCapacity / weights[i]) * profits[i]
7. Output totalProfit as the maximum achievable profit.
Knapsack Problem
Object(O) 1 2 3 4 5 6 7
Profits(P) 10 5 15 7 6 18 3
Weights(w) 2 3 5 7 1 4 1
▪ There are n=7 items

▪ Capacity, m = 15 kg
▪ So, problem is container loading problem
Knapsack Problem
Object(O) 1 2 3 4 5 6 7
Profits(P) 10 5 15 7 6 18 3
Weights(w) 2 3 5 7 1 4 2
• There are n=7 items

• Capacity, m = 15 kg
• So, problem is container loading problem
P/w 5 1.6 3 1 6 4.5 3

X Second: 1 First: 1
x1 x2 x3 x4 x5 x6 x7
• 15-1 = 14kg
• 14-2 = 12kg and so on
Knapsack Problem
Object(O) 1 2 3 4 5 6 7
Profits(P) 10 5 15 7 6 18 3
Weights(w) 2 3 5 7 1 4 2
P/w 5 1.6 3 1 6 4.5 3

X Second: 1 2/3 1 0 First: 1 1 1
x1 x2 x3 x4 x5 x6 x7
15-1 = 14kg
14-2 = 12kg
12-4 = 8kg
8-5 = 3kg
3-1 = 2kg
2-2 = 0
Knapsack Problem
Object(O) 1 2 3 4 5 6 7
Profits(P) 10 5 15 7 6 18 3
Weights(w) 2 3 5 7 1 4 2
P/w 5 1.3 3 1 6 4.5 3

X Second: 1 2/3 1 0 First: 1 1 1
x1 x2 x3 x4 x5 x6 x7
o Compute sum(xiwi)
o Profit sum(xipi)
o Constraint Sum(xiwi) <= m
o Objective Sum(xipi) needs to be maximum
o Hence constraint needs to be fulfilled having maximized objective function.
o Code Implementation
Job Sequencing with deadlines
• When we are given a set of ‘n’ jobs. Associated with each Job i, deadline di
>= 0 and profit Pi >= 0.
• For any job ‘i’ the profit pi is earned iff the job is completed by its deadline.
• Only one machine is available for processing jobs. An optimal solution is
the feasible solution with maximum profit.
• Sort the jobs in ‘j’ ordered by their deadlines. The array d [1 : n] is used to store
the deadlines of the order of their p-values.
• The set of jobs j [1 : k] such that j [r], 1 ≤ r ≤ k are the jobs in ‘j’ and d (j [1]) ≤ d
(j[2]) ≤ . . . ≤ d (j[k]).
• There are n jobs to be processed on a machine.
• Each job i has a deadline di ≥ 0 and profit pi ≥ 0 .
• Pi is earned iff the job is completed by its deadline.
• The job is completed if it is processed on a machine for unit time.
• Only one machine is available for processing jobs.
• Only one job is processed at a time on the machine.
• A feasible solution is a subset of jobs J such that each job is completed
by its deadline.
• An optimal solution is a feasible solution with maximum profit value.
Using Greedy Method
• Step-01:
• Sort all the given jobs in decreasing order of their profit.
• Step-02:
• Check the value of maximum deadline.
• Draw a Gantt chart where maximum time on Gantt chart is the value of maximum
deadline.
• Step-03:
• Pick up the jobs one by one.
• Put the job on Gantt chart as far as possible from 0 ensuring that the job gets
completed before its deadline.
Using Greedy Method
Jobs J1 J2 J3 J4 J5 J6
Deadlines 5 3 3 2 4 2
Profits 200 180 190 300 120 100
• Write the optimal schedule that gives maximum profit.

• Are all the jobs completed in the optimal schedule?
• What is the maximum earned profit?
Using Greedy Method
Jobs J4 J1 J3 J2 J5 J6
Deadlines 2 5 3 3 4 2
Profits 300 200 190 180 120 100
• Step-01: Sort all the given jobs in decreasing order of their profit.
• Step-02: Value of maximum deadline: 5. So, draw a Gantt chart with maximum time on Gantt
chart = 5.
• We take each job one by one in the order they appear in Step-01.
• We place the job on Gantt chart as far as possible from 0.
• We take job J4. Since its deadline is 2, so we place it in the first empty cell before deadline 2.
• Now, we take job J5. Since its deadline is 4, so we place it in the first empty cell before deadline
4.
• The only job left is job J6 whose deadline is 2. All the slots before deadline 2 are already
occupied. Thus, job J6 can not be completed.
Using Greedy Method
Job Slot Assigned Solution Profit
Considered
-------- ------- --------- 0
J1 [4, 5] J1 200
J2 [0, 1], [4, 5] J2, J1 380
J3 [0, 1], [2, 3], , [4, 5] J2, J3, J1 570
J4 [0, 1], [1, 2], [2, 3], [4, 5] J2, J4, J3, J1 870
J5 [0, 1], [1, 2], [2, 3], [3, 4], [4, 5] J2, J4, J3, J5, J1 990
J6 ------- ------- ----------
Using Greedy Method
• Summary:
• The optimal schedule is: J2 , J4 , J3 , J5 , J1
• This is the required order in which the jobs must be completed in
order to obtain the maximum profit.
• All the jobs are not completed in optimal schedule.
• This is because job J6 could not be completed within its deadline.
• Maximum earned profit
▪ Sum of profit of all the jobs in optimal schedule
▪ Profit of job J2 + Profit of job J4 + Profit of job J3 + Profit of job J5
+ Profit of job J1
▪ 180 + 300 + 190 + 120 + 200 = 990 units
Exercise
Jobs J1 J2 J3 J4 J5
Deadlines 2 1 3 2 1
Profits 60 100 20 40 20
Jobs J1 J2 J3 J4 J5
Profits 20 15 10 5 1
Deadlines 2 2 1 3 3
Optimal Merge Patterns
• Let's say we want merge two array:
A B
3 5
8 9
12 11
20 16
• Here we can compare elements from two array and place in the new array.
• Time taken to merge these items is the sum of number of elements in each list.
• Say we have 5 array with multiple elements to be merged, then we need optimal
way to merge them.
• Given n number of sorted files, the task is to find the minimum computations
done to reach the Optimal Merge Pattern.
• When two or more sorted files are to be merged altogether to form a single file,
the minimum computations are done to reach this file are known as Optimal
Merge Pattern.
• If more than 2 files need to be merged then it can be done in pairs. For example,
if need to merge 4 files A, B, C, D. First Merge A with B to get X1, merge X1 with
C to get X2, merge X2 with D to get X3 as the output file.
• If we have two files of sizes m and n, the total computation time will be m+n.
Here, we use the greedy strategy by merging the two smallest size files among
all the files present.
• Examples: Given 3 files with sizes 2, 3, 4 units. Find an optimal way to combine
these files
• Given ‘n’ sorted files, there are many ways to pair wise merge them into a
single sorted file.
• As, different pairings require different amounts of computing time, we
want to determine an optimal (i.e., one requiring the fewest comparisons)
way to pair wise merge ‘n’ sorted files together.
• This type of merging is called as 2-way merge patterns.
• To merge an n-record file and an m-record file requires possibly n + m
record moves, the obvious choice is, at each step merge the two smallest
files together.
• The two-way merge patterns can be represented by binary merge trees.
• Solve:
• Given five files (X1, X2, X3, X4, X5) with sizes (20, 30, 10, 5, 30). Apply
greedy rule to find optimal way of pair wise merging to give an optimal
solution using binary merge tree representation.
• Solve:
• Consider the sequence {3, 5, 9, 11, 16, 18, 20}. Find optimal merge patter
for this data
Algorithm: TREE (n)

for i := 1 to n – 1 do
declare new node
node.leftchild := least (list) // function returns minimum
element from tree and delete it.
node.rightchild := least (list)
node.weight) := ((node.leftchild).weight) +
((node.rightchild).weight)
insert (list, node);
return least (list);
Optimal Storage Allocation on Magnetic Tapes
• Given n programs P1, P2, …, Pn of length L1, L2, …, Ln respectively, store
them on a tape of length L such that Mean Retrieval Time (MRT) is a
minimum.
• The retrieval time of the jth program is a summation of the length of first j
programs on tape.
• Let Tj be the time to retrieve program P j. The retrieval time of Pj is
computed as,
• Mean retrieval time of n programs is the average time required to retrieve
any program.
• It is required to store programs in an order such that their Mean Retrieval
Time is minimum. MRT is computed as,
• In this case, we have to find the permutation of the program order which
minimizes the MRT after storing all programs on single tape only.
• There are many permutations of programs. Each gives a different MRT.
Consider three programs (P1, P2, P3) with a length of (L1, L2, L3) = (5, 10, 2).
• Let's find the MRT for different permutations. 6 permutations are possible
for 3 items.
• The Mean Retrieval Time for each permutation is listed in the following
table.
• It should be observed from the above table that the MRT is 26/3, which is
achieved by storing the programs in ascending order of their length.
• Thus, greedy algorithm stores the programs on tape in non-decreasing
order of their length, which ensures the minimum MRT.
Algorithm MRT_SINGLE_TAPE(L):
// Description: Find storage order of n programs such that mean retrieval
time is minimum
// Input: L is an array of program lengths sorted in ascending order
// Output: Minimum Mean Retrieval Time
Tj ← 0 // Initialize total retrieval time
for i ← 1 to n do
for j ← 1 to i do
Tj ← Tj + L[j] // Accumulate retrieval time for each program
end for
end for
MRT ← Tj / n // Calculate mean retrieval time
return MRT
Minimum Cost Spanning Tree
• A minimum spanning tree (MST) is a tree that spans all the vertices in a
connected, undirected graph while minimizing the sum of the weights
(costs) of the edges.
• In simpler terms, it is a subset of the edges of the graph that forms a tree
and connects all the vertices with the minimum possible total edge weight.
• A single graph can have multiple spanning trees.
• A Minimum Spanning Tree(MST) or minimum weight spanning tree for a
weighted, connected, undirected graph is a spanning tree having a weight
less than or equal to the weight of every other possible spanning tree.
• The weight of a spanning tree is the sum of weights given to each edge of
the spanning tree.
• Key characteristics of a minimum spanning tree:
• Spanning Tree: It covers all the vertices of the graph without forming
any cycles.
• Acyclic: It does not contain any cycles since it is a tree.
• Connected: It connects all the vertices of the original graph.
• Minimum Weight: The sum of the edge weights in the spanning tree is
minimized.
• A Graph is a non-linear data structure consisting of vertices and edges.
More formally a Graph is composed of a set of vertices( V ) and a set of
edges( E ). The graph is denoted by G(E, V).
• Vertices: Vertices are the fundamental units of the graph. Sometimes,
vertices are also known as vertex or nodes. Every node/vertex can be
labeled or unlabeled.
• Edges: Edges are drawn or used to connect two nodes of the graph. It can
be ordered pair of nodes in a directed graph. Edges can connect any two
nodes in any possible way. There are no rules. Sometimes, edges are also
known as arcs. Every edge can be labeled/unlabeled.
• Graphs are used to solve many real-life problems. Graphs are used to
represent networks. The networks may include paths in a city or telephone
network or circuit network.
• If G(V, E) is a graph then every spanning tree of graph G consists of (V – 1)
edges, where V is the number of vertices in the graph and E is the number
of edges in the graph.
• Consider a complete graph of three vertices and all the edge weights are the
same then there will be three spanning trees(which are also minimal) of the same
path length are possible.
• For any cut C of the graph, if the weight of an edge E in the cut-set of C is
strictly smaller than the weights of all other edges of the cut-set of C, then
this edge belongs to all the MSTs of the graph.
• Consider Example with possible spanning tree
• Algorithms for finding Minimum Spanning Tree(MST):-
o Prim’s Algorithm
o Kruskal’s Algorithm
Prim’s Algorithm
• It starts with an empty spanning tree. The idea is to maintain two sets of
vertices.
• The first set contains the vertices already included in the MST, the other
set contains the vertices not yet included.
• At every step, it considers all the edges that connect the two sets and picks
the minimum weight edge from these edges.
• After picking the edge, it moves the other endpoint of the edge to the set
containing MST.
• A group of edges that connects two sets of vertices in a graph is called cut
in graph theory.
• So, at every step of Prim’s algorithm, find a cut (of two sets, one contains
the vertices already included in MST and the other contains the rest of the
vertices), pick the minimum weight edge from the cut, and include this
vertex to MST Set (the set that contains already included vertices).
Prim’s Algorithm
Prim's Algorithm(Graph G):
1. Initialize an empty priority queue Q.
2. Add an arbitrary starting vertex to the priority queue.
3. While Q is not empty:
a. Extract the edge with the smallest weight from Q.
b. If adding this edge doesn't form a cycle, add it to the minimum
spanning tree.
c. Add the vertex at the other end of the chosen edge to the priority
queue if not already present.
4. Return the minimum spanning tree.
Prim’s Algorithm
Prim’s Algorithm (Start with minimum edge and
then start adding connected smallest)
Prim’s Algorithm
Kruskal’s Algorithm
Kruskal's Algorithm(Graph G):
1. Sort all edges in non-decreasing order of their weights.
2. Initialize an empty minimum spanning tree.
3. Initialize a data structure to keep track of connected components.
4. For each edge in the sorted order:
a. If adding the edge does not create a cycle, add it to the minimum
spanning tree and merge the connected components.
5. Return the minimum spanning tree.
• Now pick all edges one by one from the sorted list of edges
Step 1: Pick edge 7-6: No cycle is formed, include it.
• Step 2: Pick edge 8-2: No cycle is formed, include it.

• Step 6: Pick edge 8-6: Since including this edge results in the cycle, discard
• Step 8: Pick edge 7-8: Since including this edge results in the cycle, discard.
• Step 10: Pick edge 1-2: Since including this edge results in the cycle,
discard it.
• Note: Since the number of edges included in the MST equals to (V – 1), so
the algorithm stops here.
Characteristic Prim's Algorithm Kruskal's Algorithm
Greedy Strategy Prim's algorithm is Vertex-centric Kruskal's algorithm is Edge-centric
Data Structures Priority queue (or min-heap) Disjoint set data structure (union-find)
Selects edge with minimum weight Selects edge with minimum weight
Edge/Vertex
connecting a vertex in the current tree to from the sorted list of edges without a
Selection
a vertex outside the tree predetermined starting point
O(E log V), where E is the number of O(E log E), where E is the number of
Complexity
edges, V is the number of vertices edges
Starts with a single vertex and grows Starts with an empty tree and adds
Starting Point
the tree edges
Suitable for dense graphs or graphs Suitable for sparse graphs or graphs
Applications
with dense clusters with edges of similar weights
Terminates when all vertices are Terminates when all vertices are
Termination
included in the minimum spanning tree included in the minimum spanning tree
Tree Vertex Splitting
• Directed and weighted binary tree
• Consider a network of power line transmission
• The transmission of power from one node to the other results in some
loss, such as drop in voltage
• Each edge is labeled with the loss that occurs (edge weight)
• Network may not be able to tolerate losses beyond a certain level
• You can place boosters in the nodes to account for the losses
• Definition 1 Given a network and a loss tolerance level, the tree
vertex splitting problem is to determine the optimal placement
of boosters.
• You can place boosters only in the vertices and nowhere else
• The tree vertex splitting problem involves optimizing the placement of boosters
in a directed and weighted binary tree, representing a power transmission
network.
• The objective is to minimize losses, which are associated with the edges
(transmission lines) in the tree.
• Network Description:
• The network is represented as a directed and weighted binary tree.
• Nodes in the tree correspond to locations in the power transmission network.
• Edges in the tree are labeled with weights that represent the losses occurring
during the transmission between nodes.
• Loss Tolerance Level:
• There is a specified loss tolerance level that the network can withstand.
• The total loss along a path from the source to any node should not exceed
this tolerance level.
• Objective:
• The goal is to determine the optimal placement of boosters in the vertices
(nodes) of the tree.
• Boosters are placed to compensate for losses and ensure that the total loss
along any path does not exceed the given tolerance level.
• Constraints:
• Boosters can only be placed in the vertices of the tree, and not along the
edges.
• Optimization:
• The optimization problem involves finding the best locations for boosters to
minimize losses in the network.
• Let T = (V, E, w) be a weighted directed tree
• V is the set of vertices
• E is the set of edges
• w is the weight function for the edges
• wij is the weight of the edge hi, ji ∈ E
• We say that wij = ∞ if <i, j> !∈ E
• A vertex with in-degree zero is called a source vertex
• A vertex with out-degree zero is called a sink vertex
• For any path P ∈ T, its delay d(P) is defined to be the sum of the weights
(wij ) of that path, or
• Delay of the tree T, d(T) is the maximum of all path delays.

• Split node is the booster station
• Tree vertex splitting problem is to identify a set X ⊆ V of minimum
cardinality (minimum number of booster stations) for which d(T /X) ≤ δ
for some specified tolerance limit δ
• TVSP has a solution only if the maximum edge weight is ≤ δ
Greedy solution for TVSP
• We want to minimize the number of booster stations (X)
• For each node u ∈ V , compute the maximum delay d(u) from u to any
other node in its subtree
• If u has a parent v such that d(u) + w(v, u) > δ, split u and set d(u) to zero
• Computation proceeds from leaves to root
• Delay for each leaf node is zero
• The delay for each node v is computed from the delay for the set of its
children C(v)
Solve tree for δ = 5
Thank You
Recurrence Relation
By: Ashok Basnet
Recurrence Relation
• A recurrence relation (R.R., or just recurrence) for a sequence {an} is an

equation that expresses an in terms of one or more previous elements
a0,…, an−1 of the sequence, for all n≥n0.
• A particular sequence (described non-recursively) is said to solve the given
recurrence relation if it is consistent with the definition of the recurrence.
o A given recurrence relation may have many solutions.
• Consider the recurrence relation
o a = 2an−1 − an−2 (n≥2).
n
• Which of the following are solutions?

an = 3n
an = 2 n
an = 5
Recurrence Relation
• E.g.: S = {2 , 22 , 23 , ….. 2n }
S = { Sn } = { 2n }
• Here Initial Condition is S1 = 2. So Recurrence relation can be expressed as:
Sn = 2Sn-1 , n ≥ 2
• E.g.: S = {1, 1, 2, 3, 5, ….. }
o Sn = Sn-1 + Sn-2 , n ≥ 3 with S1 = S2 = 1 (This is Fibonacci Sequence)
Linear Recurrence Relation with Constant Time Coefficient
• Equation: [ C0an + C1an-1 + C2an-2 + ….…. + Ckan-k = f(n) ]

where C0 C1 ,C2 , Ck are constants.
• E.g.:
o 2an + 3an-1 = 3
o an – 7an-1 + 12an-2 = n.4n
• Order: It is the difference between the highest and lowest subscript of a.
• Degree: It is defined as the highest power of an.
• Iteration Method
• Method of characteristic roots
• Generating functions
• The method of characteristic roots with constant coefficient can solve both
o Homogeneous Recurrence Relation [ f(n) = 0 ]
o Non-homogeneous Recurrence Relation [ f(n) != 0 ]
Homogeneous Recurrence Relation
• Equation: [ C0an + C1an-1 + C2an-2 + ….…. + Ckan-k = 0 ] where C C ,C , C are

0 1 2 k
constants.
• Put an = rn , an-1 = rn-1 and so on.
• Find an equation in terms of r. This is called as characteristic equation or
auxiliary equation.
• Solve characteristic equation and find characteristic roots.
• If characteristic roots are:
o r = r1, r2, r3 (distinct), then general solution is an = b1r1n + b2r2n + b3r3n
where b1, b2, b3 are constants.
o r = r1, r1 then an = (b1 + nb2) r1n
o r = r1, r1, r2, r3 then an = (b1 + nb2)r1n + b3r2n + b4r3n
o r = r1, r1, r1, r2 then an = (b1 + nb2+ n2b3)r1n +b4r2n
Homogeneous Recurrence Relation
• Solve an = an-1 + 2an-2 , n ≥ 2 with the initial conditions a 0 = 0, a1 = 1.

• Solve an = 4(an-1 - an-2 ) , n ≥ 2 with the initial conditions a0 = a1 = 1.
• Solve an = 8an-1 - 21an-2 + 18an-3
• Solve an = -an-1 + 4an-2 + 4an-3, with the initial conditions a0 = 8, a1 = 6, a2= 26.
Case I: Non-Homogeneous Recurrence Relation with Const. Coeff.
• Equation: [ C0an + C1an-1 + C2an-2 + ….…. + Ckan-k = f(n) ] where f(n) != 0.

• General solution: an = anh + anp where h is for homogeneous solution and p is
for particular solution.
• Case 1: Equate equation to zero and find homogeneous solution
• Case 2:
o Let an = A
o Put an = an-1 = ….......... = A in the given recurrence relation
o Find A
o an(p) = A
Non-Homogeneous Recurrence Relation with Const. Coeff.
• Solve an+2 = 5an+1 - 6an + 2, with the initial conditions a0 = 1, a1 = -1.

• Solve an = 6an-1 - 8an-2 +3.
• Solve an = 5an-1 - 6an-2 + 1
Case II: Non-Homogeneous Recurrence Relation with Const. Coeff.
• Equation: [ C0an + C1an-1 + C2an-2 + ….…. + Ckan-k = f(n) ] where f(n) != 0 and
f(n) is a polynomial of degree s.
• Case 2:
o Let an = A0 + A1n + A2n2 + …... + Asns
o Put an , an-1 and so on in the given recurrence relation
o Compare the coefficients of like power on n.
o Find A0, A1, A2,…. As
o An(p) = A0 + A1n +A2n2 + …........... + Asns
• Solve yn+2 - yn+1 - 2yn = n2

• For yn(h) : yn+2 – yn+1 – 2yn = 0
• Put yn = rn . Then characteristics equation can be written as:
o r2 – r – 2 = 0
o Solving we get r = -1, 2
o yn(h) = b1 (-1)n + b2 (2)n
To find yn(p):
put yn = A0 + A1n + A2n2
{A0 + A1(n+2) + A2(n+2)2 } - { A0 + A1(n+1) + A2(n+1)2 } - 2{A0 + A1n
+ A2n2 } = n2
• To find yn(p):
put yn = A0 + A1n + A2n2
{A0 + A1(n+2) + A2(n+2)2 } - { A0 + A1(n+1) + A2(n+1)2 } - 2{A0 + A1n
+ A2n2 } = n2
{ A1 – 2 A0 + 3A2} + {2A2 – 2A1}n + {-2A2}n2 = n2
Comparing coefficients,
A1 – 2A0 + 3A2 = 0
2A2 - 2A1 = 0
-2A2 = 1
Solving A0 = -1, A1 = -½ and A2 = -1/2
• Solve an+2 + 2an+1 - 15an = 6n + 10, with the initial conditions a0 = 1, a1 = -1/2.
• Solve an+2 - 5an+1 + 6an = n2
• Solve an - 2an-1 = 6n, with a1 = 2
Case III: Non-Homogeneous Recurrence Relation with Const. Coeff.
• Equation: [ C0an + C1an-1 + C2an-2 + ….…. + Ckan-k = f(n) ] where f(n) != 0 and
f(n) = βnP(n) where β is not a characteristics root and P(n) is a polynomial.
• Case 2:
o Let an = βn (A0 + A1n + A2n2 + …... + Asns )
• an(p) =βn (A0 + A1n + A2n2 + …... + Asns )
• Solve an - 7an-1 + 12an-2 = 2n,

• Solve an - 7an-1 + 12an-2 = n.2n ,
Case IV: Non-Homogeneous Recurrence Relation with Const. Coeff.
• Equation: [ C0an + C1an-1 + C2an-2 + ….…. + Ckan-k = f(n) ] where f(n) != 0 and f(n)
= βnP(n) where β is characteristics root of multiplicity t and P(n) is a polynomial.
• General solution: an = anh + anp where h is for homogeneous solution and p is for
particular solution.
• Case 2:
o Let an = ntβn (A0 + A1n + A2n2 + …... + Asns )
• an(p) = ntβn (A0 + A1n + A2n2 + …... + Asns )
• Solve an - 7an-1 + 12an-2 = 4n,

• Solve an - 7an-1 + 12an-2 = n.4n ,
Solving Recurrences
• Establishing a recurrence relation from a program involves identifying the relationship

between different instances of the problem size and how the solution to one instance
relates to the solution of a smaller instance.
• Let's go through an example to illustrate this process: Consider a simple recursive
function for calculating the n-th Fibonacci number.
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
Steps to Establish the Recurrence Relation
• Identify the base cases: Determine the simplest cases where the function does not
call itself.
if n <= 1:
return n
• This means F(0) = 0 and F(1) = 1
• Identify the recursive case(s): Look at the part of the function where it calls itself
with smaller inputs.
else:
return fibonacci (n-1) + fibonacci (n-2)
• This translates to the recurrence relation: F(n) = F(n-1) + F(n-2) for n > 1
• Combine the base case and the recursive case to form the complete recurrence
relation.
Complete Recurrence Relation for Fibonacci
• Combining the above steps, the recurrence relation for the Fibonacci sequence is:
𝐹(𝑛)=⎧ 0 if 𝑛 = 0
⎨ 1 if 𝑛 = 1
⎩ 𝐹(𝑛−1) + 𝐹(𝑛−2) if 𝑛 > 1
Another Example: Factorial
• Consider a recursive function to calculate the factorial of n:

def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
• Steps to Establish the recurrence relation for factorial

o Base Case
if n == 0:
return 1
This means F(0) = 1
Another Example: Factorial
• Recursive case:
else:
return n * factorial(n-1)
This translates to F(n) = n . F(n-1) for n > 0

o Base Case:
if n == 0:
return 1
This means F(0) = 1
Complete Recurrence Relation for Factorial
• Combining the above steps, the recurrence relation for the Factorial is:
𝐹(𝑛) =⎧ 1 if 𝑛 = 0
⎩ n . 𝐹(𝑛−1) if 𝑛 > 0
Example: Binary Search
• Consider a recursive function to calculate the factorial of n:

def binary_search(arr, target, low, high):
if low > high:
return -1
return mid
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1)
else:
return binary_search(arr, target, mid + 1, high)
Example: Binary Search

• Define the problem size: The size of the problem is the range [low, high]
• Base Case:
if low > high:
return -1
This means T(0) = constant time = O(1)
• Recursive case: elif and else in above program. Since Each recursive call reduces the
problem size by half and there are other constant time factor involved, we have
• T(n) = T(n/2) + O(1)
• Complete Recurrence Relation:
𝐹(𝑛) =⎧ O(1) if 𝑛 = 0
⎩ T(n/2) + O(1) if 𝑛 > 0
Solution Recurrence Relation for:
• Merge Sort
• Tower of Hanoi
• Quick Sort
•
Find Recurrence Relation for:
• Merge Sort
𝐹(𝑛) =⎧ O(1) if 𝑛 ≤ 1
⎩ 2T(n/2) + O(1) if 𝑛 > 1
• Tower of Hanoi
𝐹(𝑛) =⎧ O(1) if 𝑛 = 1
⎩ 2T(n - 1) + O(1) if 𝑛 > 1
• Quick Sort
𝐹(𝑛) =⎧ O(1) if 𝑛 ≤ 1
⎩ 2T(n/2) + O(n) if 𝑛 > 1
•
General Steps to Derive Recurrence Relations
1. Define the problem size: Determine what 𝑛 represents (e.g., the size of the input).
2. Identify base case(s): Find the simplest cases where the function terminates
without recursion.
3. Identify recursive case(s): Determine how the function reduces the problem size
and combines the results of smaller subproblems.
4. Formulate the recurrence: Write the mathematical expression that represents the
function's behavior in terms of smaller problem sizes.
Methods to Solve Recurrence Relations
1. Substitution Method or Backward Substitution Method

2. Recursion Tree Method
3. Master Method
Substitution Method
𝐹(𝑛) =⎧ 1 otherwise
⎩ 3T(n - 1) if 𝑛 > 0
• Solution
T(n) = 3T(n-1) ------------------- (1)
Put, n -> n-1
T(n-1) = 3T(n-2)
Put, n -> n-2
T(n-2) = 3T(n-3)
Substitute,
T(n) = 3T(n-1) = 3 { 3T(n-2) } = 32T(n-2) = 32{3T(n-3)} = 33T(n-3) … = 3kT(n-k)
Assume, n - k = 0, then k = n. So, T(n) = 3kT(n-k) = 3nT(0) = 3n
Complexity, T(n) = O(3n)
Substitution Method
𝐹(𝑛) =⎧ 1 otherwise
⎩ 2T(n - 1) - 1 if 𝑛 > 0
T(n) = 2T(n-1) - 1 ------------------- (1)
Put, n -> n-1
T(n-1) = 2T(n-2) - 1
Put, n -> n-2
T(n-2) = 2T(n-3) - 1
Substitute,
T(n) = 2T(n-1) -1 = 2 { 2T(n-2) -1 } -1 = 22T(n-2) -2 -1
= 22{2T(n-3) - 1} -2 –1 = 23T(n-3) - 22 – 2 –1
= 2KT(n-k) - 2k-1 – 2k-2 …... - 22 – 2 - 1
Assume, n - k = 0, then k = n. So, T(n) = 2nT(0) - 2n-1 – 2n-2 ….. -22 - 2 -1= 2n – 2n-1... -2 -20
= 2n - (20 + 21 + …... + 2n-2 + 2n-1) = 1 So, Complexity, T(n) = O(1)
Substitution Method
𝐹(𝑛) =⎧ 1 if n =1
⎩ T(n - 1) + n if 𝑛 > 1
Complexity, T(n) = O(n2)
Tree Method
𝐹(𝑛) =⎧ 1 if n =1
⎩ 2T(n / 2) + n if 𝑛 > 1
Complexity, T(n) = O(n2)
Master Method
T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed to have the
same size.
f(n) = cost of the work done outside the recursive call, which includes the cost
of dividing the problem and cost of merging the solutions
Here, a ≥ 1 and b > 1 are constants, and f(n) is an asymptotically positive function.
Master Theorem Method
Master Method
• If the cost of solving the sub-problems at each level increases by a certain factor, the
value of f(n) will become polynomially smaller than nlogb a. Thus, the time complexity
is oppressed by the cost of the last level ie. nlogb a
• If the cost of solving the sub-problem at each level is nearly equal, then the value of
f(n) will be nlogb a. Thus, the time complexity will be f(n) times the total number of
levels ie. nlogb a * log n
• If the cost of solving the subproblems at each level decreases by a certain factor, the
value of f(n) will become polynomially larger than nlogb a. Thus, the time complexity is
oppressed by the cost of f(n).
T(n) = 3T(n/2) + n 2
Here,
a=3
n/b = n/2
f(n) = n2
logb a = log2 3 ≈ 1.58 < 2
ie. f(n) < nlogb a+ϵ , where, ϵ is a constant.
Case 3 implies here if a f(n/b) ≤ cf(n) and c ≤ 1.
3 (n2 / 4) ≤ c n2
Hence, 3/ 4 ≤ 1. Case 3 applies.
Thus, T(n) = f(n) = Θ(n 2)
Thank you
Dynamic Programming
By: Ashok Basnet
Course Outline
• Dynamic Programming
• Multistage Graphs
• All Pair Shortest Paths
• Single Source Shortest Path: General Weights
• Optimal Binary Search Trees
• String Editing Problem
• 0/1-Knapsack Problem
• Reliability Design
• TSP
Dynamic Programming
• Dynamic programming is a name, coined by Richard Bellman in 1955.
• Dynamic programming, as greedy method, is a powerful algorithm design
technique that can be used when the solution to the problem may be
viewed as the result of a sequence of decisions.
• In the greedy method we make irrevocable decisions one at a time, using a
greedy criterion.
• However, in dynamic programming we examine the decision sequence to
see whether an optimal decision sequence contains optimal decision
subsequence.
• When optimal decision sequences contain optimal decision subsequences,
we can establish recurrence equations, called dynamic-programming
recurrence equations, that enable us to solve the problem in an efficient
way.
Dynamic Programming
• Dynamic programming is based on the principle of optimality.
• The principle of optimality states that no matter whatever the initial
state and initial decision are, the remaining decision sequence must
constitute an optimal decision sequence with regard to the state resulting
from the first decision.
• The principle implies that an optimal decision sequence is comprised of
optimal decision subsequences.
• Since the principle of optimality may not hold for some formulations of
some problems, it is necessary to verify that it does hold for the problem
being solved.
• Dynamic programming cannot be applied when this principle does not hold.
Dynamic Programming
• The steps in a dynamic programming solution are:
• Verify that the principle of optimality holds
• Set up the dynamic-programming recurrence equations
• Solve the dynamic-programming recurrence equations for the value
of the optimal solution.
• Perform a trace back step in which the solution itself is constructed.
• Dynamic programming differs from the greedy method since the greedy
method produces only one feasible solution, which may or may not be
optimal, while dynamic programming produces all possible sub-problems
at most once, one of which guaranteed to be optimal.
• Optimal solutions to sub-problems are retained in a table, thereby
avoiding the work of recomputing the answer every time a sub-problem
is encountered.
Dynamic Programming
• The divide and conquer principle solve a large problem, by breaking it up
into smaller problems which can be solved independently.
• In dynamic programming this principle is carried to an extreme: when we
don't know exactly which smaller problems to solve, we simply solve
them all, then store the answers away in a table to be used later in
solving larger problems.
• Care is to be taken to avoid recomputing previously computed values,
otherwise the recursive program will have prohibitive complexity.
• In some cases, the solution can be improved and in other cases, the
dynamic programming technique is the best approach.
Dynamic Programming
Two difficulties may arise in any application of dynamic programming:
• It may not always be possible to combine the solutions of smaller
problems to form the solution of a larger one.
• The number of small problems to solve may be un-acceptably large.
• There is no characterized precisely which problems can be effectively
solved with dynamic programming; there are many hard problems for
which it does not seen to be applicable, as well as many easy problems
for which it is less efficient than standard algorithms.
Multi Stage Graphs
• A multistage graph G = (V, E) is a directed graph in which the vertices are
partitioned into k ≥ 2 disjoint sets Vi , 1 ≤ i ≤ k. In addition, if <u, v> is an
edge in E, then u ∈ Vi and v ∈ Vi+1 for some i, 1 ≤ i ≤ k.
• Let the vertex ‘s’ is the source, and ‘t’ the sink. Let c (i, j) be the cost of
edge <i, j>.
• The cost of a path from ‘s’ to ‘t’ is the sum of the costs of the edges on the
path.
• The multistage graph problem is to find a minimum cost path from ‘s’ to ‘t’.
• Each set Vi defines a stage in the graph. Because of the constraints on E,
every path from ‘s’ to ‘t’ starts in stage 1, goes to stage 2, then to stage 3,
then to stage 4, and so on, and eventually terminates in stage k.
Multi Stage Graphs
• A dynamic programming formulation for a k-stage graph problem is
obtained by first noticing that every s to t path is the result of a sequence
of k – 2 decisions.
• Let c (i, j) be the cost of the path from source to destination and cost(i, j)
= cost(stage, vertex). Then using the forward approach, we obtain:
Multi Stage Graphs
Multi Stage Graphs
• Cost can be represented as: cost(stage_number, vertext_number)
V 1 2 3 4 5 6 7 8 9 10 11 12
cost
d
Multi Stage Graphs
• For fifth stage
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 0
d 12
• Cost(5, 12) = 0
Multi Stage Graphs
• for fourth stage
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 4 2 5 0
d 12 12 12 12
• Cost(4, 9) = 4
• Cost(4, 10) = 2
• Cost(4, 11) = 5
Multi Stage Graphs
• for third stage
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 7 4 2 5 0
d 10 12 12 12 12
• Cost(3, 6) = min{ c(6,9) + cost(4, 9), c(6, 10) + cost(4, 10) }

= min { 6+4, 5+2 } = 7
Multi Stage Graphs
• for third stage
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 7 5 4 2 5 0
d 10 10 12 12 12 12

= min { 6+4, 5+2 } = 7
• Cost(3, 7) = min{ c(7,9) + cost(4, 9) , c(7, 10) + cost(4, 10) }
= min{ 4 + 4, 3 + 2 } = 5
Multi Stage Graphs
• for third stage
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 7 5 7 4 2 5 0
d 10 10 10 12 12 12 12

= min { 6+4, 5+2 } = 7
• Cost(3, 7) = min{ c(7,9) + cost(4, 9) , c(7, 10) + cost(4, 10) }
= min{ 4 + 4, 3 + 2 } = 5
• Cost(3, 8) = min { c(8, 10) + cost ( 4, 10) , c(8, 11) + cost(4, 11)
= min { 5+2, 6+5 } = 7
Multi Stage Graphs
• For second stage
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 7 7 5 7 4 2 5 0
d 7 10 10 10 12 12 12 12
• Cost(2, 2) = min{ c(2, 6) + cost (3, 6), c(2, 7) + cost(3, 7), c(2, 8) + cost(3, 8) }
= { 4+7, 2+5, 1+7 } = 7
Multi Stage Graphs
• for second stage
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 7 9 7 5 7 4 2 5 0
d 7 6 10 10 10 12 12 12 12
= { 4+7, 2+5, 1+7 } = 7
• Cost(2, 3) = min{ c(3, 6) + cost (3, 6), c(3, 7) + cost(3, 7) }
= { 2+7, 7+5 } = 9
Multi Stage Graphs
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 7 9 18 7 5 7 4 2 5 0
d 7 6 8 10 10 10 12 12 12 12
= { 4+7, 2+5, 1+7 } = 7
= { 2+7, 7+5 } = 9
• Cost(2, 4) = min{ c(4, 8) + cost (3, 8) }
= { 11+7 } = 18
Multi Stage Graphs
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 7 9 18 15 7 5 7 4 2 5 0
d 7 6 8 8 10 10 10 12 12 12 12
= { 4+7, 2+5, 1+7 } = 7
= { 2+7, 7+5 } = 9
• Cost(2, 4) = min{ c(4, 8) + cost (3, 8) }
= { 11+7 } = 18
= { 11+5, 8+7 } = 15
Multi Stage Graphs
• for first stage
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 16 7 9 18 15 7 5 7 4 2 5 0
d 2 or 7 6 8 8 10 10 10 12 12 12 12
3
• Cost(1, 1) = min{ c(1,2) + cost(2, 2), c(1, 3) + cost(2, 3), c(1, 4) + cost(2, 4), c(1, 5) +
cost(2, 5) }
= min{ 9+7, 7+9, 3+18, 2+15 } = min(16, 16, 21, 17)
Multi Stage Graphs
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 16 7 9 18 15 7 5 7 4 2 5 0
d 2 or 7 6 8 8 10 10 10 12 12 12 12
3
• We have complete data. Now we can implement the dynamic programming to make
decision.
• For forward approach, we will move from source to sink.
• d(stage, vertex) = d(1, 1) = 2
• d(2, 2) = 7
• d(3, 7) = 10
• d(4, 10) = 12
• Path = 1, 2, 7, 10, 12
Multi Stage Graphs
V 1 2 3 4 5 6 7 8 9 10 11 12
cost 16 7 9 18 15 7 5 7 4 2 5 0
d 2 or 7 6 8 8 10 10 10 12 12 12 12
• We have3 complete data. Now we can implement the dynamic programming to make
decision.
• For forward approach, we will move from source to sink.
• d(stage, vertex) = d(1, 1) = 3
• d(2, 3) = 6
• d(3, 6) = 10
• d(4, 10) = 12
• Path = 1, 3, 6, 10, 12
Multi Stage Graphs
• Algorithm for Multistage Graph (Shortest Path):
• Initialization:
• Create a table to store the optimal costs for each node in each stage.
• Initialize the last stage's costs as the weights of the corresponding nodes.
• Bottom-Up Computation:
• Starting from the penultimate stage and moving backward, compute the optimal costs for each
node in each stage based on the optimal costs of the next stage.
• Use the following recurrence relation for each node in a stage i:
cost[i] = min(weight(i, j) + cost[j]) for all j in the next stage
Here, weight(i, j) represents the weight of the edge from node i to node j.
• Traceback:
• After completing the bottom-up computation, the optimal cost of the starting node is obtained.
• Trace back through the computed costs to reconstruct the optimal path.
• Optimal Solution:
• The optimal solution is the path from the starting node to the ending node with the minimum
total cost.
All pairs shortest paths
All pairs shortest paths (Floyd-Warshall)
• In the all pairs shortest path problem, we are to find a shortest path
between every pair of vertices in a directed graph G.
• That is, for every pair of vertices (i, j), we are to find a shortest path
from i to j as well as one from j to i.
• These two paths are the same when G is undirected.
• The all pairs shortest path problem is to determine a matrix A such that
A (i, j) is the length of a shortest path from i to j.
• The matrix A can be obtained by solving n single-source problems using
the algorithm shortest Paths.
• The shortest i to j path in G, i ≠ j originates at vertex i and goes through
some intermediate vertices (possibly none) and terminates at vertex j.
• If k is an intermediate vertex on this shortest path, then the sub paths from
i to k and from k to j must be shortest paths from i to k and k to j,
respectively.
• Otherwise, the i to j path is not of minimum length. So, the principle of
optimality holds.
• Let Ak (i, j) represent the length of a shortest path from i to j going through
no vertex of index greater than k, we obtain:
All pairs
shortest paths
Single Source Shortest Path: General Weights (Bellman Ford
Algorithm)
• The Single-Source Shortest Path (SSSP) algorithm is used to find the shortest paths from
a single source vertex to all other vertices in a weighted graph.
• There are several algorithms to solve this problem, and two of the most commonly used
ones are Dijkstra's algorithm and Bellman-Ford algorithm.
• Given a graph and a source vertex src in the graph, find the shortest paths from src to all
vertices in the given graph. The graph may contain negative weight edges.
• Dijkstra doesn’t work for Graphs with negative weights, Bellman-Ford works for such
graphs.
• Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems.
• Initialization:
• Create an array dist[] to store the shortest distances from the source to each vertex.
• Initialize dist[] with infinity for all vertices except the source, and set dist[source] to 0.
• Relaxation Loop:
• Iterate |V| - 1 times, where |V| is the number of vertices.
• For each edge (u, v) in the graph, check if the distance from the source to v can be
shortened by going through u.
• If dist[u] + weight(u, v) < dist[v], update dist[v] with the new, shorter
distance.
• Negative Cycle Check:
• After the relaxation loop, check for the presence of negative cycles.
• If there is a vertex v such that dist[u] + weight(u, v) < dist[v], then the graph
contains a negative cycle.
• Result:
• The final distances in the dist[] array represent the shortest paths from the source to all
other vertices, or the presence of a negative cycle is detected.
function BellmanFord(graph, source):
create an array dist[] to store the shortest distances
initialize dist[] with infinity for all vertices except the source
set distance[source] to 0
for i from 1 to |V| - 1:
for each edge (u, v) in graph:
alt = dist[u] + weight(u, v)
if alt < dist[v]:
dist[v] = alt
for each edge (u, v) in graph:
if dist[u] + weight(u, v) < dist[v]:
raise Error("Graph contains a negative cycle")
return dist
Problem
1
Problem 2
• Let the given source

vertex be 1. Initialize all
distances as infinite,
except the distance to
the source itself. Total
number of vertices in
the graph is 7, so all
edges must be
processed 6 times.
Problem 3
Problem
4
0/1 - Knapsack
Problem
0/1 - Knapsack Problem
• Knapsack Problem algorithm is a very helpful problem in combinatorics. In the
supermarket there are n packages (n ≤ 100) the package i has weight W[i] ≤ 100 and
value V[i] ≤ 100. A thief breaks into the supermarket, the thief cannot carry weight
exceeding M (M ≤ 10).
• The problem to be solved here is: which packages the thief will take away to get the
highest value?
• Input
o Maximum weight M and the number of packages n.
o Array of weight W[i] and corresponding value V[i].
• Output:
o Maximize value and corresponding weight in capacity.
o Which packages the thief will take away.
• The 0/1 Knapsack problem using dynamic programming. In this Knapsack algorithm
type, each package can be taken or not taken. Besides, the thief cannot take a
fractional amount of a taken package or take a package more than once. This type
can be solved by Dynamic Programming Approach.
• The basic idea of Knapsack dynamic programming is to use a table to store the
solutions of solved subproblems.
• When analyzing 0/1 Knapsack problem using Dynamic programming, you can find
some noticeable points.
• The value of the knapsack algorithm depends on two factors:
o How many packages are being considered?
o The remaining weight which the knapsack can store?
• Therefore, you have two variable quantities. With dynamic programming, you have
useful information:
o the objective function will depend on two variable quantities
o the table of options will be a 2-dimensional table.
• If calling B[i][j] is the maximum possible value by selecting in packages {1, 2, …, i} with
weight limit j.
• The maximum value when selected in n packages with the weight limit M is B[n][M].
In other words: When there are i packages to choose, B[i][j] is the optimal weight
when the maximum weight of the knapsack is j.
• The optimal weight is always less than or equal to the maximum weight: B[i][j] ≤ j.
• For example: B[4][10] = 8. It means that in the optimal case, the total weight of the
selected packages is 8, when there are 4 first packages to choose from (1st to 4th
package) and the maximum weight of the knapsack is 10. It is not necessary that all 4
items are selected.
• W[i], V[i] are in turn the weight and value of package i, in which i ∈ {1, …, n}.
• M is the maximum weight that the knapsack can carry.
• If ( j < wt[ i ] ) :
B[i][j] = B[i – 1][j]
• Else :
B[i][j]= max(V[i]+B[i – 1][j – W[i]], B[i – 1][j])
• Let's say we have 4 items and a knapsack of capacity 7.
Weight 1 3 4 5
Value 1 4 5 7
• Hence, m = 7
Weight 1 3 4 5
Value 1 4 5 7
V Wt. 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0 0
1 1 0
4 3 0
5 4 0
7 5 0
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1
4 3 2 0
5 4 3 0
7 5 4 0
Here, B[i][j]= max(V[i]+B[i – 1][j – W[i]], B[i – 1][j])

B[1][1] = max(1+B[0][0], B[0][1])
B[1][1] = max(1, 0) = 1
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0
5 4 3 0
7 5 4 0
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0 1 1
5 4 3 0
7 5 4 0
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0 1 1
5 4 3 0
7 5 4 0

B[2][3] = max(4+B[1][0], B[1][3])
B[2][3] = max(4+0, 1) = 4
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0 1 1 4
5 4 3 0
7 5 4 0

B[2][3] = max(4+B[1][0], B[1][3])
B[2][3] = max(4+0, 1) = 4
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0 1 1 4 5
5 4 3 0
7 5 4 0

B[2][4] = max(4+B[1][1], B[1][4])
B[2][3] = max(4+1, 1) = 5
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0 1 1 4 5 5 5 5
5 4 3 0
7 5 4 0
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0 1 1 4 5 5 5 5
5 4 3 0 1 1 4 5
7 5 4 0

B[4][4] = max(5+B[2][0], B[2][4])
B[2][3] = max(5+0, 4) = 5
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0 1 1 4 4 4 4 4
5 4 3 0 1 1 4 5 6 6 9
7 5 4 0 1 1 4 5 7 8 9
V Wt. j=0 1 2 3 4 5 6 7
0 0 i=0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 1 1
4 3 2 0 1 1 4 4 4 4 4
5 4 3 0 1 1 4 5 6 6 9
7 5 4 0 1 1 4 5 7 8 9
▪ 9 is the highest value we can get.

▪ It's coming from 3rd row to 4th row.
▪ So, we select the 3rd row with weight 4 and value 5.
▪ Now, the weight of 4kg is full, so we take 2nd row and 3rd column. It
has value of 4 and coming from same row.
▪ So, we take second column with weight 3 and value 4.
• Let's say we have 4 items and a knapsack of capacity 8.
Weight 2 3 4 5
Value 1 2 5 6
• Solve given problem.

Weight 2 3 4 5
Value 1 2 5 6
Value Wt J=0 1 2 3 4 5 6 7 8
0 0 i=0 0 0 0 0 0 0 0 0 0
1 2 1 0 0 1 1 1 1 1 1 1
2 3 2 0 0 1 2 2 3 3 3 3
5 4 3 0 0 1 2 5 5 6 7 7
6 5 4 0 0 1 2 5 6 6 7 8
String Editing Problem
• The String Editing Problem, also known as the Edit Distance or Levenshtein Distance
problem, involves determining the minimum number of operations required to
transform one string into another.
• The allowed operations typically include insertion, deletion, and substitution of
characters.
• The goal is to find the minimum cost or number of operations needed to make the two
strings identical.
• Example:
o Convert azced to abcdef
o Let's create a matrix to solve the String Editing Problem (Edit Distance problem)
using dynamic programming.
Null a b c d e f
Null 0 1 2 3 4 5 6
a 1
z 2
c 3
e 4
d 5
Null a b c d e f
Null 0 1 2 3 4 5 6
a 1 0 1 2 3 4 5
z 2 1 1 2 3 4 5
c 3 2 2 1 2 3 4
e 4 3 3 2 2 2 3
d 5 4 4 3 2 3 3
Null a b c d e f
Null 0 1 2 3 4 5 6
a 1 0 1 2 3 4 5
z 2 1 1 2 3 4 5
c 3 2 2 1 2 3 4
e 4 3 3 2 2 2 3
d 5 4 4 3 2 3 3
Reliability Design
• The problem is to design a system that is composed of several devices
connected in series.
• Let ri be the reliability of device Di (that is ri is the probability that device i
will function properly) then the reliability of the entire system is π ri.
• Even if the individual devices are very reliable, the reliability of the system
may not be very good.
• For example, if n=10 and ri = 0.99, 1 ≤ i ≤ 10, then π ri = 0.904.
• Hence, it is desirable to duplicate devices. Multiple copies of the same
device type are connected in parallel.
Reliability Design
• An optimal solution m1, m2 …........ mn is the result of a sequence of

decisions, one decision for each mi.
• The dominance rule (f1, x1) dominate (f2, x2) if f1 ≥ f2 and x1 ≤ x2.
Hence, dominated tuples can be discarded from Si
Di Ci ri ui
D1 30 0.9 2
D2 15 0.8 3
D3 20 0.5 3
TSP
Optimal Binary Search Tree
• As we know that in binary search tree, the nodes in the left subtree have lesser
value than the root node and the nodes in the right subtree have greater value
than the root node.
• We know the key values of each node in the tree, and we also know the
frequencies of each node in terms of searching means how much time is required
to search a node.
• The frequency and key-value determine the overall cost of searching a node. The
cost of searching is a very important factor in various applications.
• The overall cost of searching a node should be less. The time required to search a
node in BST is more than the balanced binary search tree as a balanced binary
search tree contains a lesser number of levels than the BST.
• There is one way that can reduce the cost of a binary search tree is known as an
optimal binary search tree.
Optimal Binary
Search Tree
Optimal Binary Search Tree
• In the above tree, all the nodes on the left subtree are smaller
than the value of the root node, and all the nodes on the right
subtree are larger than the value of the root node.
• The maximum time required to search a node is equal to the
minimum height of the tree, equal to log(n).
• Now we will see how many binary search trees can be made
from the given number of keys.
• For example: 10, 20, 30 are the keys, and the following are the
binary search trees that can be made out from these keys.
• When we use the above formula, then it is
found that total 5 number of trees can be
created.
• The cost required for searching an element
depends on the comparisons to be made to
search an element. Now, we will calculate the
average cost of time of the above binary search
trees.
• Till now, we read about the height-balanced binary search tree.
• To find the optimal binary search tree, we will determine the frequency of
searching a key.
• Let's assume that frequencies associated with the keys 10, 20, 30 are 3, 2,
5.
Keys 10 20 30

Frequency 3 2 5
• The above trees have different frequencies. The tree with the
lowest frequency would be considered the optimal binary search tree. The
tree with the frequency 17 is the lowest, so it would be considered as
the optimal binary search tree.
Dynamic Approach Optimal Binary Search Trees
General formula for calculating the minimum cost

is:
C[i,j] = min (I<k<=j){c[i, k-1] + c[k,j]} + w(i,j)
• First, we will calculate the values where j-i is equal to zero.
• When i=0, j=0, then j-i = 0
• When i = 1, j=1, then j-i = 0
• When i = 2, j=2, then j-i = 0
• When i = 3, j=3, then j-i = 0
• When i = 4, j=4, then j-i = 0
• Therefore, c[0, 0] = 0, c[1 , 1] = 0, c[2,2] = 0, c[3,3] = 0, c[4,4] = 0
• Now we will calculate the values where j-i equal to 1.
• When j=1, i=0 then j-i = 1
• Now to calculate the cost, we will consider only
the jth value.
• The cost of c[0,1] is 4 (The key is 10, and the cost
corresponding to key 10 is 4).
corresponding to key 20 is 2).
corresponding to key 30 is 6)
corresponding to key 40 is 3)
• Now we will calculate the values where j-i = 2
• In this case, we will consider two keys.
• When i=0 and j=2, then keys 10 and 20. There are two possible trees that
can be made out from these two keys shown below:
• In the first binary tree, cost
would be: 4*1 + 2*2 = 8
• In the second binary tree, cost
would be: 4*2 + 2*1 = 10
• The minimum cost is 8;
therefore, c[0,2] = 8
• When i=1 and j=3, then keys 20 and 30. There are two possible trees that
can be made out from these two keys shown below:
• In the first binary tree, cost would be: 1*2 + 2*6 = 14
• In the second binary tree, cost would be: 1*6 + 2*2 = 10
• The minimum cost is 10; therefore, c[1,3] = 10
• When i=2 and j=4, we will consider the keys at 3 and 4, i.e., 30 and 40.
There are two possible trees that can be made out from these two keys
shown as below:
• In the first binary tree, cost would be: 1*6 + 2*3 = 12
• In the second binary tree, cost would be: 1*3 + 2*6 = 15
• The minimum cost is 12, therefore, c[2,4] = 12
• Now we will calculate the values when j-i = 3
• When i=0, j=3 then we will consider three keys, i.e., 10,
20, and 30.
• The following are the trees that can be made if 10 is
considered as a root node.
• In the above tree, 10 is the root node, 20 is the right child
of node 10, and 30 is the right child of node 20.
• Cost would be: 1*4 + 2*2 + 3*6 = 26
of node 10, and 20 is the left child of node 20.
• Cost would be: 1*4 + 2*6 + 3*2 = 22
• Cost would be: 1*2 + 4*2 + 6*2 = 22
• In the above tree, 30 is the root node, 20 is the left child
• Cost would be: 1*6 + 2*2 + 3*4 = 22
• In the above tree, 30 is the root node, 10 is the left child of
node 30 and 20 is the right child of node 10.
• Cost would be: 1*6 + 2*4 + 3*2 = 20
• Therefore, the minimum cost is 20 which is the 3rd root. So,
c[0,3] is equal to 20.
• When i=1 and j=4 then we will consider the keys 20, 30, 40
• c[1,4] = min{ c[1,1] + c[2,4], c[1,2] + c[3,4], c[1,3] + c[4,4] } + 11
= min{0+12, 2+3, 10+0}+ 11
= min{12, 5, 10} + 11
• The minimum value is 5; therefore, c[1,4] = 5+11 = 16
• Now we will calculate the values when j-i = 4
• When j=4 and i=0 then j-i = 4
• In this case, we will consider four keys, i.e., 10, 20, 30 and 40. The
frequencies of 10, 20, 30 and 40 are 4, 2, 6 and 3 respectively.
• w[0, 4] = 4 + 2 + 6 + 3 = 15
• If we consider 10 as the root node then
C[0, 4] = min {c[0,0] + c[1,4]}+ w[0,4] = min {0 + 16} + 15= 31
• If we consider 20 as the root node then
C[0,4] = min{c[0,1] + c[2,4]} + w[0,4] = min{4 + 12} + 15 = 16 + 15 = 31
• If we consider 30 as the root node then,
C[0,4] = min{c[0,2] + c[3,4]} +w[0,4] = min {8 + 3} + 15 = 26
• If we consider 40 as the root node then,
C[0,4] = min{c[0,3] + c[4,4]} + w[0,4] = min{20 + 0} + 15 = 35
Graph Traversal and Search
Techniques
By: Ashok Basnet
Lecture Outline
• Graphs
• Binary Tree Traversal Technique and Search
• Graph Traversal Technique and Search: BFS and DFS
• Connected Components and Spanning Trees
• Bi-connected Components and DFS
Binary Tree Traversal Technique
• Search means finding a path or traversal between a start node and one of a set of goal
nodes.
• Search is a study of states and their transitions. Search involves visiting nodes in a
graph in a systematic manner, and may or may not result into a visit to all nodes.
• When the search necessarily involved the examination of every vertex in the tree, it is
called the traversal.
• There are three common ways to traverse a binary tree:
• Preorder
• Inorder
• postorder
• In all the three traversal methods, the left subtree of a node is traversed before the right
subtree.
• The difference among the three orders comes from the difference in the time at which a
node is visited.
• Inorder Traversal:
• In the case of inorder traversal, the root of each subtree is visited after its left subtree
has been traversed but before the traversal of its right subtree begins. The steps
for traversing a binary tree in inorder traversal are:
• Visit the left subtree, using inorder.
• Visit the root.
• Visit the right subtree, using inorder.
• Preorder Traversal:
• In a preorder traversal, each node is visited before its left and right subtrees
are traversed. Preorder search is also called backtracking. The steps for traversing
a binary tree in preorder traversal are:
• Visit the root.
• Visit the left subtree, using preorder.
• Visit the right subtree, using preorder.
• Postorder Traversal:
• In a postorder traversal, each root is visited after its left and right subtrees have
been traversed. The steps for traversing a binary tree in postorder traversal are:
• Visit the left subtree, using postorder.
• Visit the right subtree, using postorder
• Visit the root.
BFS and DFS
• Given a graph G = (V, E) and a vertex V in V (G) traversing can be done in two ways.
• Depth first search
• Breadth first search
Depth First
Search
• With depth first search, the start
state is chosen to begin, then some
successor of the start state, then
some successor of that state, then
some successor of that and so
on, trying to reach a goal state.
• If depth first search reaches a state S
without successors, or if all the
successors of a state S have been
chosen (visited) and a goal state has
not get been found, then it “backs
up” that means it goes to the
immediately previous state or
predecessor formally, the state
whose successor was ‘S’ originally.
Depth First Search
• For example consider the figure. The circled letters are state and arrows are branches.
• Suppose S is the start and G is the only goal state. Depth first search will first visit S, then
A then D. But D has no successors, so we must back up to A and try its second successor,
E. But this doesn’t have any successors either, so we back up to A again.
• But now we have tried all the successors of A and haven’t found the goal state G so we
must back to ‘S’.
• Now ‘S’ has a second successor, B. But B has no successors, so we back up to S again and
choose its third successor, C.
• C has one successor, F. The first successor of F is H, and the first of H is J. J doesn’t have
any successors, so we back up to H and try its second successor. And that’s G, the only
goal state. So the solution path to the goal is S, C, F, H and G and the states considered
were in order S, A, D, E, B, C, F, H, J, G.
Depth First Search
Disadvantages:
▪ It works very fine when search graphs are trees or lattices, but can get struck in an
infinite loop on graphs. This is because depth first search can travel around a cycle in the
graph forever. To eliminate this keep a list of states previously visited, and never permit
search to return to any of them.
▪ One more problem is that, the state space tree may be of infinite depth, to prevent
consideration of paths that are too long, a maximum is often placed on the depth of
nodes to be expanded, and any node at that depth is treated as if it had no successors.
▪ We cannot come up with shortest solution to the problem.
Breadth First Search
• Given an graph G = (V, E), breadth-first search starts at some source vertex S and
“discovers" which vertices are reachable from S. Define the distance between a
vertex V and S to be the minimum number of edges on a path from S to V.
• Breadth-first search discovers vertices in increasing order of distance, and hence
can be used as an algorithm for computing shortest paths (where the length of a
path = number of edges on the path).
• Breadth-first search is named because it visits vertices across the entire breadth.
• Breadth first search does not have the danger of infinite loops as we consider
states in order of increasing number of branches (level) from the start state.
• To illustrate this let us consider the following tree:
Breadth First
Search
• Breadth first search finds states level
by level. Here we first check all the
immediate successors of the start
state. Then all the immediate
successors of these, then all the
immediate successors of these, and so
on until we find a goal node. Suppose
S is the start state and G is the goal
state. In the figure, start state S is at
level 0; A, B and C are at level 1; D, e
and F at level 2; H and I at level 3; and
J, G and K at level 4. So breadth first
search, will consider in order S, A, B, C,
D, E, F, H, I, J and G and then stop
because it has reached the goal node.
Depth First and Breadth Spanning Trees
• BFS and DFS impose a tree (the BFS/DFS tree) along with some auxiliary edges (cross
edges) on the structure of graph. So, we can compute a spanning tree in a graph.
• The computed spanning tree is not a minimum spanning tree. Trees are much more
structured objects than graphs. For example, trees break up nicely into subtrees, upon
which subproblems can be solved recursively.
• For directed graphs the other edges of the graph can be classified as follows:
• Back edges: (u, v) where v is a (not necessarily proper) ancestor of u in the tree. (Thus, a
self-loop is considered to be a back edge).
• Forward edges: (u, v) where v is a proper descendent of u in the tree.
• Cross edges: (u, v) where u and v are not ancestors or descendants of one another (in
fact, the edge may go between different trees of the forest).
BF and DF
Spanning
Tree
Articulation Points
• An articulation point (or cut vertex) in a graph is a vertex whose removal disconnects the
graph.
• In other words, if you were to remove an articulation point, the graph would become
disconnected or have more components than before.
• Articulation points are critical for maintaining the connectivity of a graph.
• The presence of articulation points is often associated with vulnerabilities in network
communication.
Biconnected Components
• A biconnected component in a graph is a maximal subgraph in which any two vertices are
connected by at least two disjoint simple paths.
• In simpler terms, a biconnected component is a portion of the graph that is highly
connected; even if you remove any single vertex (and its incident edges), the remaining
graph will still be connected.
• Biconnected components are important for understanding the robustness of a graph and
identifying parts of the graph that can withstand the removal of certain nodes.
Articulation Points and Biconnected Components
• Articulation points and biconnected components are concepts related to the analysis of
connectivity in a graph.
• Articulation points play a crucial role in the identification of biconnected components.
• Removing an articulation point often results in breaking the graph into multiple
biconnected components.
• The graph itself can be viewed as a union of its biconnected components, and articulation
points are the vertices that connect these components.
• In summary, articulation points are key vertices whose removal can separate a graph into
multiple connected components, and biconnected components are maximal subgraphs
that remain connected even after the removal of any single vertex.
• The analysis of these concepts helps in understanding the connectivity and robustness of
a graph
• Let G = (V, E) be a connected undirected graph. Consider the following definitions:
• Articulation Point (or Cut Vertex): An articulation point in a connected graph is a vertex
(together with the removal of any incident edges) that, if deleted, would break the graph
into two or more pieces.
• Bridge: Is an edge whose removal results in a disconnected graph.
• Biconnected: A graph is biconnected if it contains no articulation points. In a biconnected
graph, two distinct paths connect each pair of vertices. A graph that is not biconnected
divides into biconnected components.
• Biconnected graphs and articulation points are of great interest in the design of network
algorithms, because these are the “critical" points, whose failure will result in the network
becoming disconnected.
• This is illustrated in the following figure:
Find Articulation Point
4 2
5 6
• Let G = (V, E) be a connected undirected graph. Consider the following definitions:
• Articulation Point (or Cut Vertex): An articulation point in a connected graph is
a vertex (together with the removal of any incident edges) that, if deleted, would
break the graph into two or more pieces.
• Bridge: Is an edge whose removal results in a disconnected graph.
• Biconnected: A graph is biconnected if it contains no articulation points. In
a biconnected graph, two distinct paths connect each pair of vertices. A graph
that is not biconnected divides into biconnected components.
• This is illustrated in the following figure:
Compute
discovery
time
Make table for identifying articulation point
node 1 2 3 4 5 6
Discovery 1 6 3 2 4 5
time(d)
L 1 1 1 1 3 3
Compute articulation point
• (u, v) = (parent, child)
• If L[v] >= d[u] then articulation point exist at u except for root,
otherwise not articulation point.
• Different condition will be applied for root vertex.
• If root is having multiple child then root is an articulation point.
• Initialization:
• Perform a DFS traversal of the graph starting from any vertex (usually the root).
• Initialize variables to keep track of the discovery time and low-link values for each
vertex.
• Use a stack to keep track of the vertices in the current DFS traversal.
• DFS Traversal:
• During the DFS traversal, assign a unique discovery time to each vertex as you visit it
for the first time.
• Keep track of the lowest discovery time (low-link value) reachable from the current
vertex, considering both forward and backward edges.
• Identifying Articulation Points:
• An articulation point is identified based on the following conditions:
• If the current vertex is the root of the DFS tree and has more than one child, it is
an articulation point.
• For other vertices, if there exists a child v such that low[v] >=
discovery_time[current], then the current vertex is an articulation point.
Thank You
Backtracking
By: Ashok Basnet
Lecture Outline
• Introduction to Backtracking method of problem solving
• The 8-queen problem
• Sum of Sub-set problem
• Graph coloring problem
• Hamilton Cycle
Introduction to Backtracking method of problem
solving
• Backtracking is used to solve problem in which a sequence of objects is chosen from a
specified set so that the sequence satisfies some criterion.
• Backtracking is a modified depth first search of a tree.
• Backtracking algorithms determine problem solutions by systematically searching the
solution space for the given problem instance.
• This search is facilitated by using a tree organization for the solution space.
• Backtracking is the procedure where by, after determining that a node can lead
to nothing but dead end, we go back (backtrack) to the nodes parent and proceed
with the search on the next child.
Terminology
• Problem state is each node in the depth first search tree.
• Solution states are the problem states ‘S’ for which the path from the root node to ‘S’
defines a tuple in the solution space.
• Answer states are those solution states for which the path from root node to s defines
a tuple that is a member of the set of solutions.
• State space is the set of paths from root node to other nodes. State space tree is
the tree organization of the solution space.
• Live node is a node that has been generated but whose children have not yet
been generated.
• E-node is a live node whose children are currently being explored. In other words, an E-
node is a node currently being expanded.
• Dead node is a generated node that is not to be expanded or explored any further. All
children of a dead node have already been expanded.
Planar Graphs
• When drawing a graph on a piece of a paper, we often find it convenient to permit
edges to intersect at points other than at vertices of the graph.
• These points of interactions are called crossovers.
• A graph G is said to be planar if it can be drawn on a plane without any
crossovers; otherwise G is said to be non-planar i.e., A graph is said to be planar.
N-Queens Problem
• Let us consider, N = 8. Then 8-Queens Problem is to place eight queens on an 8 x 8
chessboard so that no two “attack”, that is, no two of them are on the same
row, column, or diagonal.
• All solutions to the 8-queens problem can be represented as 8-tuples (x1, . . . . ,
x8), where xi is the column of the ith row where the ith queen is placed.
• The explicit constraints using this formulation are Si = {1, 2, 3, 4, 5, 6, 7, 8}, 1 < i < 8.
Therefore the solution space consists of 88 8-tuples.
• The implicit constraints for this problem are that no two xi’s can be the same (i.e.,
all queens must be on different columns) and no two queens can be on the
same diagonal.
• This realization reduces the size of the solution space from 88 tuples to 8! Tuples.
N-Queens Problem
• The promising function must check whether two queens are in the same column
or diagonal:
• Suppose two queens are placed at positions (i, j) and (k, l) Then:
• Column Conflicts: Two queens conflict if their xi values are identical.
• Diag 45 conflict: Two queens i and j are on the same 450 diagonal if: i – j = k – l. This
implies, j – l = i – k.
• Diag 135 conflict: i + j = k + l. This implies, j – l = k – i.
• Therefore, two queens lie on the same diagonal if and only if: |j – l| = |i – k |
• Where, j be the column of object in row i for the ith queen and l be the column
of object in row ‘k’ for the kth queen.
Sum of Sub-set problem
• Given a set of non-negative integers and a value sum, the task is to check if there is a
subset of the given set whose sum is equal to the given sum.
• Examples:
• Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
Explanation: There is a subset (4, 5) with sum 9.
• Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
Explanation: There is no subset that add up to 30.
Sum of Sub-set problem
• Given positive numbers wi, 1 ≤ i ≤ n, and m, this problem requires finding all subsets of
wi whose sums are ‘m’.
• All solutions are k-tuples, 1 ≤ k ≤ n.
• For example, n = 4, w = (11, 13, 24, 7) and m = 31, the desired subsets are (11, 13, 7)
and (24, 7).
• Draw the tree for the given problem to find the solution.
Graph coloring problem
• Let G be a graph and m be a given positive integer.
• We want to discover whether the nodes of G can be colored in such a way that no two
adjacent nodes have the same color, yet only m colors are used.
• This is termed the m-colorabiltiy decision problem.
• The m-colorability optimization problem asks for the smallest integer m for which the
graph G can be colored.
• Given any map, if the regions are to be colored in such a way that no two
adjacent regions have the same color, only four colors are needed.
• For many years it was known that five colors were sufficient to color any map, but
no map that required more than four colors had ever been found.
• After several hundred years, this problem was solved by a group of mathematicians
with the help of a computer. They showed that in fact four colors are sufficient for
planar graphs.
Graph coloring problem
• The function m-coloring will begin by first assigning the graph to its adjacency
matrix, setting the array x [] to zero.
• The colors are represented by the integers 1, 2, . . . , m and the solutions are given by
the n-tuple (x1, x2, . . ., xn), where xi is the color of node i.
Hamilton Cycle
• Let G = (V, E) be a connected graph with n vertices. A Hamiltonian cycle (suggested by
William Hamilton) is a round-trip path along n edges of G that visits every vertex once
and returns to its starting position.
• The graph G1 contains the Hamiltonian cycle 1, 2, 8, 7, 6, 5, 4, 3, 1. The graph G2
contains no Hamiltonian cycle.
Start with the node 0 .
Apply DFS for finding the Hamiltonian path.
When base case reach (i.e. total no of node traversed == V (total vertex)):
Check whether current node is a neighbour of starting node.
As node 2 and node 0 are not neighbours of each other so return from it.
As cycle is not found in path {0, 3, 1, 4, 2}. So, return from node 2, node 4.
Now, explore another option for node 1 (i.e node 2)
When it hits the base condition again check for Hamiltonian cycle
As node 4 is not the neighbour of node 0, again cycle is not found then return.
Return from node 4, node 2, node 1.
Now, explore other options for node 3.
In the Hamiltonian path {0,3,4,2,1,0} we get cycle as node 1 is the
neighbour of node 0.
So print this cyclic path .
This is our Hamiltonian cycle.
Hamilton Cycle

ADA Merged

Uploaded by

Copyright:

Available Formats

ADA Merged

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ADA Merged

Uploaded by

Copyright:

Available Formats

CHAPTER 1: PRINCIPLES OF ANALYZING

ALGORITHMS AND PROBLEMS

3. Sorting, Selection and Sequencing: Merge sort, Binary search, Job

6. Backtracking: The 8-queens problem

▪ Definition: An algorithm is a precise sequence of instructions designed to tackle

▪ Algorithms consist of finite, well-defined instructions.

Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7

Need to recognize limitations of various algorithms for solving a problem.

Need to learn techniques for writing more efficient code.

Correctness and Efficiency

Decide whether some problems have no solution in

Investigate memory usage as different measure of

The performance of a program is the amount of computer memory and

We use two approaches to determine the performance of a program.

One is analytical, and the other experimental.

In performance analysis we use analytical methods, while in performance

▪ The time needed by an algorithm expressed as a function of the size of a problem is

▪ It is the asymptotic complexity of an algorithm, which ultimately determines the size of

▪ The space complexity of a program is the amount of memory it needs to run to

▪ The space need by a program has the following components:

- Likewise, a program that saves space over a competing program is

- We want to “save face” by preventing the program from locking up or generating

▪ If ‘n’ is the number of data items to be processed

▪ When the running time of a program is linear, it is

▪ This running time arises for algorithms that

▪ When the running time of an algorithm is

- Whenever n doubles, the running time squares.

- Typically, the storage space required by an algorithm is directly proportional to

▪ The solution to above search problem includes:

▪ So the machine-dependent constants can always be ignored after a certain

▪ We define an algorithm’s worst-case time complexity by using the Big-O notation.

▪ Scalability: Estimates how an algorithm's performance scales with input size.

▪ Constants Ignored: Simplifies analysis by disregarding constant factors.

▪ Omega notation helps us understand how efficiently an algorithm performs under

▪ It represents both the upper and lower bounds of an algorithm's performance,

▪ Little Omega (ω)

▪ Linear search is O (n)

▪ Bubble sort is O (n2)

- For example, Consider the expression 3n3 + 6n2 + 6000 = Θ(n3)

▪ A randomized algorithm is an algorithm that employs a degree of randomness as

▪ Makes use of Randomizer (Random number generator).

▪ Decisions made in the algorithm depends on the output of the randomizer.

▪ Efficiency and Approximation:

▪ Las Vegas Algorithms:

▪ These algorithms use randomness to improve efficiency.

▪ Examples include randomized quicksort and some graph algorithms.

▪ For the pop operation:

Addition of an element to the queue.

Adding an element will be performed after checking

But if rear == n then it is said to be an Overflow

▪ Get the front element from the

In the priority queue, an

▪ A Binary tree is represented by a pointer to

When we insert a new element, the rear

If there is only one element left which is to

▪ Step 1 − Checks if the stack is empty.

o Multiplying Large Numbers: for efficient multiplication.

o Closest Pair of Points: finding the closest pair in a set of points.

▪ Divide the problem into a number of

function selectionSort(array, size):

Keys 10 20 30