Introduction to Problem

Solving
 Module 1: Computational Problems

Introduction to computational problems: Sorting, Searching, Nearest-neighbour search, k-th smallest

Selection, Greatest Common Divisor (GCD), Fibonacci sequence, Factorial, Primality, Integer
Factorization, Polynomial Identity Testing, Discrete Logarithm, Shortest Path, Hamiltonian Cycle,
Integer Programming,
Knapsack problem, 3-SAT, Clique, Vertex Cover, Minimum spanning tree (MST), Maximum flow,
Undirected s-t Reachability, Pattern matching, Longest common subsequence (LCS), Traveling
Salesman, recommendation systems, Job Scheduling, Efficient range sum queries.

Flowcharts, Algorithms, pseudocode and logical reasoning

Problem-Solving Approaches: Brute force, Divide and conquer, Greedy methods, Backtracking,
Dynamic programming.
Computational Problems

Problem-solving is the cognitive process and structured

methodology of identifying an issue, analyzing its root
causes, developing potential solutions, selecting the most
viable option, and implementing it to achieve a desired
outcome. It involves overcoming obstacles to reach a goal,
whether the problem is simple or complex, and is a
fundamental skill used in all aspects of life and business.
“How many of you used Google Maps, Amazon, YouTube, or WhatsApp
today?”
Example 1: Google Maps
•Problem: Find the shortest path from your home to college.
•Input: Locations (home, college, roads).
•Output: Shortest path + estimated time.

Example 2: Amazon
•Problem: Recommend products based on your search.
•Input: Purchase history, browsing.
•Output: Suggested items (Recommendation System).

Example 3: WhatsApp Search

•Problem: Search a word inside chat.
•Input: Search keyword.
•Output: Matching messages.

Every real-world problem that computers solve is a computational

problem.
Why Study Computational Problems?
• Google Maps → Shortest path
• Amazon → Product recommendations
• WhatsApp → Search messages
• YouTube → Suggested videos

• All of these are computational problems!

What is a Computational Problem?
▪ Solving problems effectively with a computer.
▪ A task that can be solved by a computer using a sequence of steps.

• Structure:
• 1. Input → What is given
• 2. Output → What we want
• 3. Method → Steps/Algorithm to solve
Types of Computational Problems
• Numerical → Sorting, GCD, Fibonacci
• Graph → Shortest path, MST
• Optimization → Knapsack, Job Scheduling
• String → Pattern Matching, LCS
• Decision → Primality, 3-SAT
Sorting
Sorting refers to rearrangement of a given array or list of elements according
to a comparison operator on the elements. The comparison operator is used to
decide the new order of elements in the respective data structure
Sorting
Sorting algorithms are essential in Computer Science as they simplify complex
problems and improve efficiency. They are widely used in searching, databases,
divide and conquer strategies, and data structures.

Key Applications:

• Organizing large datasets for easier handling and printing

• Enabling quick access to the k-th smallest or largest elements
• Making binary search possible for fast lookups in sorted data
• Solving advanced problems in both software and algorithm design
 Types of Sorting Techniques

There are various sorting algorithms are used in data

structures.
[Link]-based: We compare the elements in a
comparison-based sorting algorithm)

[Link]-comparison-based: We do not compare the

elements in a non-comparison-based sorting algorithm)
Bubble Sort
•Bubble Sort: Compare neighbors, swap if wrong → repeat (like bubbles
rising in water).
Insertion Sort
•Insertion Sort: Insert each element into its correct place in sorted part.
Selection Sort
It is a comparison-based sorting algorithm that repeatedly selects the smallest (or largest) element
from the unsorted part of the array and swaps it with the first unsorted element. This process continues
until the array is fully sorted.
Merge Sort
• Divide: Divide the list or array recursively into two halves until it can no more be divided.
• Conquer: Each subarray is sorted individually using the merge sort algorithm.
• Merge: The sorted subarrays are merged back together in sorted order. The process continues until all
elements from both subarrays have been merged
Searching

• Searching algorithms are essential tools in computer science used to locate

