Jain Global Campus

Module 1: Computational
Problems
Course Name: Introduction to Problem Solving
Course Code: New
Table of Content

• Aim – Understanding the purpose and • Did You Know*

efficacy of object oriented programming • Summary
• Introduction • Terminal Questions
• Objective – unit wise split into 3 to 5 • Reference Links*
• Sections/Topics • Q&A*
• Self Assessments – 3 per section • Thank You
• Activities – 1 per section
*not mandatory
 a. Provide an understanding of basic computational problems such as

sorting, searching, selection, GCD, Fibonacci, factorial, primality, and

factorization.

b. Equip students with knowledge of algorithm design strategies including

brute force, divide and conquer, greedy methods, dynamic

programming, and backtracking.

c. Enable students to analyze problems in terms of input, output,

Objectiv
efficiency, and correctness, and select suitable approaches.
e
d. Build the ability to represent problems using flowcharts, pseudocode,

and structured methods.

e. Lay the foundation for solving real-world problems in domains like data

science, cryptography, optimization, and artificial intelligence.

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.
What are Computational Problems?
• A computational problem is a precisely defined question that can be
solved using algorithms.
• Each problem has:
• Input: The data provided to the algorithm.
• Output: The expected result produced by the algorithm.
• These problems act as the foundation of algorithm design and analysis.
• Examples: Sorting a list of numbers, Searching for an element in a
dataset, Calculating GCD of two integers, Testing whether a number is
prime
Importance of Computational Problems
• Essential for developing problem-solving skills in computer [Link]
in designing algorithms that are:
• Correct (produces the right output)
• Efficient (uses minimal time and memory)
• Applications across domains:
• Data Analysis: Handling and organizing large datasets.
• Artificial Intelligence: Pattern recognition, decision-making.
• Cryptography: Ensuring secure communication.
• Optimization: Efficient allocation of resources.
Types of Computational Problems
• 1. Decision Problem: Answer is Yes/No.
• Example: “Given n, is it even?” or “Is n prime?”
• 2. Search Problem: Find one or more values that satisfy a condition.
• Example: Finding a path between two locations on a map.
• 3. Counting Problem: Determine the number of possible solutions to
a search problem.
• Example: Counting the number of valid paths in a graph.
• 4. Optimization Problem: Find the best solution under given criteria.
• Example: Finding the shortest or fastest route between two cities.
Sorting
• Definition: Rearranging data items into a specific order
(ascending/descending).
• Key Algorithms:
• Bubble Sort – simple but inefficient.
• Merge Sort – divide and conquer, O(n log n).
• Quick Sort – efficient in practice, average O(n log n).
• Heap Sort – based on heap data structure.
• Applications:
• Preparing data for efficient searching.
• Ranking students, results, or web [Link] large datasets for
analysis.
Searching
• Definition: Finding the position of a target element in a dataset.
• Techniques:
• Linear Search: Simple, O(n), checks one by one.
• Binary Search: Requires sorted input, O(log n).
• Applications:
• Database query processing.
• Real-time systems (e.g., flight information systems).File retrieval in
operating systems.
Nearest-Neighbour Search
• Definition: Nearest-neighbour search (NNS) is a crucial problem in
which the goal is to find the point in a given dataset that is closest or most
similar to a given query point. The "closeness" is measured using a
distance metric, such as Euclidean distance.
• Example: Recommendation systems use NNS to suggest products to a
user. For example, by finding other users with similar purchase histories,
the system can recommend products that those "neighbors" have bought.
Nearest-Neighbour Search
k-th Smallest Selection
• Definition:
• Finding the k-th smallest element in a dataset.
• Algorithms:
• QuickSelect
• Heap-based methods
• Applications:
• Median finding
• Statistical analysis
• Order statistics problems
 k-th Smallest Selection

et.
Greatest Common Divisor (GCD)
• Definition:
• Largest integer that divides two numbers without remainder.
• Example: The GCD of 12 and 18 is 6, because 6 is the largest number
that divides both 12 (12=6×2) and 18 (18=6×3).
• Algorithms: Euclidean Algorithm (efficient and widely used)
• Applications:
• Cryptography
• Simplifying fractions
• Modular arithmetic
 Greatest Common Divisor (GCD)

