Problem Solving Techniques

Computer
◻ A computer is an electronic device that can be
programmed to process, store, and retrieve
data. It's designed to perform calculations and
solve problems quickly and efficiently. 💻
Problem

Algorithm

Flowchart

Program
Some Terminologies
◻ Algorithm / Flowchart
? A step-by-step procedure for solving a particular
problem.
? Independent of the programming language.

◻ Program
? A translation of the algorithm/flowchart into a form
that can be processed by a computer.
? Typically written in a high-level language like C,
C++, Java, etc.
History of Computer
❖ Abacus :- The Abacus is one of the earliest known calculating devices.
❖ Napier’s Bones (1617) – Invented by John Napier, used rods to simplify
multiplication and division.
❖ Slide Rule (1622) – Invented by William Oughtred, used for multiplication,
division, roots, logarithms, and trigonometry.
❖ Pascal’s Machine (1642) – Invented by Blaise Pascal, first mechanical
calculator for addition and subtraction.
❖ Leibniz Machine (1673) –Invented by Gottfried Wilhelm Leibniz,
improved Pascal’s machine, could do multiplication, division, and square
roots
❖ Computer - Computer was invented by Charles Babbage in 1823,
known as the “Father of Computer.” He designed the Difference Engine
and later the Analytical Engine, foundation of modern computers
Generations of Computers
First Generation (1940–1956)

❖ Used vacuum tubes

❖ Very large, slow, expensive
❖ Machine Language

Second Generation (1956–1963)

❖ Used transistors
❖ Smaller, faster, more reliable

Third Generation (1964–1971)

❖ Used Integrated Circuits (ICs)

❖ Faster, smaller, cheaper
Generations of Computers
Fourth Generation (1971–1980s)

❖ Used Microprocessors
❖ Personal computers developed
❖ VLSI - Very large scale integration
❖ Example: Apple, IBM PC

Fifth Generation (1980s–Present)

❖ Based on AI, parallel processing, supercomputers

❖ SLSI - Super large scale integration
❖ Use of Robotics, Expert Systems, Machine Learning
Components of Computer System:
1. Hardware

❖ Physical parts of computer (CPU, Monitor, Keyboard, Mouse,

Printer, Hard Disk).

2. Software

❖ System Software → OS (Windows, Linux, MacOS)., Device

Driver

❖ Application Software → MS Office, Browsers, Games.

 Data Types
◻ Three common data types used:

? Integer :: can store only whole numbers

■ Examples: 25, -56, 1, 0

? Floating-point :: can store numbers with fractional

values.
■ Examples: 3.14159, 5.0, -12345.345

? Character :: can store a character

■ Examples: ‘A’, ‘a’, ‘*’, ‘3’, ‘ ’, ‘+’
Data Types…

❖ How are they stored in memory?

➢ Integer ::
■ 16 bits
➢ Float ::
■ 32 bits
➢ Char ::
■ 8 bits (ASCII code)
■ 16 bits (UNICODE, used in Java)
Problems and Problem Instances

A problem is a general question to be solved. It defines the set of inputs, the desired
output, and the constraints that the output must satisfy. It's a template or a broad
category.

A problem instance is a specific occurrence of a problem. It provides concrete input

values for the problem.

● Problem: Sorting. The general question is, "How can we arrange a list of items in
a specific order (e.g., ascending or descending)?"
● Problem Instance: Sorting the list [8, 3, 1, 9]. This is a specific list of numbers
that you want to sort.
● Another Problem Instance: Sorting a list of names ["Zoe", "Alice", "Bob"].
Generalization and Special Cases

Generalization is the process of defining an algorithm that can solve a broader category of problems. It
involves identifying the common underlying principles of several similar problems and creating a single
solution that applies to all of them.

❖ Generalization Example:
➢ Special Case: Finding the maximum number in a list of integers.
➢ Generalization: Finding the maximum element in any type of collection where elements can be
compared (e.g., numbers, strings, dates). A generalized algorithm would work for all these cases.

Specialization is the opposite of generalization. A special case is a specific instance of a general problem that
might have a simpler or more efficient solution due to its specific characteristics.

❖ Special Case Example:

➢ General Problem: Sorting a list of numbers.
➢ Special Case: Sorting a list that is almost sorted. An algorithm like Insertion Sort is a good
example of an algorithm that performs exceptionally well on this special case, even though a
general-purpose algorithm like Merge Sort might be more efficient on a truly random list.
➢ Another Special Case: Finding the maximum element in a list that is already sorted. The solution
is simply to take the last element, which is much faster than iterating through the entire list.
Computational Problems

Introduction -
Computational problems are abstract models of tasks
computers can perform.
Each problem has:
❖ Input (given data)
❖ Output (solution)
❖ Relation/Rule connecting input → output.

Type of Computational Problem

❖ Decision Problems
❖ Search Problems
❖ Optimization Problems
❖ Enumeration Problems
 [Link] Problems

Definition: Output is always YES or NO.

Examples:
❖ Is a given number prime?
❖ Does a graph contain a cycle?
❖ Is there a path from A to B in a network?

Applications:
❖ Compiler checks → “Is this code correct?”
❖ Security → “Is this password valid?”

2. Search Problems
Definition: Find a specific solution from possible solutions.

Examples:

❖ Find the shortest path in a graph.

❖ Find an element in a sorted array (Binary Search).

Applications: Google search, database queries, AI search.

 [Link] Problems

Definition: Find the best possible solution among many valid solutions.
Examples:

❖ Traveling Salesman Problem (shortest route visiting all cities).

❖ Knapsack Problem (maximum value items in a bag with weight limit).

Applications:

❖ Logistics (delivery trucks use shortest route).

❖ Airlines (minimum cost scheduling).
❖ Finance (maximum profit investment).

4. Enumeration Problems
Generate all possible solutions.

Examples:

❖ Generate all possible passwords of length 4.

❖ List all seating arrangements in an exam hall.
❖ Find all spanning trees in a graph.

Applications: 1 Cryptography (brute force attacks). [Link] testing (all input combinations).
Classification of Problems

Introduction
❖ Computational problems can be classified by how difficult they are to
solve.
❖ Some problems can be solved quickly (efficient).
❖ Some problems are very hard (may take years even for
supercomputers).
Type of Classification of Problems
❖ Tractable vs. Intractable,
❖ P, NP,
❖ NP-Complete,
❖ NP-Hard,
❖ Reduction
Tractable vs. Intractable Problems

Tractable Problems
❖ Can be solved in polynomial time (e.g., O(n), O(n²), O(n³)).
❖ Considered feasible or efficient.
❖ Example: Sorting numbers (O(n log n)).

Intractable Problems
❖ Require super-polynomial / exponential time (e.g., O(2^n), O(n!)).
❖ Very hard to solve for large inputs.
❖ Example: Traveling Salesman Problem (brute force).
The Class P

Definition: Problems that can be solved in polynomial time.

Examples:

❖ Checking if a number is prime (efficient algorithms exist).

❖ Shortest path in a graph (Dijkstra’s algorithm).
❖ Sorting numbers.

The Class NP(Nondeterministic Polynomial)

Definition: Problems for which a given solution can be verified in polynomial time, even
if finding it is hard.

Examples:

❖ Sudoku puzzle → If someone gives a solution, you can check it quickly.

❖ Traveling Salesman → If someone gives a tour, we can check its distance easily.
❖ Boolean satisfiability (SAT).
NP-Complete Problems

Definition: Hardest problems in NP. If you can solve one NP-Complete problem quickly,
you can solve all NP problems quickly.

Examples:

❖ Traveling Salesman (decision version: is there a tour ≤ k distance?).

❖ Subset Sum Problem.
❖ 3-SAT Problem.

NP-Hard Problems
Definition: At least as hard as NP-Complete, but not necessarily in NP (may not even have
a solution to verify).

Examples:

❖ Optimization version of Traveling Salesman (find the shortest route, not just yes/no).
❖ Halting Problem (decide if a program will stop or run forever).
 Problem Reduction

Definition: Converting one problem into another.

❖ If Problem A can be reduced to Problem B, and B is easy, then A is also easy.

❖ Used to prove NP-Completeness.

Example:

❖ SAT → 3-SAT → Clique → Vertex Cover (reductions used to show

NP-Completeness).

SAT (Boolean Satisfiability Problem)