specific items within a collection of data. When we search an item in an
array, there are two most common algorithms used based on the type of
input array.
• Linear Search : It is used for an unsorted array. It mainly does one by one
comparison of the item to be search with array elements.
• Binary Search : It is used for a sorted array. It mainly compares the array's
middle element first and if the middle element is same as input, then it
returns. Otherwise it searches in either left half or right half based on
comparison result (Whether the mid element is smaller or greater). This
algorithm is faster than linear search and takes O(Log n) time.
Linear Search ?
Linear search is the simplest search algorithm and often called sequential search. In this type of searching, we simply
traverse the list completely and match each element of the list with the item whose location is to be found. If the
match found then location of the item is returned otherwise the algorithm return NULL.
Binary Search
• Binary Search is a searching algorithm that operates on a sorted or monotonic
search space, repeatedly dividing it into halves to find a target value or optimal
answer in logarithmic time O(log N).
Nearest Neighbor Search

Nearest neighbor search (NNS) finds the data point(s) in a

dataset that are closest or most similar to a given query
point, often using a distance metric like Euclidean
distance. The goal is to efficiently retrieve similar items
from a large collection, which can be an exact search or
an Approximate Nearest Neighbor (ANN) search for speed
in high-dimensional data. This technique is fundamental in
AI for applications like recommendation engines, image
retrieval, and natural language processing.
Kth Smallest Selection
Given an array of distinct integers arr[] and an integer k. The task is to find the k-th smallest element in the
array.

Input: arr[] = [7, 10, 4, 3, 20, 15], k = 3

Output: 7
Explanation: The sorted array is [3, 4, 7, 10, 15, 20]. The 3rd smallest element is 7.

Input: arr[] = [12, 3, 5, 7, 19], k = 2

Output: 5
Explanation: The sorted array is [3, 5, 7, 12, 19]. The 2nd smallest element is 5.

Input: arr[] = [1, 5, 2, 8, 3], k = 4

Output: 5
Greatest Common Divisor
The greatest common divisor (GCD), or highest common factor (HCF), is the largest positive integer that
divides two or more integers exactly, without leaving a remainder.

For example, the GCD of 20 and 15 is 5, because 5 is the largest number that divides both 20 and 15 evenly.

The concept is fundamental in number theory and has applications in simplifying fractions, modular
arithmetic, and encryption algorithms.

Example: GCD of 20 and 15

Factors of 20: 1, 2, 4, 5, 10, 20
Factors of 15: 1, 3, 5, 15
Common Factors: 1, 5
Greatest Common Factor (GCD): 5
Fibonacci
• Definition: A Sequence where each term is the sum of the previous
two. Standard start: F0 = 0, F1 = 1 → 0, 1, 1, 2, 3, 5, 8, 13, ...
• Why it matters: DP classic, modeling growth, spirals in nature, and
interviews.
Factorial

A factorial, denoted by an exclamation point (!), is the product of all positive integers from 1 up to a given
non-negative integer.

For example, 5! (5 factorial) is 5 × 4 × 3 × 2 × 1, which equals 120.

By convention, 0! is defined as 1. Factorials are used in mathematics, especially in probability and

combinatorics, for calculating permutations and combinations.
Primality
Primality, is the property of being a prime number, meaning a natural number greater than 1 that has no
positive divisors other than 1 and itself.

Definition: A prime number is a whole number greater than 1 that can only be divided evenly by 1 and
itself.
Examples: 2, 3, 5, 7, 11, 13, and 97 are prime numbers.
Non-examples:1 is not prime: It is specifically excluded from the definition of prime numbers.
Composite numbers: Numbers that have more than two factors (e.g., 4, 6, 8, 9, 10) are called composite
numbers.

What is a primality test?

Purpose: An algorithm designed to determine if a given number is prime or not.
How it works: Instead of factoring the number (finding its prime factors), a primality test directly answers
whether the number is prime or composite.
Applications: Primality tests are fundamental in cryptography to ensure the security of online transactions
and digital data.
Integer Factorization

Integer factorization is the process of breaking down a composite positive integer into its prime factors,
which are prime numbers that multiply together to equal the original number. For example, the prime
factorization of 60 is 2 × 2 × 3 × 5
Polynomial Identity Testing
Polynomial Identity Testing (PIT) is a problem in theoretical computer science and mathematics that asks
whether a given arithmetic circuit computes the zero polynomial (a polynomial that is identically zero for all
variable assignments). While a simple randomized algorithm exists by evaluating the polynomial at a
random point, a deterministic algorithm remains an open challenge and its solution has significant
implications for understanding the hardness of computations.

Consider the well-known polynomial identity:

(a+b)(a-b) = a2 – b2

To apply Polynomial Identity Testing, one would typically rearrange the equation to test if the difference of
the two sides is identically zero.
Let P = (a+b)(a-b) and Q = a2 – b2
We want to test if P – Q = 0