.
Fibonacci Sequence
• Definition: Sequence where each term = sum of the previous two.
• Example: The sequence begins 0, 1, 1, 2, 3, 5, 8, ...
• Formula: F(n) = F(n-1) + F(n-2)
• Computation:
• Recursive method (inefficient), Dynamic Programming (efficient)
• Applications:
• Algorithm analysis
• Natural patterns (spirals, shells)
• Financial models
Factorial
• Definition: Product of all positive integers ≤ n.
• Example: The factorial of 5 (5!) is calculated as 5×4×3×2×1=120
• Formula: n! = n × (n-1) × … × 1, with 0! = 1
• Applications:
• Probability and combinatorics
• Complexity analysis
• Binomial theorem
Primality
• Primality is the problem of determining whether a given integer is a
prime number. A prime number is a number greater than 1 that has no
positive divisors other than 1 and itself. This problem is central to
cryptography, particularly in public-key systems like RSA.
• Example: To check if the number 13 is prime, you would test if it is
divisible by any integer from 2 up to its square root. Since it is not, 13 is a
prime number.
Integer Factorization
• Integer factorization is the decomposition of a composite integer into its
prime factors.
• This problem is considered computationally difficult for very large
numbers, which is the basis for the security of many cryptographic
algorithms.
• Example:
• The prime factors of the number 30 are 2, 3, and 5, since 30 = 2×3×5
• 60 = 2 × 2 × 3 × 5
• 72 = 2 × 2 × 2 × 3 × 3
Polynomial Identity Testing
• Polynomial Identity Testing is the problem of checking whether two
polynomials are identically equal (i.e., they give the same output for all
possible inputs).
• Example 1: (x+2)(x+3) and x2+5x+6 - They are identical polynomials.
• Example 2:
Check if, (x+1)2 and x2+2x(x+1)^2 are not identical.
 Discrete Logarithm
• In normal logarithms, we solve equations like:

• In discrete logarithms, the same concept is applied but in modular

arithmetic.
• So, the discrete logarithm problem is:

• Find 𝑥.
• Here, 𝑝p = a prime number (modulus), 𝑔g = base (called a generator),
• 𝑦y = result,𝑥x = discrete logarithm (unknown exponent).
Ref: [Link]
 Discrete Logarithm

Ref: [Link]
Discrete Logarithm
• Suppose we want to solve:

