IMPORTANT SHORT NOTES:

[Link] Search

A heuristic search is a search technique that uses additional knowledge (called a heuristic) to
guide the search toward a solution more efficiently than an uninformed search.

A heuristic is an estimate of how close a state is to the goal. It helps the algorithm decide which
path to explore first.

Definition

A heuristic function (h(n)) estimates the cost or distance from a node (n) to the goal state.

The search algorithm chooses the node that appears most promising according to the heuristic
value.

Example

Suppose you want to travel from city A to city G.

 (h(A) = 10)
 (h(B) = 6)
 (h(C) = 4)
 (h(G) = 0)

The algorithm prefers cities with smaller heuristic values because they are estimated to be closer
to the destination.

Steps of Heuristic Search

1. Start from the initial state.

2. Evaluate neighboring states using the heuristic function (h(n)).
3. Select the most promising state.
4. Repeat until the goal state is reached.

Advantages

 Reduces the search space.

 Often finds solutions faster than uninformed methods.
  Useful for complex optimization problems.

Disadvantages

 Does not always guarantee the optimal solution.

 Performance depends on the quality of the heuristic function.
 A poor heuristic may lead to inefficient searches.

Applications

 Travelling Salesman Problem (TSP)

 Path finding and navigation
 Artificial Intelligence
 Game playing (Chess, Tic-Tac-Toe)
 Robot navigation

2-Mark Definition

Heuristic Search: A search technique that uses a heuristic function (h(n)) to estimate the
distance or cost from a current state to the goal and guides the search toward the most promising
solution path.

2. Randomized Algorithm

A randomized algorithm is an algorithm that uses random numbers or random choices

during its execution to make decisions. Because of the randomness, the algorithm may produce
different execution paths (and sometimes different running times) for the same input.

Definition

A randomized algorithm is an algorithm that employs a random process as part of its logic to
solve a problem.

Example: Randomized Quick Sort

In Quick Sort, instead of always choosing the first or last element as the pivot, a random
element is chosen as the pivot.

This random choice reduces the chance of encountering the worst-case time complexity.

Types of Randomized Algorithms

1. Las Vegas Algorithms

 Always produce the correct result.

 Running time is random.
 Example: Randomized Quick Sort.

2. Monte Carlo Algorithms

 Running time is fixed or bounded.

 May produce an incorrect result with a small probability.
 Example: Probabilistic primality testing.

Advantages

 Often simpler to design and implement.

 Can achieve better average-case performance.
 Helps avoid worst-case inputs.
 Useful for large and complex problems.

Disadvantages

 Results or running time may vary from run to run.

 Some algorithms may have a small probability of error.
 Analysis can be more difficult than deterministic algorithms.

Applications

 Quick Sort
 Primality Testing
 Load Balancing
 Cryptography
  Machine Learning
 Network Algorithms

2-Mark Definition

Randomized Algorithm: An algorithm that uses random numbers or random choices during
execution to solve a problem. Its running time or output may depend on the random choices
made by the algorithm.

3. Brute Force Algorithm

A Brute Force Algorithm is a straightforward problem-solving technique that tries all possible
solutions and selects the correct or best one.

It does not use any special optimization or shortcuts. Instead, it systematically examines every
possible candidate until the solution is found.

Definition

A brute force algorithm solves a problem by exhaustively checking all possible solutions and
choosing the valid or optimal one.

Example 1: Searching an Element

To find a number in an array:

Array: [5, 8, 2, 9, 4]
Search: 9

Check each element one by one:

 5 → No
 8 → No
 2 → No
 9 → Yes

This is a brute force approach called Linear Search.

Example 2: Travelling Salesman Problem (TSP)

For (n) cities:

1. Generate all possible tours.

2. Compute the cost of each tour.
3. Choose the tour with the minimum cost.

For 4 cities:

A-B-C-D-A
A-B-D-C-A
A-C-B-D-A
...

All possible tours are checked.

Time Complexity: O(n!)

General Steps

1. Generate all possible solutions.

2. Test each solution.
3. Select the valid or optimal solution.

Advantages

 Simple and easy to understand.

 Always finds the correct solution if one exists.
 Useful for small-sized problems.

Disadvantages

 Very inefficient for large inputs.

 Requires high computation time.
 Often impractical for optimization problems.

Applications
  Linear Search
 Selection Sort
 Bubble Sort
 Travelling Salesman Problem (exhaustive search)
 Password Cracking
 String Matching

Time Complexity

Usually high because all possibilities are examined.