Polynomial Identity Testing Not Happening:

P(x) = x + 1
Q(x) = x^2 - 1
Shortest Path

The shortest path algorithms are the ones that focuses

Types of Shortest Path Algorithm

on calculating the minimum travelling cost from source
node to destination node of a graph in optimal time and
space complexities.
Single Source Shortest
Types of Shortest Path Algorithms: Path
As we know there are various types of graphs (weighted,
unweighted, negative, cyclic, etc.) therefore having a
single algorithm that handles all of them efficiently is not All Pair Shortest Path
possible. In order to tackle different problems, we have
different shortest-path algorithms, which can be
categorised into two categories.
 Shortest Path
Single Source Shortest Path All Pair Shortest Path Algorithm
(The shortest path algorithms are the ones that focuses
on calculating the minimum travelling cost from source
node to destination node of a graph in optimal time and
space complexities)

• Depth First Search (DFS) • Floyd-Warshall Algorithm

• Breadth First Search (BFS) • * Johnson’s Algorithm
• Dijkstra’s Algorithm
• Bellman Ford Algorithm
• Topological Sort
• A* Search Algorithm
Shortest Path
Depth First Search:

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. we traverse all
adjacent vertices one by one. When we traverse an adjacent vertex, we completely finish the traversal of all
vertices reachable through that adjacent vertex. Extra memory, usually a stack, is needed to keep track of the
nodes discovered so far along a specified branch which helps in backtracking of the graph.

A -> B -> D -> F -> E -> C -> G

Shortest Path
Depth First Search:
Shortest Path
Depth First Search:

The depth first search traversal order of the above graph is-
A, B, E, F, C, D
Shortest Path
Depth First Search:
Shortest Path
Depth First Search:
Shortest Path
Depth First Search:

DFS: U -> V -> Y -> X -> W -> Z

Shortest Path
Breadth First Search:

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given
property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at
the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were
encountered but not yet explored.

A -> B -> C -> E -> D -> F -> G

Shortest Path
Breadth First Search:

The breadth first search traversal order of the above graph is-
A, B, C, D, E, F
Shortest Path
Breadth First Search:
Shortest Path
Breadth First Search:
Shortest Path
Breadth First Search:
Shortest Path
Dijkstra's Algorithm

In Dijkstra's Algorithm, the goal is to find the shortest distance from a given source node to all other nodes in the
graph. As the source node is the starting point, its distance is initialized to zero. From there, we iteratively pick
the unprocessed node with the minimum distance from the source, this is where a min-heap (priority queue) or a
set is typically used for efficiency. For each picked node u, we update the distance to its neighbors v using the
formula: dist[v] = dist[u] + weight[u][v], but only if this new path offers a shorter distance than the current
known one. This process continues until all nodes have been processed.

5
A 3 B C
Shortest Path
Dijkstra's Algorithm

1
B D Find the shortest path from A to D
10
3
A 9 6 DBCA
2
5
C E
2

A B C D E
A 0
C 10 5
E 8 14 7
B 8 13
D 9
Shortest Path
Dijkstra's Algorithm

Limitation of Dijkstra's Algorithm: Since, we need to find the single source shortest path, we might initially think of
using Dijkstra's algorithm. However, Dijkstra is not suitable when the graph consists of negative edges. The reason is, it doesn't
revisit those nodes which have already been marked as visited. If a shorter path exists through a longer route with negative
edges, Dijkstra's algorithm will fail to handle it.
Shortest Path
Dijkstra's Algorithm
Shortest Path
Dijkstra's Algorithm
Shortest Path
Bellman-Ford Algorithm

Bellman-Ford is a single source shortest path algorithm. It effectively works in the cases of negative edges and is
able to detect negative cycles as well. It works on the principle of relaxation of the edges.

Principle of Relaxation of Edges

• Relaxation means updating the shortest distance to a node if a shorter path is found through another node.
For an edge (u, v) with weight w:
• If going through u gives a shorter path to v from the source node (i.e., distance[v] > distance[u] + w), we
update the distance[v] as distance[u] + w.
• In the bellman-ford algorithm, this process is repeated (V - 1) times for all the edges.
Shortest Path
Bellman – Ford Algorithm
Shortest Path
Bellman Ford Algorithm
Shortest Path
Topological Sort

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed
edge u-v, vertex u comes before v in the ordering.
Shortest Path
Topological Sort
Shortest Path
Topological Sort

Write in-degree of each vertex

•Vertex-A has the least in-degree.