• We need to find 𝑥.
Solution:
Discrete Logarithm
Shortest Path
• The Shortest Path problem involves finding a path between two vertices
in a graph such that the sum of the weights of its constituent edges is
minimized. This problem has numerous real-world applications.
• Types:
• Single-source shortest path: Finds the shortest path from a single
source vertex to all other vertices.
• All-pairs shortest path: Finds the shortest paths between all pairs of
vertices.
• Example: A GPS navigation system uses a shortest path algorithm to
find the quickest route from your current location to your destination.
Shortest Path
Hamiltonian Cycle
• Definition: A Hamiltonian Cycle is a cycle in a graph that visits each
vertex exactly once. The problem is to determine if such a cycle exists.
This is an NP-complete problem, meaning no efficient algorithm is known
to solve it for all possible graphs.
• Example: A traveling salesman who needs to visit every city on a map
exactly once before returning to his starting point is trying to find a
Hamiltonian cycle.
• Applications: routing, circuit design.
Hamiltonian Cycle
Hamiltonian Cycle
Integer Programming
• Integer Programming is a mathematical optimization problem where
some or all of the variables are restricted to be integers. It is a powerful
tool for modeling and solving complex decision-making problems,
especially those involving discrete choices.
• Simple Example: Suppose a factory makes chairs (profit = 50) and tables
(profit = 80). Each chair requires 2 hours of work and each table requires
3 hours. If there are 10 work hours available, how many chairs (x) and
tables (y) should be made?
Integer Programming
• Constraint: 2x + 3y ≤ 10, x,y must be integers.
• Possible solutions: (x=2,y=2) → Profit=260, (x=5,y=0) → Profit=250.
• Best solution is making 2 chairs and 2 tables.
• Applications: Workforce scheduling, production planning, logistics.
Knapsack problem
• The Knapsack problem is a classic optimization problem where you are
given a set of items, each with a weight and a value, and you must
determine which items to include in a collection so that the total weight is
less than or equal to a given limit and the total value is as large as
possible.
• Types:
• 0/1 Knapsack: Each item can either be taken or left; no partial items.
• Fractional Knapsack: Parts of an item can be taken.
• Example: A hiker needs to choose which items to pack in their knapsack
to maximize the value without exceeding the weight limit.
• Applications: Budget allocation, cargo loading, investment decisions.
Knapsack problem
3-SAT Problem
• Concept: A satisfiability problem where each clause has exactly 3
literals. The task is to check if there exists an assignment of true/false
values to variables that makes the formula true.
• Example: (x ∨ y ∨ z) ∧ (¬x ∨ y ∨ z). If x=false, y=true, z=false,
formula is satisfied.
• Importance: 3-SAT is one of the first NP-complete problems, meaning if
we can solve it efficiently, we can solve all NP problems efficiently.
• Applications: Circuit verification, artificial intelligence reasoning,
optimization problems.
Clique Problem
• Concept: A clique is a subset of vertices in a graph where every two
vertices are directly connected by an edge.
• Example: In a graph with vertices {A,B,C,D}, if edges {AB, AC, BC} exist,
then {A,B,C} is a clique.
• Importance: Clique finding is computationally hard for large graphs.
• Applications: Social network analysis (finding tightly connected groups),
bioinformatics (protein interaction networks).
Clique Problem
Pattern Matching
Vertex Cover
• Vertex Cover: The problem of finding the smallest set of vertices in a
graph such that every edge is incident to at least one vertex in the set.
• Example: Placing security cameras at the minimum number of street
intersections to monitor all streets.
Vertex Cover
Minimum Spanning Tree (MST)
• Concept: A spanning tree of a graph connects all vertices with minimum
possible edge weight.
• Algorithms: Kruskal’s (greedy, sorts edges), Prim’s (grows MST from a
starting node).
• Example: Graph edges A-B=1, B-C=2, A-C=3. MST = {A-B, B-C} with
total weight 3.
• Applications: Designing least-cost networks (electricity grids, computer
networks), clustering.
Minimum Spanning Tree (MST)
Maximum Flow
• Maximum Flow: Calculating the maximum amount of "flow" that can
pass from a source to a sink in a flow network.
• The flow represents a limited resource, such as traffic or data.
• Example: Determining the maximum amount of traffic that can flow
through a road network during rush hour.
Maximum Flow
Undirected s-t Reachability
• Undirected s-t Reachability: Determining if a path exists between two
specified vertices, s and t, in an undirected graph.
• Example: Checking if two locations are connected on a map.
Pattern Matching
• Concept: Process of finding one string (pattern) within another string
(text).
• Algorithms: Naive search, Knuth-Morris-Pratt (KMP), Rabin-Karp.
• Example: Text = "ABABCA", Pattern = "ABC" → Found starting at index
2.
• Applications: Search engines, plagiarism detection, DNA sequence
analysis, text editors
Longest Common Subsequence (LCS)
• Finding the longest subsequence that is common to all sequences in a
set.
• A subsequence does not have to be contiguous.
• Example:
• Input: s1 = "ABC", s2 = "ACD"
• Output: 2
• Explanation: The longest subsequence which is present in both strings is
"AC".
• Input: s1 = "AGGTAB", s2 = "GXTXAYB"
• Output: 4
• Explanation: The longest common subsequence is "GTAB".
Longest Common Subsequence (LCS)
• Input: s1 = "ABC", s2 = "CBA"
• Output: 1
• Explanation: There are three longest common subsequences of length 1,
"A", "B" and "C".
Travelling Salesman Problem
• Finding the shortest possible route that visits each city exactly once and
returns to the origin city.
• It's a classic NP-hard [Link]: A delivery driver finding the most
efficient route to visit several delivery locations.

