DAA Insem

Unit 1
Q1. Define Iterative Algorithm

An iterative algorithm is an algorithm that repeats a set of steps again and again until a condition is satisfied. It uses
loops such as for, while, or do-while instead of calling itself (like recursion).

An iterative algorithm is an algorithm that solves a problem by repeatedly executing a set of instructions using loops
until the required result is obtained.

Example

Finding the sum of numbers from 1 to 5.

Algorithm

sum = 0

for i = 1 to 5

sum = sum + i

print(sum)

Working

 sum = 0

 Add 1 → sum = 1

 Add 2 → sum = 3

 Add 3 → sum = 6

 Add 4 → sum = 10

 Add 5 → sum = 15

Output: 15

Q2. Explain Iterative Algorithm Design Issues

When designing an iterative algorithm, we need to consider some important points to make sure it works correctly
and efficiently.

1. Initialization:
Variables should be given the correct initial value before the loop starts.

Example

sum = 0

for i = 1 to 5

sum = sum + i

If sum is not initialized to 0, the result may be incorrect.

Example

while i <= 5

If you write

while i < 5

then the number 5 will not be included.

3. Loop Update:
The loop variable must be updated after each iteration.

Example

i=i+1

If you forget to increase i, the loop never ends.

Example:

i=1

while i <= 5

print(i)

Since i is never increased, it prints 1 forever (Infinite Loop).

4. Termination:
The loop should stop after completing the required work.

Example

for i = 1 to 10

The loop automatically stops after i = 10.

## What is Algorithm Correctness?

Algorithm correctness means that an algorithm always produces the correct output for every valid input and
solves the given problem as intended.

[Link] is Correctness Important?

Correctness is important because:

1. Produces Accurate Results

The main purpose of an algorithm is to solve a problem correctly. An incorrect algorithm gives wrong answers.

Example:

 Input: 10 + 20

 Correct Output: 30

 Incorrect Output: 40
DAA Insem
2. Avoids Errors

A correct algorithm reduces mistakes and prevents unexpected behavior in software.

Example:
A banking application must calculate account balances correctly. A small error can lead to incorrect transactions.

3. Builds User Trust

Users trust software only when it consistently provides correct results.

Example:
People trust navigation apps because they give accurate routes.

4. Saves Time and Cost

Finding and fixing errors after software is released is expensive. A correct algorithm reduces debugging and
maintenance costs.

5. Ensures Reliability

Correct algorithms work properly for all valid inputs, making the software dependable.

Example:
A hospital management system must always calculate medicine dosages correctly to ensure patient safety.

Q. Define Loop Invariant

A Loop Invariant is a condition or statement that remains true before and after every iteration of a loop. It is
used to prove that an algorithm is correct.

Why is Loop Invariant Used?

 To prove the correctness of an algorithm.

 To show that the loop works as expected.

 To ensure the final output is correct.

Proving Correctness Using Loop Invariant

To prove correctness, we use three steps:

1. Initialization

Before the loop starts, prove that the loop invariant is true.

2. Maintenance

Assume the loop invariant is true before one iteration. Show that it is still true after that iteration.

3. Termination

When the loop ends, use the loop invariant to prove that the algorithm produces the correct final result.

Example: Sum of First n Numbers

Step 1: Initialization

Before the loop starts:

sum = 0

i=1
DAA Insem
The sum of numbers from 1 to 0 is 0.

So, the loop invariant is true.

Step 2: Maintenance

Assume before an iteration:

sum = 1 + 2 + ... + (i − 1)

Inside the loop:

sum = sum + i

Now,

sum = 1 + 2 + ... + i

The loop invariant is still true after the iteration.

Step 3: Termination

The loop stops after i = n.

At this point,

sum = 1 + 2 + ... + n

This is exactly the required answer.

Hence, the algorithm is correct.

Q. Prove Correctness Using Mathematical Induction

Mathematical Induction is a proof technique used to show that an algorithm or formula is correct for all positive
integers (n).

Steps of Mathematical Induction

There are two main steps:

1. Base Case

Prove that the statement is true for the first value (usually n = 1).

2. Induction Step

 Assume the statement is true for n = k (called the induction hypothesis).

 Then prove it is also true for n = k + 1.

If both steps are true, then the statement is true for all positive integers.

Example: Sum of First n Natural Numbers