•So, remove vertex-A and its associated edges.
•Now, update the in-degree of other vertices.
Shortest Path
Topological Sort

For the given graph, following 2 different topological orderings are possible-
•A B C D E
•A B D C E
Shortest Path
Topological Sort

For the given graph, following 4 different topological orderings are possible:
•1 2 3 4 5 6
•1 2 3 4 6 5
•1 3 2 4 5 6
•1 3 2 4 6 5
Shortest Path
A* Search Algorithm

To approximate the shortest path in real-life situations, like- in maps, games where there can be many
hindrances. We can consider a 2D Grid having several obstacles and we start from a source cell to reach towards
a goal cell.

A* Search algorithm is one of the best and popular technique used in path-finding and graph traversals
Shortest Path
A* Search Algorithm

• A* search algorithm is informed search algorithm.

• Used to find the optimal path from the initial state to the goal state.
• A* search algorithm evaluates nodes by using the function,
f(n) = g(n) + h(n)
• g(n) = Cost from initial state to the state at the current node n
• h(n) = Estimated cost from the state at node n to a goal state
 Shortest Path
A* Search Algorithm
Nodes: S (Start), A, B, G (Goal)

S Edge costs:
1 4 S-A=1, S-B=4, A-B=2, A-G=5, B-G=1
2
A B Heuristic h(n):
h(S)=7, h(A)=6, h(B)=2, h(G)=0
5 1
G
Neighbours:
• Neighbors: A (via B): g=6, h=6 → f=12 (worse,
At S: • A: g=1, h=6 → f=7 ignore)
g(S) = 0 G: g=5, h=0 → f=5
• B: g=4, h=2 → f=6 Path found: S → B → G
f(S) = g + h = 0 + 7 = 7
• Open = {A(f=7), B(f=6)} Total cost = 5
Open = {S} Open = {A(f=7), G(f=5)}
• Pick B (lowest f). Pick G (lowest f).
 Shortest Path
Floyd – Warshall Algorithm

The Floyd–Warshall algorithm works by

maintaining a two-dimensional array that
represents the distances between nodes. Initially,
this array is filled using only the direct edges
between nodes. Then, the algorithm gradually
updates these distances by checking if shorter
paths exist through intermediate nodes.

This algorithm works for both

directed and undirected weighted graphs and can
handle graphs with both positive and negative-
weight edges.
Shortest Path
Floyd – Warshall Algorithm
Shortest Path
Johnson’s Algorithm

(Uses Dijkstra’s and Bellman Ford to compute. Less complex compare to Floyd-warshall)

[Link] a New Vertex:

•Introduce a new vertex s and connect it to every other vertex in the graph with edge weight 0.
[Link] Bellman-Ford from s:
•This gives you shortest distances h[v] from s to every vertex v.
•If a negative-weight cycle is detected, the algorithm terminates.
[Link] the Graph:
•For each edge (u, v) with weight w(u, v), compute a new weight:
w′(u,v)=w(u,v)+h[u]−h[v]w'(u, v) = w(u, v) + h[u] - h[v]
•This transformation ensures all edge weights become non-negative, preserving shortest paths.
[Link] Dijkstra’s Algorithm:
•For each vertex u, run Dijkstra’s algorithm on the reweighted graph to find shortest paths to all other vertices.
[Link] Final Distances:
•Convert the reweighted distances back to original weights:
d(u,v)=d′(u,v)−h[u]+h[v]
 First take a New Vertex S and then, Calculate the
shortest path from S to All other Vertices:

H(a) = (s,a) = 0
H(b) = (s,b) = s, d, c, b = -1
H(c) = (s,c) = s, d, c = -5
H(d) = (s,d) = s, d = 0
H(e) = (s,e) = s, a, e = -4

W(u,v) W(u,v) = w(u,v) + h(u) – h(v)

W(a,b) = 3 + 0 – (-1) = 4
W(a,c) = 13
W(a,e) = 0 w(c,b) = 0 w(e,d)= 2
W(s,c) = 5 w(b,d) = 0 w(d,c) = 0
W(s,a) = 0 w(s,d) = 0 w(b,e) = 10
W(d,a) = 10 w(s,b) = 1 w(s,e) = 4

After this, Use Dijkstra’s for final searching of least path

Hamiltonian Cycle
Hamiltonian Cycle or Circuit is a path in an undirected graph that visits all the vertices in the graph exactly once
and terminates back at the starting node. It's also known as a Hamiltonian circuit and is a fundamental concept
in graph theory.