❖ SAT = Boolean Satisfiability Problem
❖ Can we assign True/False values to variables of a Boolean formula so that the whole
formula becomes True?
Analysis of Problems

Introduction

❖ Before solving a problem, we must analyze it properly.

❖ Poor analysis → Wrong algorithm or inefficient solution.
❖ Good analysis → Correct, efficient, reusable solution.

Importance of Problem Analysis

❖ Clarity: Understand exactly what is being asked.
❖ Correctness: Ensures solution solves the real problem.
❖ Efficiency: Helps choose the right algorithm/data structure.
❖ Scalability: Ensures solution works for large inputs.
❖ Reusability: A well-analyzed problem can be adapted for future problems.
Problem Modeling (Real World → Abstract)

❖ Problem Modeling = Representing real-world problem in computer-friendly

terms.
❖ Steps:
➢ Identify the input (data given).
➢ Identify the output (result required).
➢ Define the constraints (rules, limits).
➢ Choose the representation (mathematical, logical, or graph model).

Example – Real World → Abstract:

❖ Real World: “Find the shortest path from Surat to Delhi.”

❖ Abstract: Graph with cities as nodes and distances as edges → Apply Dijkstra’s
Algorithm.
Complexity Considerations

❖ Time Complexity: How much time an algorithm needs (as input grows).
❖ Space Complexity: How much memory it uses.
❖ Trade-off: Faster algorithms may use more memory, and memory-saving
ones may run slower.
Why complexity matters?
❖ Small input → Any algorithm works.
❖ Large input → Only efficient algorithms survive.
Examples of Simple vs. Complex Problems

Simple Problems:
❖ Checking if a number is even or odd (O(1)).
❖ Finding the maximum in a small list (O(n)).

Complex Problems:
❖ Traveling Salesman Problem (O(n!)).
❖ Protein structure prediction (NP-hard).
❖ Cryptography (large prime factorization).
Solution Approaches

❖ Many problems can be solved in multiple ways.

❖ Choice of solution approach affects efficiency and feasibility.
❖ Today we study 5 main approaches used in algorithm design.
Type of Solution Approaches
1. Brute Force
2. Divide & Conquer
3. Greedy Algorithms
4. Dynamic Programming
5. Backtracking & Branch-and-Bound
1. Brute Force

❖ Linear Search → Check every element one by one.

❖ Password Cracking → Try all possible combinations.
❖ Traveling Salesman (brute force) → Test all possible tours.

Complexity: Often O(n!) or O(2^n).

2. Divide and Conquer

● Idea: Break the problem into smaller subproblems, solve them, and combine results.
● Usually reduces time complexity.

Divide and Conquer (Examples)

❖ Merge Sort (O(n log n))

❖ Binary Search (O(log n))
❖ Quick Sort (average O(n log n))

Steps:

1. Divide → Split into smaller subproblems.

2. Conquer → Solve subproblems.
3. Combine → Merge solutions.
3. Greedy Algorithms

Concept: An approach that makes the locally optimal choice at each step with the hope of finding a globally
optimal solution. It focuses on making the best immediate decision without considering future consequences.

Characteristics:

❖ Makes a series of locally optimal choices.

❖ Doesn't always find the globally optimal solution. The "greedy" choice might not be the best in the
long run.
❖ Simple and intuitive to implement.
❖ Works best for specific types of problems that have the "greedy choice property" and "optimal
substructure."

Examples:

❖ Coin Change Problem: To make change for a certain amount, a greedy algorithm would always choose
the largest denomination coin possible at each step. This works in many currency systems but not all.
❖ Dijkstra's Algorithm: Finds the shortest path between two nodes in a graph by always picking the
closest unvisited node.
❖ Prim's and Kruskal's Algorithms: Used to find a minimum spanning tree.
4. Dynamic Programming

Concept: A method for solving complex problems by breaking them down into simpler overlapping
subproblems. It solves each subproblem only once and stores the results in a table or memoization array to
avoid recomputing them.

Characteristics:

❖ Requires two key properties:

➢ Overlapping Subproblems: The same subproblems are solved multiple times.
➢ Optimal Substructure: The optimal solution to the problem can be constructed from the optimal
solutions of its subproblems.
❖ Uses memoization (top-down) or tabulation (bottom-up) to store results.
❖ More efficient than a naive recursive approach because it avoids redundant calculations.