We want to prove:

n ( n+1 )
1+2+3+⋯+ n=
2
Step 1: Base Case (n = 1)
DAA Insem
Left Side (LHS):

1
Right Side (RHS):

1 ( 1+1 ) 2
= =1
2 2
LHS = RHS

✅ Therefore, the statement is true for n = 1.

Step 2: Induction Hypothesis

Assume the statement is true for n = k.

That is,

k ( k +1 )
1+2+3+⋯+ k=
2
Step 3: Prove for n = k + 1

We need to prove:

( k+ 1 )( k +2 )
1+2+3+⋯+ k + ( k +1 ) =
2
Using the induction hypothesis:

k ( k +1 )
+ ( k +1 )
2
Take (k + 1) common:

( k +1 ) ( k2 +1)¿ ( k +1 )( k +22 )¿ ( k +1)2( k +2)

✅ Hence, the statement is true for k + 1.

[Link] Correctness Using Counter Example

A counterexample is a specific example that shows a statement or algorithm is not always correct. If even one
valid input gives the wrong result, then the statement or algorithm is incorrect.

Example 1

Statement

"All even numbers are prime."

Counterexample
DAA Insem
Take the number:

 8 is an even number.

 But 8 is not a prime number because it is divisible by 2 and 4.

Therefore, the statement is false.

Example 2 (Algorithm)

Algorithm

largest = arr[0]

for i = 1 to n-1

if arr[i] > arr[0]

largest = arr[i]

print(largest)

Input

Array = [5, 10, 8, 12, 9]

Output

12

This works correctly.

Now test another input:

Array = [5, 10, 12, 11]

Output:

11

Correct answer should be:

12

The algorithm compares every element only with the first element (arr[0]), not with the current largest value. Hence
it fails for this input.

This input is a counterexample, proving that the algorithm is not correct.

3. Problem Solving Strategies

Problem-solving strategies are methods or techniques used to solve a problem efficiently and systematically.
They help in designing algorithms and finding the best solution.

Explain Any Four Problem Solving Strategies

Meaning

The Brute Force method tries all possible solutions and selects the correct one.

Example

Finding a number in an array by checking each element one by one (Linear Search).

Advantages

 Easy to understand and implement.

 Always finds the solution if one exists.

Disadvantages

 Slow for large problems.

 May take more time.

2. Divide and Conquer Strategy

Meaning

This strategy divides a large problem into smaller subproblems, solves each one separately, and then combines
the results.

Example

 Merge Sort

 Quick Sort

 Binary Search

Advantages

 Faster than brute force.

 Efficient for large datasets.

Disadvantages

 Can be difficult to design.

 Uses recursion, which may require extra memory.

3. Greedy Strategy

Meaning

A Greedy algorithm makes the best choice at each step with the hope of reaching the overall best solution.

Example

 Activity Selection Problem

 Huffman Coding

 Prim's Algorithm

Advantages
DAA Insem
 Simple and fast.

 Uses less memory.

Disadvantages

 Does not always give the optimal solution for every problem.

4. Dynamic Programming (DP)

Meaning

Dynamic Programming solves overlapping subproblems only once and stores their results to avoid repeated
calculations.

Example

 Fibonacci Series

 0/1 Knapsack Problem

 Longest Common Subsequence (LCS)

Advantages

 Reduces repeated work.

 Faster than simple recursion.

Disadvantages

 Requires extra memory to store intermediate results.

 More complex to implement.

Unit 2
Best, Average & Worst Case Analysis (Easy Explanation)

When we analyze an algorithm, we want to know how much time it takes to run. Since the input size can be
different each time, we study the algorithm in three cases:

1. Best Case

Definition
DAA Insem
The best case is the situation where the algorithm takes the least amount of time to complete.

 This happens when the input is in the most favorable condition.

 It tells us the minimum running time.

Example

Suppose you are searching for a number in an array.

Array: [10, 20, 30, 40, 50]

Search for 10

The number is found in the first position, so only one comparison is needed.

Time Complexity: O(1) (Constant Time)

2. Average Case

Definition

The average case is the expected running time for a normal or random input.

 It assumes all inputs are equally likely.

 It gives a realistic idea of the algorithm's performance.

Example

Array: [10, 20, 30, 40, 50]

Search for 30

The number is found after checking a few elements.