Given an undirected graph, our task is to determine whether the graph contains a Hamiltonian cycle or not.
For example, in a graph with vertices A, B, C, and D, a Hamiltonian cycle could be A -> B -> C -> D -> A.

In the Hamiltonian path {0,3,4,2,1,0} we get cycle

Other paths are to be ignored as repetition of nodes will be

there.
Hamiltonian Cycle
Hamiltonian Cycle or Circuit is a path in an undirected graph that visits all the vertices in the graph exactly once
and terminates back at the starting node. It's also known as a Hamiltonian circuit and is a fundamental concept
in graph theory.

Given an undirected graph, our task is to determine whether the graph contains a Hamiltonian cycle or not.
For example, in a graph with vertices A, B, C, and D, a Hamiltonian cycle could be A -> B -> C -> D -> A.
Integer Programming

Integer programming (IP) is an optimization technique where some or all of the decision variables are restricted
to integer values, such as "whole numbers".

This mathematical approach is used to solve problems involving discrete quantities or yes/no decisions, aiming
to minimize or maximize an objective function subject to certain constraints.

Common applications include portfolio optimization, resource allocation, and scheduling.

An example of an Integer Programming (IP) problem is the Knapsack Problem. A hiker wants to fill their
knapsack with items to maximize the total value, subject to a weight capacity constraint. Each item has a specific
weight and a specific value. The hiker cannot take fractions of items; they must take the whole item or none at
all.
Knapsack Problem
A thief is robbing a store and can carry a maximal
weight of W into his knapsack. There are n items
available in the store, and the weight of the i-th item is
wi, and its profit is pi. What items should the thief
take?
Based on the nature of the items, Knapsack problems
are categorized as
 Knapsack Problem
Objective of the Knapsack problem:
We have some objects, and every object has some
weights. We are provided with a bag, which is known as a
Knapsack
We have to fill the maximum objects in the bag according
to their weights and profit so that the profit we get is
maximum.

Constraints:

We will be provided with the object identification, including

their profits and weight.
The total weight of the objects filled in the bags should be
less than the provided counter(m), which is given.
Knapsack Problem N=3
Max=20

1 2 3
Profit 25 24 15
Weight 18 15 10
Knapsack Problem
Knapsack Problem
It’s a Dynamic Programming concept which falls in optimization category.
It derives its name from a scenario where, given a set of items with specific weights and assigned values, the goal is
to maximize the value in a knapsack while remaining within the weight constraint. Each item can only be selected
once, as we don’t have multiple quantities of any item.

Example
Let’s take the example of Mary, who wants to carry some fruits in her knapsack and maximize the profit she makes.
She should pick them such that she minimizes weight and maximizes value.
Here are the weights and profits associated with the different fruits:
Items: { Apple, Orange, Banana, Melon }
Weights: { 2, 3, 1, 4 }
Profits: { 4, 5, 3, 7 }
Knapsack Capacity: 5
Fruits Picked by Mary:
Banana and Melon is the best combination, as it gives us the maximum profit (10) and the total weight does not
exceed the knapsack’s capacity (5).
Knapsack Problem
 Knapsack Problem

120 Because from there, changes started occurring. So 120 – 70 = 50, so next wherever it is happening, which means item 1
3-SAT
SAT stands for Boolean Satisfiability Problem.

Imagine you’re given a logical expression made up of variables (like A, B, C), and each variable can be either
true or false.

Your job is to figure out: Is there any way to assign true/false values to these variables so that the whole
expression becomes true?

If yes, the expression is satisfiable. If no, it’s unsatisfiable.

Example:
(A OR NOT B) AND (B OR C)
3-SAT
3SAT is a special version of SAT where: The expression is written in Conjunctive Normal Form (CNF): a bunch
of clauses joined by ANDs.

Each clause has exactly three literals (variables or their negations) joined by ORs.

Example of a 3SAT expression:

(A OR B OR C) AND (NOT A OR D OR E) AND (F OR NOT B OR G)

Your task is the same: Find a way to assign true/false values to all variables so that every clause is true.

Why is 3SAT Important?

• Many complex problems can be transformed into 3SAT.
• If you can solve 3SAT efficiently, you can solve a whole class of problems known as NP-complete.
Clique
A clique is a group of nodes where each node is directly connected to every other node in the group. Any
complete subgraph (all nodes connected) is clique.
.
 Clique
2-Node Cliques (Edges)
Every edge is a 2-node clique. There are 10 edges, so 10 cliques of size 2.