Problem Time Complexity

Linear Search O(n)
String Matching O(nm)
TSP (Brute Force) O(n!)

2-Mark Definition

Brute Force Algorithm: A simple problem-solving technique that tries all possible solutions
and selects the correct or optimal one. It guarantees finding a solution but is often inefficient for
large inputs.

[Link]'s Theorem

Cook's Theorem (also called the Cook–Levin Theorem) is a fundamental result in

Computational Complexity Theory.

It states that the Boolean Satisfiability Problem (SAT) is NP-Complete.

Statement of Cook's Theorem

SAT is NP-Complete.

That is:

1. SAT belongs to NP.

2. Every problem in NP can be polynomial-time reduced to SAT.
Explanation

 SAT (Boolean Satisfiability Problem):

Given a Boolean formula, determine whether there exists an assignment of truth values
(True/False) to the variables that makes the formula true.
 Cook's theorem shows that any problem whose solution can be verified in polynomial
time can be transformed into a SAT instance in polynomial time.

Importance

 It was the first NP-Complete problem to be identified.

 It provides the basis for proving many other problems NP-Complete.
 If SAT can be solved in polynomial time, then every NP problem can be solved in
polynomial time ((P = NP)).

Outline of the Proof

1. Show that SAT ∈ NP:

o Given a truth assignment, we can verify in polynomial time whether the formula
is satisfied.
2. Show that every language in NP reduces to SAT:
o Consider a nondeterministic Turing machine that solves an NP problem in
polynomial time.
o Construct a Boolean formula that represents the machine's computation.
o The formula is satisfiable if and only if the machine accepts the input.
o This construction takes polynomial time.

Therefore, SAT is NP-Complete.

Applications

 Complexity theory
 NP-Completeness proofs
 Artificial Intelligence
 Optimization problems
 Circuit design and verification
5-Mark Answer

Cook's Theorem: SAT is NP-Complete. It states that every problem in NP can be reduced to the
Boolean Satisfiability Problem (SAT) in polynomial time. The theorem proves that SAT belongs
to NP and that all NP problems can be transformed into SAT instances. It was the first NP-
Complete problem and forms the foundation for NP-Completeness theory.

[Link] Closure

The transitive closure of a graph or relation is used to determine whether a path exists between
every pair of vertices.

For a graph (G), the transitive closure (G^*) contains an edge ((u,v)) if there is a path from
vertex (u) to vertex (v) in the original graph.

Definition

The transitive closure of a relation (R) on a set (A) is the smallest transitive relation that contains
(R).

Example

Consider the directed graph:

A → B
B → C

Since there is a path from A to C through B, the transitive closure adds the edge:

A → C

Thus, the transitive closure becomes:

A → B
B → C
A → C

Warshall's Algorithm

The transitive closure of a graph can be computed efficiently using Warshall's Algorithm,
which has time complexity:
[
O(n^3)
]

where (n) is the number of vertices.

Applications

 Finding reachability in graphs

 Database query processing
 Network routing
 Program analysis
 Dependency analysis

Short Note (5 Marks)

Transitive closure of a graph or relation represents reachability among vertices. If there is a path
from vertex (u) to vertex (v), then the transitive closure contains the edge ((u,v)). It is commonly
represented using a reachability matrix and can be computed using Warshall's Algorithm in
(O(n^3)) time. Transitive closure is widely used in graph theory, databases, and network
analysis.

6. P and NP Classes

P and NP are important complexity classes used to classify computational problems based on the
time required to solve them.

1. Class P (Polynomial Time)

A problem belongs to P if it can be solved by a deterministic algorithm in polynomial time.

Definition

[
P = {\text{Problems solvable in polynomial time}}
]

Polynomial time means the running time is of the form:

[
O(n),\ O(n^2),\ O(n^3),\ \ldots
]