Examples:

❖ Fibonacci Sequence: The calculation of F5 needs F4 and F3. The calculation of F4 needs F3 and F2.
Notice the overlapping subproblem of F3. Dynamic programming stores the values to avoid
recomputing them.
❖ Knapsack Problem: Finds the most valuable combination of items that can fit into a bag of a certain
weight capacity.
❖ Longest Common Subsequence: Finds the longest sequence of characters common to two strings.
5. Backtracking & Branch-and-Bound

Concept: Both are systematic search techniques used to find solutions to problems, often in a tree-like
structure. They explore different paths and use a pruning strategy to avoid unnecessary searches.

Backtracking

Concept: A general algorithmic technique for solving problems recursively by trying to build a
solution incrementally. If a path fails to lead to a valid solution, it "backtracks" (reverts) to a previous
state and tries a different path.

Characteristics:

❖ Used for solving constraint satisfaction problems.

❖ Explores the search space using a depth-first search (DFS) approach.
❖ Prunes invalid or non-promising paths to reduce the search space.

Examples:

❖ N-Queens Problem: Placing N chess queens on an N×N chessboard so that no two queens
threaten each other. Backtracking explores different placements and reverts when a conflict is
found.
❖ Sudoku Solver: Tries to place numbers and backtracks if a placement violates the rules.
5. Backtracking & Branch-and-Bound

Branch-and-Bound

Concept: An optimization technique that extends backtracking by keeping track of the best solution
found so far. It uses "bounding" to prune branches of the search tree that cannot possibly lead to a
better solution than the current best one.

Characteristics:

❖ Used for optimization problems (finding the minimum or maximum).

❖ Maintains a current "bound" on the best solution found so far.
❖ Prunes branches of the search tree that are guaranteed to have a worse solution than the current
bound.

Examples:

❖ Traveling Salesperson Problem: A branch-and-bound algorithm would explore different routes.

If it finds a partial route whose cost is already higher than the best full route found so far, it
prunes that branch and doesn't explore it further.
❖ Integer Programming: Solving optimization problems where the variables must be integers
Algorithm Development

Steps in Algorithm Development

Developing an algorithm is a systematic process. The key steps are:

1. Problem Definition: Clearly define the problem, including the input, output, and
constraints.
2. Model Building: Create a conceptual model to represent the data and relationships.
3. Algorithm Design: Brainstorm and choose a strategy (e.g., brute force, greedy).
4. Algorithm Specification: Describe the algorithm's logic using pseudocode or
flowcharts.
5. Algorithm Analysis: Analyze its performance for time and space complexity,
typically using Big O notation like O(n) or O(n2).
6. Implementation & Testing: Code the algorithm and test it thoroughly with various
data.
Problem solving
◻ Step 1:
? Clearly specify the problem to be solved.
◻ Step 2:
? Draw flowchart or write algorithm.
◻ Step 3:
? Convert flowchart (algorithm) into program code.
◻ Step 4:
? Compile the program into object code.
◻ Step 5:
? Execute the program.
Flowchart

A pictorial representation of an algorithm is

called a flowchart.

In a flowchart, each step of the algorithm is

represented using different shapes, with each shape
having a specific meaning (such as process,
decision, input/output, etc.).
Flowchart: basic symbols

Computation /
Processing

Input / Output

Decision Box

Start / Stop
Flowchart: basic symbols…

Flow of
control

Connector
Example 1: Adding three numbers
START

READ A,
B, C

S=A+B+C

OUTPUT
S

STOP
Example 2: Larger of two numbers
START

READ X,
Y

YES IS NO
X>Y?

OUTPUT OUTPUT
X Y

STOP STOP
Example 3: Largest of three numbers
START

READ A,
B, C

YES IS NO
A > B?

A>C B>C
YES NO YES NO

A C B C

Stop
Example :- Try Yourself

1. Write a even or odd

2. Area of circle
3. Circumference of circle
4. Perimeter of rectangle
5. Create a flowchart to check whether a person is
eligible to vote or not.
6. Create a flowchart to convert temperature from
Celsius to Fahrenheit. ( Fahrenheit = (Celsius ×
9/5) + 32)