3-Node Cliques (Triangles)

We look for triplets where all three nodes are mutually connected.
•{1, 2, 3}
•{1, 3, 4}
•{2, 3, 5}
•{3, 4, 5}
So, 4 cliques of size 3.

4-Node Cliques
Check if any 4 nodes are fully connected:
•{1, 3, 4, 5} → All connected
•{2, 3, 4, 5} → All connected
So, 2 cliques of size 4.

5-Node Clique?
Check if all 5 nodes are mutually connected. Node 1 is not connected to node 5, so no 5-node clique.
Clique
 Vertex Cover
A vertex cover is a set of vertices in a graph such that every edge in the graph is connected to at least one vertex
in this set. In simple terms, You’re choosing nodes so that every edge is “touched” by at least one of them.

Edges:
A—B—C
•A–B, A–D
| | |
•B–C, B–E
D—E—F
•C–F
|
•D–E
G
•E–F, E–G

Minimum Vertex Cover: {A, B, C, E} Minimum Vertex Cover: ?

Minimum Spanning Tree (MST)
A spanning tree is a tree in which we have N nodes(i.e. All the nodes present in the original graph) and N-1
edges and all nodes are reachable from each other.
Minimum Spanning Tree (MST)
Among all possible spanning trees of a graph, the minimum spanning tree is the one for which the sum of
all the edge weights is the minimum.

Sum of edge weights = 17

Minimum Spanning Tree (MST)
Among all possible spanning trees of a graph, the minimum spanning tree is the one for which the sum of
all the edge weights is the minimum.

Sum of edge weights = 17

Minimum Spanning Tree (MST)
Two ways by which we can check for MST.
1. Prim’s Method
2. Kruskal’s Method

Prim’s algorithm is a Greedy algorithm. This algorithm always starts with a single node and moves through
several adjacent nodes, in order to explore all of the connected edges along the way.
Minimum Spanning Tree (MST)
Minimum Spanning Tree (MST)
Minimum Spanning Tree (MST)
Minimum Spanning Tree (MST)
Undirected S-T Reachability

Undirected S-T Reachability, also known as Undirected S-T Connectivity (USTCON), is the problem of
determining if there is a path between two specified vertices, s and t, in an undirected graph. Standard
graph traversal algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) can solve this
problem, but they require more space than is ideal.
Pattern Matching
Pattern matching is the process of searching for a specific sequence of characters, called a “Pattern,” within
a larger piece of text or data.
Longest Common Subsequence (LCS)
The Longest Common Subsequence (LCS) problem is where you're asked to find the longest sequence of
characters present in two strings. Variations of this problem are commonly found in real-world applications
such as bioinformatics, natural language processing, and text comparison. This problem can be solved using
dynamic programming techniques, which involve breaking down the problem into smaller subproblems and
then solving them iteratively.

Example 1
Input: s1 = "abccba", s2 = "abddba" Output: "abba"

Example 2
Input: s1 = "zfadeg", s2 = "cdfsdg" Output: "fdg"

Example 3
Input: s1 = "abd", s2 = "badc" Output: "ad" (or "bd")
Longest Common Subsequence (LCS)
The following steps are followed for finding the longest common subsequence.

[Link] a table of dimension n+1*m+1 where n and m are the lengths

of X and Y respectively. The first row and the first column are filled with zeros.
Longest Common Subsequence (LCS)
2. Fill each cell of the table using the following logic.

3. If the character corresponding to the current row and current column are matching, then fill the current cell by adding one to
the diagonal element. Point an arrow to the diagonal cell.

4. Else take the maximum value from the previous column and previous row element for filling the current cell. Point an arrow to
the cell with maximum value. If they are equal, point to any of them.

The value in the last row

and the last column is the
length of the longest
common subsequence.
 Longest Common Subsequence (LCS)
In order to find the longest common subsequence, start from the last element and follow the direction of the arrow. The
elements corresponding to () symbol form the longest common subsequence.

Thus, the longest common subsequence is CA.

Travelling Salesman Problem
Travelling Salesman Problem
The traveling salesman problem consists of a salesman and a set of cities. The salesman has to visit each one of
the cities starting from a certain one (e.g. the hometown) and returning to the same city. The challenge of the
problem is that the traveling salesman wants to minimize the total length of the trip.
Travelling Salesman Problem