Examples

 Linear Search
 Binary Search
 Merge Sort
 Shortest Path Problem (Dijkstra's Algorithm)

2. Class NP (Nondeterministic Polynomial Time)

A problem belongs to NP if a proposed solution can be verified in polynomial time by a

deterministic algorithm.

Definition

[
NP = {\text{Problems whose solutions can be verified in polynomial time}}
]

A problem may be difficult to solve, but once a solution is given, checking it is easy.

Examples

 SAT (Boolean Satisfiability Problem)

 Clique Problem
 Hamiltonian Cycle Problem
 Travelling Salesman Problem (Decision Version)

Difference Between P and NP

P NP

Solutions can be found in polynomial

Solutions can be verified in polynomial time.
time.

Easier class of problems. Potentially harder class of problems.

Can be solved by a nondeterministic machine in polynomial

Uses deterministic algorithms.
time.

Examples: Sorting, Searching. Examples: SAT, Clique, Hamiltonian Cycle.

Relationship Between P and NP

[
P \subseteq NP
]

Every problem that can be solved quickly can also be verified quickly.

The famous open question is:

[
P \stackrel{?}{=} NP
]

No one currently knows whether (P = NP) or (P \neq NP).

Diagram
NP
__________
| |
| P |
|__________|

P is a subset of NP.

5-Mark Answer

P (Polynomial Time) is the class of decision problems that can be solved by a deterministic
algorithm in polynomial time. NP (Nondeterministic Polynomial Time) is the class of decision
problems whose solutions can be verified in polynomial time. Every problem in P is also in NP,
so (P \subseteq NP). Whether (P = NP) remains one of the most important unsolved problems in
computer science.

7. NPSPACE (Nondeterministic Polynomial Space)

NPSPACE is the class of decision problems that can be solved by a nondeterministic Turing
machine using a polynomial amount of memory (space).
Definition

[
\text{NPSPACE} = \bigcup_{k \ge 1} \text{NSPACE}(n^k)
]

That is, a problem belongs to NPSPACE if it can be solved using at most (O(n^k)) space for
some constant (k).

Key Idea

 P and NP measure time complexity.

 PSPACE and NPSPACE measure space (memory) complexity.
 In NPSPACE, the algorithm may use nondeterministic choices, but the amount of
memory used must be polynomial in the input size.

Relationship with PSPACE

A fundamental result called Savitch's Theorem states:

[
\text{NPSPACE} = \text{PSPACE}
]

This means that nondeterminism does not increase the power of polynomial-space computation.

Complexity Class Relationships

P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME

Example Problems in PSPACE/NPSPACE

 Quantified Boolean Formula (QBF)

 Generalized Geography
 Certain game-solving problems
 Reachability problems requiring polynomial space
Difference Between NP and NPSPACE

NP NPSPACE
Limited by polynomial time Limited by polynomial space

NP ⊆ NPSPACE
Solutions verifiable in polynomial time Solvable using polynomial memory
Usually considered a larger class
Example: SAT Example: QBF

Short Note (5 Marks)

NPSPACE is the class of decision problems solvable by a nondeterministic Turing machine

using polynomial space. It focuses on memory usage rather than execution time. By Savitch's
Theorem, NPSPACE is equal to PSPACE, i.e.,

[
\text{NPSPACE} = \text{PSPACE}
]

NPSPACE contains many important problems that may require exponential time but only
polynomial memory to solve.

8. PSPACE (Polynomial Space)

PSPACE is the class of decision problems that can be solved by a deterministic Turing
machine using a polynomial amount of memory (space).

Definition

[
\text{PSPACE} = \bigcup_{k \ge 1} \text{SPACE}(n^k)
]

A problem belongs to PSPACE if it can be solved using at most (O(n^k)) space for some
constant (k), where (n) is the input size.

Key Idea

 PSPACE measures memory usage, not running time.

 An algorithm may take a long time (even exponential time), but it must use only
polynomial space.
Example

Consider a maze-solving problem:

 The algorithm explores all possible paths.

 It may take a very long time.
 However, it only needs to store the current path and some bookkeeping information,
which requires polynomial space.

Therefore, such problems can belong to PSPACE.

Important Properties

1. Every problem in P is in PSPACE.

[
P \subseteq PSPACE
]

2. Every problem in NP is also in PSPACE.

[
NP \subseteq PSPACE
]

3. By Savitch's Theorem:

[
NPSPACE = PSPACE
]

Complexity Class Relationship

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

PSPACE-Complete Problems

These are the hardest problems in PSPACE.

Examples:

 Quantified Boolean Formula (QBF)

 Generalized Geography
 Many game-playing and planning problems

If any PSPACE-complete problem is solved efficiently, then all PSPACE problems can be
solved efficiently.

Applications

 Artificial Intelligence planning

 Game theory
 Formal verification
 Logic and theorem proving

Difference Between P, NP, and PSPACE

Class Resource Measured Description

P Time Solvable in polynomial time
NP Time Solution verifiable in polynomial time
PSPACE Space Solvable using polynomial memory

5-Mark Answer

PSPACE is the class of decision problems that can be solved by a deterministic Turing machine
using polynomial space. It focuses on memory requirements rather than execution time. PSPACE
contains both P and NP, and many complex problems such as QBF belong to PSPACE. A key
result is Savitch's Theorem, which states that PSPACE = NPSPACE.

9. Types of Quick Sort

Quick Sort can be classified based on the pivot selection method.

1. First Element Pivot Quick Sort

  The first element is chosen as the pivot.
 Simple to implement.
 May lead to worst-case performance on already sorted data.

Example:

Array: [10, 5, 8, 2]
Pivot = 10

2. Last Element Pivot Quick Sort

 The last element is chosen as the pivot.

 Commonly used in implementations.

Example:

Array: [10, 5, 8, 2]
Pivot = 2

3. Randomized Quick Sort

 A random element is selected as the pivot.

 Reduces the chance of worst-case behavior.
 Average Time Complexity: (O(n \log n)).

Example:

Array: [10, 5, 8, 2]
Random Pivot = 8

4. Median-of-Three Quick Sort

 Pivot is chosen as the median of:

o First element
o Middle element
o Last element
 Produces better partitions in many cases.

Example:

Array: [10, 5, 8, 2, 15]

First = 10, Middle = 8, Last = 15
Pivot = 10 (median)
Based on Partitioning Scheme

5. Lomuto Partition Quick Sort

 Uses a single index.

 Easy to understand and implement.
 Commonly uses the last element as pivot.

6. Hoare Partition Quick Sort

 Uses two indices moving from opposite ends.

 Performs fewer swaps.
 Generally more efficient than Lomuto partition.

Time Complexity

Case Complexity
Best Case (O(n \log n))
Average Case (O(n \log n))
Worst Case (O(n^2))

Exam-Oriented Answer (2–3 Marks)

Types of Quick Sort:

1. First Element Pivot Quick Sort

2. Last Element Pivot Quick Sort
3. Randomized Quick Sort
4. Median-of-Three Quick Sort

Quick Sort can also be implemented using Lomuto Partition and Hoare Partition schemes.
The average time complexity of Quick Sort is (O(n \log n)).

1. Lomuto Partition Scheme

In Lomuto partition, the last element is chosen as the pivot.

Algorithm
LomutoPartition(A, low, high)
1. pivot = A[high]
2. i = low - 1

3. for j = low to high - 1

4. if A[j] <= pivot
5. i = i + 1
6. swap(A[i], A[j])

7. swap(A[i + 1], A[high])

8. return i + 1

Example
Array: [10, 80, 30, 90, 40, 50, 70]
Pivot = 70

After partitioning:

[10, 30, 40, 50, 70, 90, 80]

Pivot position = 4

Characteristics

 Easy to implement.
 Uses more swaps.
 Pivot ends up in its final sorted position.

2. Hoare Partition Scheme

In Hoare partition, the first element is usually chosen as the pivot.

Algorithm
HoarePartition(A, low, high)
1. pivot = A[low]
2. i = low - 1
3. j = high + 1

4. while true
5. repeat
6. i = i + 1
7. until A[i] >= pivot

8. repeat
9. j = j - 1
10. until A[j] <= pivot
11. if i >= j
12. return j

13. swap(A[i], A[j])

Example
Array: [50, 30, 70, 20, 40, 60, 80]
Pivot = 50

After partitioning:

[40, 30, 20, 50, 70, 60, 80]

The array is partitioned into:

 Left side ≤ pivot

 Right side ≥ pivot

Characteristics

 Uses fewer swaps.

 Faster in practice.
 Pivot may not end up in its final sorted position immediately.

Quick Sort Using Lomuto Partition

QuickSort(A, low, high)
1. if low < high
2. p = LomutoPartition(A, low, high)
3. QuickSort(A, low, p-1)
4. QuickSort(A, p+1, high)

Quick Sort Using Hoare Partition

QuickSort(A, low, high)
1. if low < high
2. p = HoarePartition(A, low, high)
3. QuickSort(A, low, p)
4. QuickSort(A, p+1, high)

Difference Between Lomuto and Hoare

Lomuto Partition Hoare Partition

Pivot usually last element Pivot usually first element

More swaps Fewer swaps

 Lomuto Partition Hoare Partition

Simpler to understand Slightly more complex

Returns final pivot position Returns partition index

Less efficient More efficient in practice

Exam Tip (4–5 Marks)

Write the algorithm, mention the pivot selection rule, and state:

 Lomuto: simple but more swaps.

 Hoare: fewer swaps and generally faster.