1 -> 2 = 10
2 -> 4 = 25
4 -> 3 = 30
3 -> 1 = 15
Output: 80
Recommendation Systems
• Recommendation Systems: Systems that predict user preferences and
suggest relevant items.
• They are widely used in e-commerce and streaming services.
• Types: Collaborative filtering and content-based filtering.
• Example: Netflix recommending movies based on a user's viewing
history.
Recommendation Systems
Recommendation Systems
Job scheduling
• Job scheduling algorithms are methods used to assign a set of tasks
(jobs) to a set of resources (machines or processors) with the goal of
optimizing a specific objective.
• The main objective is to maximize efficiency and minimize the time it
takes to complete all jobs.
Types of Scheduling Algorithms
• First-Come, First-Served (FCFS):
• This is the simplest scheduling algorithm. It executes jobs in the order
they arrive. It's easy to implement but can be inefficient, as a short job
might have to wait for a very long job to finish.
Types of Scheduling Algorithms
• First-Come, First-Served (FCFS):
Types of Scheduling Algorithms
• Shortest Job Next (SJN):
• This algorithm prioritizes jobs with the shortest execution time. It is
designed to minimize the average waiting time for all jobs.
Types of Scheduling Algorithms
• Priority Scheduling:
• In this approach, each job is assigned a priority, and the scheduler
always executes the job with the highest priority first.
• This can be useful for important tasks but may lead to "starvation,"
where low-priority jobs never get to run.
Types of Scheduling Algorithms
• Round Robin:
• This method gives each job a small, equal time slice to run in a cyclic
fashion.
• Once a job's time slice is up, it is moved to the back of the queue.
• It provides a fair distribution of CPU time among all jobs, making it
ideal for interactive systems.
Types of Scheduling Algorithms
• Round Robin:
Efficient Range Sum Queries
• Concept: The problem of quickly calculating the sum of elements
within a specified range of an array. A simple approach would be to
iterate and sum the elements for each query, but this is slow for large
datasets.
• Example: Given a daily sales array [10, 15, 8, 20, 5], you could query
the sum from day 2 to day 4 (indices 1 to 3), which would be
15+8+20=43.
• Application: This technique is used for quick data analysis, such as
finding total sales for a specific period. Data structures like a prefix
sum array can answer these queries in constant time after an initial
setup.
Foundational Tools for Problem Solving
• Flowcharts: A visual representation of a process or a workflow. It
uses shapes connected by arrows to illustrate the sequence of steps,
decisions, and operations. This helps in conceptualizing program
logic.
• Example: A flowchart can model a simple decision like checking if a
number is even or odd.
Foundational Tools for Problem Solving
Algorithms
• Algorithms: A well-defined, step-by-step procedure for solving a
problem. Algorithms are language-independent and must be correct,
efficient, and terminate after a finite number of steps.
• Example: The Euclidean algorithm for finding the Greatest Common
Divisor (GCD).
Algorithms - Example
Pseudocode
• Pseudocode is a simplified, informal way of writing out an algorithm. It
uses a mix of natural language and programming-like syntax to
describe the steps of an algorithm, making it easier to understand
without getting bogged down in the strict rules of a specific
programming language. It acts as a bridge between a
human-readable algorithm and computer-executable code.
Pseudocode
• Example:
• To find the maximum number in a list of numbers, you could use
this pseudocode:
Logical Reasoning
• Logical reasoning is the process of using a systematic approach to
arrive at a conclusion.
• It involves breaking down a problem into smaller, manageable parts,
identifying patterns, and using deductive and inductive reasoning to
formulate a solution.
• This is the thinking process that occurs before you start writing an
algorithm.
Logical Reasoning
• Example:
• When solving a puzzle, you would use logical reasoning to analyze
the pieces, understand the constraints, and formulate a strategy to
assemble them. You'd break the problem down by, for instance,
finding all the corner pieces first. Then, you'd use
1. Deductive reasoning to place pieces based on their specific
shapes. You might also use.
2. inductive reasoning to form a hypothesis about how different
sections of the puzzle connect, based on observations of patterns
Problem-Solving Approaches
• 1. Brute Force: A straightforward method that systematically checks
all possible solutions to find the correct one. It's often simple to think
of, but can be very inefficient for large problems.
• Example: To find the smallest number in an array, a brute-force
approach would iterate through every element and compare it with
a variable storing the smallest value found so far.
Brute Force
Brute Force
Problem-Solving Approaches
• 2. Divide and Conquer:
• Breaks a complex problem into smaller, more manageable
subproblems of the same type.
• It then solves these subproblems independently and combines
their solutions to solve the original problem.
Problem-Solving Approaches
Problem-Solving Approaches
• 3. Greedy Methods:
• Makes the locally optimal choice at each stage with the hope of
finding a global optimum.
• This approach doesn't always guarantee the best solution.
• Example: Giving change using the fewest coins possible. A
greedy approach always uses the largest denomination coin
available.
 available.
Problem-Solving Approaches
Problem-Solving Approaches
• 4. Backtracking:
• A recursive technique that builds a solution incrementally. If the
current partial solution cannot be completed, the algorithm
"backtracks" to the previous step and tries a different path.
• Example: Solving a Sudoku puzzle. You place a number and if it
leads to a dead end, you backtrack and try a different number.
Problem-Solving Approaches
• 4. Backtracking
Problem-Solving Approaches
• 5. Dynamic Programming:
• Solves complex problems by breaking them down into simpler,
overlapping subproblems. It stores the results of these
subproblems to avoid recomputing them, which can significantly
improve efficiency.
• Example: Calculating the Fibonacci sequence by storing
previously calculated values to avoid redundant computations.
Problem-Solving Approaches
• 5. Dynamic Programming
Thank you