The problem lies in finding a minimal path passing from all vertices once.
For example the path Path1 {A, B, C, D, E, A} and the path Path2 {A, B, C, E, D, A} pass all the vertices but Path1
has a total length of 24 and Path2 has a total length of 31.
Travelling Salesman Problem

How the Hamiltonian Cycle and the Traveling Salesman Problem differ? The Hamiltonian Cycle problem is
to find out if there exists a tour that visits each city exactly once. Here, we know that the Hamiltonian Tour
exists (due to the graph being complete), and there are indeed many such tours. The problem is to find a
minimum weight Hamiltonian Cycle.
Maximum Flow
The Maximum Flow problem is about finding the maximum flow through a directed graph, from one place in the
graph to another.
More specifically, the flow comes from a source vertex s, and ends up in a sink vertex t, and each edge in the graph
is defined with a flow and a capacity, where the capacity is the maximum flow that edge can have.

Average Path Bottle Neck

SADT 2

SBCT 3

SBACT 3

Total 8
Recommendation System

E-commerce and retail companies are utilizing the power of data to boost sales with the help of
recommender systems implemented on their websites. The use cases of these systems have been increasing
consistently.

How does it work?

Recommendation systems use specialized algorithms and machine learning solutions. Driven by the
automated configuration, coordination, and management of machine learning predictive analytics algorithms,
the recommendation system can wisely select which filters to apply to a particular user's specific situation. It
facilitates marketers to maximize conversions and average order value.
Recommendation System
Recommender systems can forecast user ratings, even before they have provided one, making them an
effective tool. Mainly, a recommendation system processes data through four phases as follows:

• Collection: Data collected can be explicit (ratings and comments on products) or implicit (page views,
order history, etc.).
• Storing: The type of data used to create recommendations can help you decide the kind of storage you
should use- NoSQL database, object storage, or standard SQL database.
• Analyzing: The recommender system finds items with similar user engagement data after analysis.
• Filtering: This is the last step where data gets filtered to access the relevant information required to
provide recommendations to the user. To enable this, you will need to choose an algorithm suiting the
recommendation system.
Recommendation System
Types of Recommendation System:

1. Collaborative Filtering: The collaborative filtering method is based on gathering and analyzing data on
user’s behavior. This includes the user’s online activities and predicting what they will like based on the
similarity with other users.
For example, if user A likes Apple, Banana, and Mango while user B likes Apple, Banana, and Jackfruit, they
have similar interests. So, it is highly likely that A would like Jackfruit and B would enjoy Mango. This is how
collaborative filtering takes place.

Two kinds of collaborative filtering techniques used are:

• User-User collaborative filtering
• Item-Item collaborative filtering
Recommendation System
Types of Recommendation System:

2. Content-Based Filtering
Content-based filtering methods are based on the description of a product and a profile of the user’s
preferred choices. In this recommendation system, products are described using keywords, and a user profile
is built to express the kind of item this user likes.

For instance, if a user likes to watch movies such as Iron Man, the recommender system recommends movies
of the superhero genre or films describing Tony Stark. The central assumption of content-based filtering is
that you will also like a similar item if you like a particular item.
Recommendation System
Types of Recommendation System:

3. Hybrid Recommendation Systems

In hybrid recommendation systems, products are recommended using both content-based and collaborative
filtering simultaneously to suggest a broader range of products to customers. This recommendation system is
up-and-coming and is said to provide more accurate recommendations than other recommender systems.

Netflix is an excellent case in point of a hybrid recommendation system. It makes recommendations by

juxtaposing users’ watching and searching habits and finding similar users on that platform. This way, Netflix
uses collaborative filtering.

By recommending such shows/movies that share similar traits with those rated highly by the user, Netflix uses
content-based filtering.
Job Scheduling
Job scheduling algorithm is applied to schedule the jobs on a single processor to maximize the profits. The
greedy approach of the job scheduling algorithm states that, Given n number of jobs with a starting time and
ending time, they need to be scheduled in such a way that maximum profit is received within the maximum
deadline.

Algorithm:
Step1 − Find the maximum deadline value from the input set of jobs.
Step2 − Once, the deadline is decided, arrange the jobs in descending order of their profits.
Step3 − Selects the jobs with highest profits, their time periods not exceeding the maximum deadline.
Step4 − The selected set of jobs are the output.
Job Scheduling
Problem: Solve the following job scheduling with deadlines problem using the greedy method. Number of
jobs N = 4. Profits associated with Jobs : (P1, P2, P3, P4) = (100, 10, 15, 27). Deadlines associated with jobs
(d1, d2, d3, d4) = (2, 1, 2, 1)