On average, about n/2 elements are checked.

Time Complexity: O(n) (Linear Time)

3. Worst Case

Definition

The worst case is the situation where the algorithm takes the maximum amount of time.

 This happens when the input is in the least favorable condition.

 It tells us the maximum running time.

Example

Array: [10, 20, 30, 40, 50]

Search for 50 (or a number that is not in the array)

The algorithm checks every element before stopping.

Time Complexity: O(n) (Linear Time)

Analysis

 Best Case: The key is at the first position.

o Time Complexity = O(1)

 Average Case: The key is somewhere in the middle.

o Comparisons ≈ n/2

o Time Complexity = O(n)

 Worst Case: The key is at the last position or not present.

o Comparisons = n

o Time Complexity = O(n)

## P, NP, NP-Hard & NP-Complete (Simple and Easy Language)

Think of a jigsaw puzzle.

 Solving the puzzle = Finding the answer.

 Checking the completed puzzle = Verifying the answer.

1. P (Polynomial Time)

P is a group of problems that a computer can solve quickly.

In simple words:

P = Easy to solve and easy to check.

Examples

 Sorting numbers

 Binary Search

 Finding the largest number in a list

 Finding the shortest path using Dijkstra's algorithm

Example

Find the largest number in:

5, 8, 2, 10, 4

Answer:

10

The computer can find it quickly.

2. NP (Non-deterministic Polynomial Time)

NP is a group of problems that are hard to solve, but easy to check if someone gives you the answer.

In simple words:

NP = Difficult to solve, but easy to verify.

 Solving a Sudoku puzzle from scratch takes time.

 If someone gives you a completed Sudoku, you can quickly check whether it is correct.

So Sudoku is an example of an NP problem.

Other examples:

 Sudoku

 Graph Coloring

 Travelling Salesman (Decision Version)

3. NP-Hard

NP-Hard problems are very difficult. They are at least as hard as the hardest NP problems.

In simple words:

NP-Hard = Extremely difficult problems.

For some NP-Hard problems, even checking a solution may not be easy.

Examples

 Travelling Salesman (Optimization Version)

 Job Scheduling

 Knapsack Optimization

 Halting Problem

4. NP-Complete

A problem is NP-Complete if:

1. It belongs to NP (its solution can be checked quickly), and

2. It is also NP-Hard (it is one of the hardest problems in NP).

In simple words:

NP-Complete = Hard to solve, but easy to verify.

Examples

 3-SAT

 Hamiltonian Cycle

 Vertex Cover (Decision)

 Travelling Salesman (Decision Version)

Easy Comparison

Type Solving the Problem Checking the Answer Example

P Easy Easy Binary Search, Sorting

NP Hard Easy Sudoku

Job Scheduling, TSP

NP-Complete Very Hard Easy 3-SAT, Hamiltonian Cycle

## What is the 3-SAT Problem?

The 3-SAT (3-Satisfiability) problem is a famous NP-Complete problem in computer science.

It asks:

Can we assign True (T) or False (F) values to the variables so that the entire logical expression becomes
True?

The name 3-SAT means:

 3 → Each group (called a clause) contains exactly 3 variables or their negations.

 SAT → Satisfiability (checking if the expression can be made True).

Basic Terms

 Variable: A letter like A, B, C

 Literal: A variable or its negation (e.g., A or ¬A)

 Clause: Three literals joined by OR (∨)

 Formula: Multiple clauses joined by AND (∧)

General Form

( A ∨ B ∨¬C ) ∧ ( ¬ A ∨C ∨ D )
Here:

 Each bracket has 3 literals.

 Brackets are connected using AND (∧).

Example

Consider the expression:

( A ∨ B ∨C ) ∧ ( ¬ A ∨ B∨ C )
Step 1: Assign values

Let:

 A = False

 B = True

 C = False
DAA Insem
Step 2: Check each clause

Clause 1:

( A ∨ B ∨C )
= False OR True OR False

= True

Clause 2:

( ¬ A ∨ B ∨C )
= True OR True OR False

= True

Step 3: Final Result

Since both clauses are True:

True AND True = True

✅ Therefore, this 3-SAT problem is Satisfiable.

Unsatisfiable Example

Expression:

( A ∨ A ∨ A ) ∧ (¬ A ∨¬ A ∨ ¬ A )
Try both possible values:

 If A = True:

o First clause = True

o Second clause = False

 If A = False:

o First clause = False

o Second clause = True

In both cases, one clause is False.

❌ Therefore, the expression is Unsatisfiable.

Applications of 3-SAT

 Artificial Intelligence (AI)

 Circuit Design and Testing

 Software Verification

 Scheduling Problems

 Cryptography
DAA Insem
Key Points

 Each clause contains exactly 3 literals.

 Clauses are connected by AND (∧).

 Literals inside a clause are connected by OR (∨).

 The goal is to assign True/False values to variables so that all clauses become True.

 3-SAT is an NP-Complete problem, meaning it is hard to solve but easy to verify once a solution is given.

## Why is SAT Important? (Easy to Understand)

SAT (Satisfiability Problem) is important because it helps determine whether a logical problem has at least one
valid solution.

In simple words:

SAT tells us whether a set of conditions can all be satisfied at the same time.

Importance of SAT

1. Foundation of Computer Science

o SAT was the first problem proved to be NP-Complete.

o Many difficult computational problems are compared to SAT.

2. Problem Solving

o It helps solve complex decision problems by checking if a valid solution exists.

3. Software Testing and Verification

o SAT is used to verify that software and hardware work correctly without errors.

4. Artificial Intelligence (AI)

o AI systems use SAT to solve planning, reasoning, and decision-making problems.

5. Circuit Design

o Engineers use SAT to test and verify digital circuits before manufacturing.

6. Scheduling and Planning

o SAT helps create schedules for exams, employees, flights, and other planning tasks while
satisfying all constraints.

## Prove 3-SAT is NP-Complete (Easy to Understand)

To prove that 3-SAT is NP-Complete, we need to show two things.

Step 1: Show that 3-SAT belongs to NP

A problem is in NP if we can quickly verify a given solution.

For 3-SAT:
DAA Insem
 Suppose someone gives us values for the variables (True/False).

 We simply check each clause.

 If every clause is True, the formula is satisfied.

Since checking all clauses takes polynomial time, 3-SAT belongs to NP.

✅ Therefore, 3-SAT ∈ NP.

Step 2: Show that 3-SAT is NP-Hard

To prove NP-Hard, we reduce a known NP-Complete problem to 3-SAT.

 The SAT problem is already known to be NP-Complete (Cook–Levin Theorem).

 Any SAT formula can be converted into an equivalent 3-SAT formula in polynomial time.

 Therefore,

SAT ≤ p 3-SAT
This means if we can solve 3-SAT, we can also solve SAT.

Hence, 3-SAT is NP-Hard.

Conclusion

Since:

1. 3-SAT is in NP, and

2. 3-SAT is NP-Hard,

we conclude that:

3-SAT is NP-Complete
## Vertex Cover NP-Complete Proof (Easy to Understand)

What is a Vertex Cover?

A Vertex Cover is a set of vertices (nodes) in a graph such that every edge is connected to at least one selected
vertex.

Example

/\

B---C

Edges:

 AB

 AC

 BC

Choose vertices A and B.

 AC → Covered by A ✅

 BC → Covered by B ✅

So, {A, B} is a Vertex Cover.

Vertex Cover Decision Problem

Given:

 A graph G

 An integer k

Question:

Does the graph have a Vertex Cover of size k or less?

This is called the Vertex Cover Decision Problem.

Proof that Vertex Cover is NP-Complete

To prove that Vertex Cover is NP-Complete, we must show two things.

Step 1: Vertex Cover belongs to NP

Suppose someone gives us a set of vertices.

We simply check:

 Is every edge connected to at least one selected vertex?

 Is the number of selected vertices ≤ k?

This checking can be done quickly (in polynomial time).

✅ Therefore,

Vertex Cover ∈ NP

Step 2: Vertex Cover is NP-Hard

We reduce a known NP-Complete problem to Vertex Cover.

A known NP-Complete problem is:

3-SAT

It can be transformed into a Vertex Cover problem in polynomial time.

3-SAT ≤ p Vertex Cover

 If we can solve Vertex Cover efficiently,

 then we can also solve every 3-SAT problem efficiently.

Hence,

Vertex Cover is NP-Hard.

Since:

 Vertex Cover is in NP.

 Vertex Cover is NP-Hard.

Therefore,

Vertex Cover is NP-Complete