Sort all jobs in descending order of profit.

So, P = (100, 27, 15, 10), J = (J1, J4, J3, J2) and D = (2, 1, 2, 1). We shall select one by one job from the list of
sorted jobs, and check if it satisfies the deadline. If so, schedule the job in the latest free slot. If no such slot is
found, skip the current job and process the next one. Initially,

Profit of scheduled jobs, SP = 0

Job Scheduling
Job Scheduling
Job Scheduling
Problem: Solve the following instance of “job scheduling with deadlines” problem : n = 7, profits (p1, p2, p3, p4,
p5, p6, p7) = (3, 5, 20, 18, 1, 6, 30) and deadlines (d1, d2, d3, d4, d5, d6, d7) = (1, 3, 4, 3, 2, 1, 2). Schedule the jobs
in such a way to get maximum profit.

Sort all jobs in descending order of profit.

So, P = (30, 20, 18, 6, 5, 3, 1), J = (J7, J3, J4, J6, J2, J1, J5) and D = (2, 4, 3, 1, 3, 1, 2). We shall select one by one job
from the list of sorted jobs J, and check if it satisfies the deadline. If so, schedule the job in the latest free slot. If
no such slot is found, skip the current job and process the next one.
Job Scheduling
Job Scheduling

First, all four slots are occupied and none of the

remaining jobs has deadline lesser than 4. So
none of the remaining jobs can be scheduled.
Thus, with the greedy approach, we will be able
to schedule four jobs {J7, J3, J4, J6}, which give a
profit of (30 + 20 + 18 + 6) = 74 units.
Efficient Range Sum Queries

Given an array, a range sum query asks: “What is the sum of elements between index L and R?”

For example, in the array [2, 4, 6, 8, 10], Sum from index 1 to 3 → 4 + 6 + 8 = 18

Naive vs Efficient Approach

Naive Approach: Loop through the array for each query → O(n) per query Not ideal when you have
many queries.

Efficient Approach: Prefix Sum: Precompute cumulative sums so each query takes O(1) time.
Efficient Range Sum Queries
Let’s say we have:
arr = [2, 4, 6, 8, 10]

We build a prefix sum array prefix such that:

Index Prefix Sum

0 0 To find sum from index L to R:
1 2
sum = prefix[R + 1] - prefix[L]
2 6
3 12 Example:
Sum from index 1 to 3:
4 20
5 30 prefix[4] - prefix[1] = 20 - 2 = 18
Flowcharts and Algorithms

• Flowcharts are graphical representations of data, algorithms, or processes, providing a visual approach to
understanding code.
• Flowcharts illustrate step-by-step solutions to problems, making them useful for beginner programmers.
• Flowcharts help in debugging and troubleshooting issues.
• Flowchart consists of sequentially arranged boxes that depict the process flow.
• Since it visually represents an algorithm or workflow, it is easier to interpret and understand. However, to
create an effective Flowchart, certain standardised rules must be followed, ensuring clarity and
consistency across different professionals worldwide.
Flowcharts and Algorithms
Start / End Data or Input/Output

Process
Data Flow

Decision Stored Data

Flowcharts and Algorithms
Types of Flowcharts

[Link] Flowchart: This type of Flowchart shows all the activities that are involved in making a product. It
provides a pathway to analyze the product to be built. It is most commonly used in process engineering to
illustrate the relation between the major as well as minor components present in the product. It is used in
business product modelling to help understand employees about the project requirements and gain some insight
into the project.

[Link] Flowchart: It is used to analyze the data, specifically it helps in analyzing the structural details related to
the project. Using this Flowchart, one can easily understand the data inflow and outflow from the system. It is
most commonly used to manage data or to analyze information to and fro from the system.

[Link] Process Modelling Diagram: Using this Flowchart or diagram, one can analytically represent the
business process and help simplify the concepts needed to understand business activities and the flow of
information. This Flowchart illustrates the business process and models graphically which paves the way for
process improvement.
Flowcharts and Algorithms
Draw a Flowchart to find the greatest number among the 2 numbers.

Algorithm:
[Link]
[Link] 2 variables from user
[Link] check the condition If a > b, go to step 4, else go to step
5.
[Link] a is greater, go to step 6
[Link] b is greater
[Link]
Flowcharts and Algorithms
Draw a Flowchart to find the sum of 2 numbers.

Algorithm:
[Link]
[Link] A, B
3.C = A + B
[Link] C
[Link]