Home / Sem 4 / CSE408 / Unit 6 Subjective

Unit6 - Subjective Questions

CSE408 • Practice Questions with Detailed Answers

Define Modular Arithmetic. Explain the properties of modular addition and multiplication with examples.

Modular Arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value, called the modulus.

Let $n$ be a positive integer. Two integers $a$ and $b$ are said to be congruent modulo $n$ , written as $a \equiv b \pmod{n}$ , if their difference $(a - b)$ is an integer multiple of $n$ .

Properties of Modular Arithmetic:
If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ , then:

Addition: $(a + c) \equiv (b + d) \pmod{n}$
Multiplication: $(a \cdot c) \equiv (b \cdot d) \pmod{n}$
Subtraction: $(a - c) \equiv (b - d) \pmod{n}$

Example: Let $n = 5$ .

$7 \equiv 2 \pmod{5}$ and $11 \equiv 1 \pmod{5}$ .
Addition: $(7 + 11) \pmod{5} = 18 \pmod{5} = 3$ . Also, $(2 + 1) \pmod{5} = 3$ .
Multiplication: $(7 \cdot 11) \pmod{5} = 77 \pmod{5} = 2$ . Also, $(2 \cdot 1) \pmod{5} = 2$ .

Explain the concept of Modular Exponentiation. Write an algorithm to compute $a^b \pmod{n}$ efficiently.

Modular Exponentiation is a type of exponentiation performed over a modulus. It is used extensively in cryptography. Computing $a^b \pmod{n}$ directly by finding $a^b$ first is computationally infeasible for large $b$ because $a^b$ grows exponentially.

The efficient way is the Right-to-Left Binary Method (Repeated Squaring), which reduces the time complexity to $O(\log b)$ .

Algorithm:
text
Modular_Exponentiation(a, b, n):
result = 1
a = a % n
while b > 0:
// If b is odd, multiply a with result
if (b % 2 == 1):
result = (result a) % n
// b must be even now
b = b >> 1 // Divide b by 2
a = (a a) % n // Square a
return result

This algorithm uses the property that $(x \cdot y) \pmod{n} = [(x \pmod{n}) \cdot (y \pmod{n})] \pmod{n}$ , keeping intermediate values small.

What is a modular multiplicative inverse? Under what conditions does it exist?

Modular Multiplicative Inverse:
In modular arithmetic, the modular multiplicative inverse of an integer $a$ modulo $m$ is an integer $x$ such that:
$a \cdot x \equiv 1 \pmod{m}$
This is analogous to the reciprocal in standard arithmetic.

Condition for Existence:
The modular multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime (i.e., their Greatest Common Divisor is 1, $\gcd(a, m) = 1$ ).

Finding the Inverse:
If $\gcd(a, m) = 1$ , the Extended Euclidean Algorithm can be used to find coefficients $x$ and $y$ such that:
$a \cdot x + m \cdot y = 1$
Taking modulo $m$ on both sides yields $a \cdot x \equiv 1 \pmod{m}$ , making $x$ the modular inverse.

State and explain the Euclidean Algorithm for finding the Greatest Common Divisor (GCD) of two numbers.

Euclidean Algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder.

Principle:
The algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. More efficiently, it uses the modulo operation:
$\gcd(a, b) = \gcd(b, a \pmod{b})$
with the base case $\gcd(a, 0) = a$ .

Algorithm:
text
Euclid(a, b):
if b == 0:
return a
else:
return Euclid(b, a % b)

Example: Find $\gcd(252, 105)$

$\gcd(252, 105) = \gcd(105, 252 \pmod{105}) = \gcd(105, 42)$
$\gcd(105, 42) = \gcd(42, 105 \pmod{42}) = \gcd(42, 21)$
$\gcd(42, 21) = \gcd(21, 42 \pmod{21}) = \gcd(21, 0)$
Return 21. Thus, $\gcd(252, 105) = 21$ .

Describe the Extended Euclidean Algorithm and its significance in number-theoretic algorithms.

The Extended Euclidean Algorithm not only finds the greatest common divisor $d$ of two integers $a$ and $b$ , but also finds integers $x$ and $y$ (called Bézout coefficients) such that:
$a \cdot x + b \cdot y = \gcd(a, b)$

Significance:

Modular Multiplicative Inverse: If $\gcd(a, m) = 1$ , then $a \cdot x + m \cdot y = 1$ . Taking modulo $m$ gives $a \cdot x \equiv 1 \pmod{m}$ . Here, $x$ is the multiplicative inverse of $a$ modulo $m$ . This is crucial in cryptography (like RSA).
Solving Linear Diophantine Equations: It helps solve equations of the form $ax + by = c$ , which has integer solutions if and only if $\gcd(a, b)$ divides $c$ .

Algorithm Idea:
It maintains variables to compute $x$ and $y$ iteratively as it computes the sequences of remainders in the standard Euclidean algorithm, effectively working backwards or parallel to the GCD computation.

Analyze the time complexity of the Euclidean Algorithm.

Time Complexity of Euclidean Algorithm:
The time complexity is determined by the number of modulo operations performed.

Let the algorithm be computing $\gcd(a, b)$ where $a > b$ .
In each step, $a$ and $b$ are replaced by $b$ and $a \pmod{b}$ .
It can be shown that after two consecutive steps, the value of the first argument is reduced to at least half of its original value. Specifically, $a \pmod{b} < \frac{a}{2}$ .

Because the numbers are halved at least every two steps, the number of steps is at most $2 \log_2(b)$ .
Thus, the number of divisions is $O(\log b)$ .
If we consider the bit-length of the numbers, say $n$ bits, the time complexity is $O(n)$ divisions. If standard long division is used, each division takes $O(n^2)$ bit operations, leading to an overall bit complexity of $O(n^3)$ .

Worst-case scenario: The worst-case occurs when $a$ and $b$ are consecutive Fibonacci numbers, known as Lamé's Theorem.

State the Chinese Remainder Theorem (CRT).

Chinese Remainder Theorem (CRT):

The Chinese Remainder Theorem states that if one knows the remainders of the Euclidean division of an integer $x$ by several pairwise coprime integers, then one can determine uniquely the remainder of the division of $x$ by the product of these integers.

Formal Statement:
Let $m_1, m_2, \dots, m_k$ be pairwise coprime positive integers (i.e., $\gcd(m_i, m_j) = 1$ for all $i \neq j$ ).
Let $a_1, a_2, \dots, a_k$ be any integers.

Then the system of simultaneous congruences:
$x \equiv a_1 \pmod{m_1}$
$x \equiv a_2 \pmod{m_2}$
$\dots$
$x \equiv a_k \pmod{m_k}$

has a unique solution modulo $M = m_1 \cdot m_2 \cdot \dots \cdot m_k$ .
This means any two solutions $x_1$ and $x_2$ will satisfy $x_1 \equiv x_2 \pmod{M}$ .

Explain the formula used to construct the solution in the Chinese Remainder Theorem.

To construct the unique solution modulo $M = m_1 m_2 \dots m_k$ for the system of congruences $x \equiv a_i \pmod{m_i}$ :

Compute the total product:
$M = m_1 \cdot m_2 \cdot \dots \cdot m_k$
Compute partial products:
For each $i$ from 1 to $k$ , compute $M_i = \frac{M}{m_i}$ .
Notice that $M_i$ is the product of all moduli except $m_i$ . Thus, $\gcd(M_i, m_i) = 1$ .
Compute modular inverses:
For each $i$ , find $y_i$ such that $M_i \cdot y_i \equiv 1 \pmod{m_i}$ .
$y_i$ is the modular multiplicative inverse of $M_i$ modulo $m_i$ .
Construct the solution:
Calculate $x = \sum_{i=1}^{k} a_i \cdot M_i \cdot y_i$ .
Final step:
The unique solution modulo $M$ is $x \pmod{M}$ .
This works because for any modulus $m_j$ , all terms in the sum where $i \neq j$ contain $m_j$ as a factor (since $M_i$ includes $m_j$ ) and thus become 0 modulo $m_j$ . The remaining term is $a_j \cdot M_j \cdot y_j \equiv a_j \cdot 1 \equiv a_j \pmod{m_j}$ .

Find the smallest positive integer $x$ that satisfies: $x \equiv 2 \pmod{3}$ , $x \equiv 3 \pmod{5}$ , and $x \equiv 2 \pmod{7}$ .

Given:
$a_1 = 2, m_1 = 3$
$a_2 = 3, m_2 = 5$
$a_3 = 2, m_3 = 7$

Step 1: $M = m_1 \cdot m_2 \cdot m_3 = 3 \cdot 5 \cdot 7 = 105$

Step 2: Compute $M_i = \frac{M}{m_i}$
$M_1 = \frac{105}{3} = 35$
$M_2 = \frac{105}{5} = 21$
$M_3 = \frac{105}{7} = 15$

Step 3: Compute inverses $y_i$ such that $M_i y_i \equiv 1 \pmod{m_i}$

$35 y_1 \equiv 1 \pmod{3} \Rightarrow 2 y_1 \equiv 1 \pmod{3} \Rightarrow y_1 = 2$
$21 y_2 \equiv 1 \pmod{5} \Rightarrow 1 y_2 \equiv 1 \pmod{5} \Rightarrow y_2 = 1$
$15 y_3 \equiv 1 \pmod{7} \Rightarrow 1 y_3 \equiv 1 \pmod{7} \Rightarrow y_3 = 1$

Step 4: Compute $x = \sum (a_i M_i y_i)$
$x = (2 \cdot 35 \cdot 2) + (3 \cdot 21 \cdot 1) + (2 \cdot 15 \cdot 1)$
$x = 140 + 63 + 30 = 233$

Step 5: Reduce modulo $M$
$x \equiv 233 \pmod{105}$
$233 = 2 \times 105 + 23$
So, $x = 23$ .

The smallest positive integer is 23.

Distinguish between Optimization Problems and Decision Problems with suitable examples.

1. Optimization Problems:
An optimization problem asks for the best (maximum or minimum) solution among all feasible solutions. The output is a value or a specific configuration that achieves that value.

Example (Traveling Salesman Problem - TSP): Given a set of cities and distances between them, find the shortest possible route that visits each city exactly once and returns to the origin city.
Example (0/1 Knapsack): Find the combination of items that maximizes the total value without exceeding the weight capacity.

2. Decision Problems:
A decision problem is a problem that requires a simple "Yes" or "No" answer based on a specific given condition.

Example (TSP Decision Variant): Given a set of cities, distances between them, and a limit $L$ , is there a route that visits each city exactly once and returns to the origin with a total distance less than or equal to $L$ ?
Example (0/1 Knapsack Decision Variant): Is there a combination of items weighing at most $W$ that yields a value of at least $V$ ?

Relationship:
In complexity theory, optimization problems are often cast as decision problems because if the decision problem is hard, the optimization problem is at least as hard.

Define the complexity class P. Give examples of problems that belong to P.

Complexity Class P:
The class P (Polynomial time) consists of all decision problems that can be solved by a deterministic Turing machine in polynomial time.

In simpler terms, a problem is in P if there exists an algorithm to solve it such that the number of steps required is bounded by a polynomial function of the input size $n$ (e.g., $O(n), O(n^2), O(n^3)$ ).

Problems in P are generally considered "tractable" or efficiently solvable.

Examples of problems in P:

Searching: Finding an element in a sorted array (Binary Search, $O(\log n)$ ).
Sorting: Sorting an array of numbers (Merge Sort, $O(n \log n)$ ).
Shortest Path: Finding the shortest path from a single source in a graph with non-negative edge weights (Dijkstra's Algorithm, polynomial time).
Primality Testing: Determining if a number is prime (AKS primality test).
Greatest Common Divisor: Finding the GCD of two numbers (Euclidean Algorithm).

Define the complexity class NP. How does it relate to non-deterministic algorithms?

Complexity Class NP:
NP stands for "Nondeterministic Polynomial time". It is the class of decision problems for which, if the answer is "Yes", there exists a proof (or certificate) that can be verified by a deterministic Turing machine in polynomial time.

Equivalently, NP is the set of decision problems that can be solved in polynomial time by a Non-deterministic Turing Machine (NDTM).

Relation to Non-deterministic Algorithms:
A non-deterministic algorithm operates in two stages:

Guessing Stage (Non-deterministic): Given an instance of the problem, it "guesses" a solution (certificate). This step is purely non-deterministic.
Verification Stage (Deterministic): It takes the guessed solution and verifies whether it is a valid solution to the problem in polynomial time.

If the verification stage returns "True" in polynomial time for at least one guess, the problem belongs to NP. Therefore, NP problems are those whose solutions are easy to check, even if they might be hard to find.

What is meant by Polynomial-Time Reduction? Explain its significance in complexity theory.

Polynomial-Time Reduction:
A polynomial-time reduction from a decision problem $A$ to a decision problem $B$ (denoted as $A \leq_p B$ ) is an algorithm that transforms instances of problem $A$ into instances of problem $B$ such that:

The transformation function $f$ computes the instance of $B$ in polynomial time: $y = f(x)$ .
The answer to instance $x$ of problem $A$ is "Yes" if and only if the answer to instance $y$ of problem $B$ is "Yes".

Significance:

Relative Hardness: If $A \leq_p B$ , it means problem $B$ is at least as hard as problem $A$ . If we have an efficient (polynomial) algorithm for $B$ , we can use it to solve $A$ efficiently.
Proving NP-Completeness: Reductions are the primary tool for proving that problems are NP-complete. To prove a new problem $B$ is NP-complete, one must show that $B \in NP$ and that a known NP-complete problem $A$ reduces to $B$ in polynomial time ( $A \leq_p B$ ).

Define NP-Hard and NP-Complete complexity classes. How do they differ?

NP-Hard:
A problem $H$ is NP-hard if every problem $L$ in NP can be reduced to $H$ in polynomial time ( $L \leq_p H$ for all $L \in NP$ ). NP-hard problems are at least as hard as the hardest problems in NP. They do not have to be in NP themselves (e.g., they could be optimization problems or undecidable problems).

NP-Complete (NPC):
A problem $C$ is NP-complete if it satisfies two conditions:

$C$ is in NP ( $C \in NP$ ).
$C$ is NP-hard (every problem in NP reduces to $C$ in polynomial time).
NP-complete problems are the hardest problems within the class NP.

Differences:

Membership in NP: NP-complete problems must be in NP (their solutions must be verifiable in polynomial time). NP-hard problems do not have to be in NP.
Problem Type: NP-complete strictly refers to decision problems. NP-hard can refer to optimization problems (like the optimization version of TSP) or search problems.
Relationship: The set of NP-Complete problems is the intersection of NP and NP-Hard.

Explain the significance of the Cook-Levin Theorem.

The Cook-Levin Theorem states that the Boolean Satisfiability Problem (SAT) is NP-complete. It was proven independently by Stephen Cook (1971) and Leonid Levin (1973).

Significance:

First NP-Complete Problem: Before this theorem, the concept of NP-completeness existed in theory, but it was unknown if any such problem actually existed. The theorem provided the very first problem proven to be NP-complete.
Foundation for Reductions: By proving that SAT is NP-complete, Cook and Levin provided a starting point for proving other problems are NP-complete. To prove a new problem $X$ is NP-complete, one no longer needs to reduce every problem in NP to $X$ . Instead, one only needs to reduce SAT (or another known NP-complete problem) to $X$ .
P vs NP connection: It established that if a deterministic polynomial-time algorithm can be found for SAT, then $P = NP$ , fundamentally shaping theoretical computer science.

What is the Satisfiability (SAT) problem? Why is it historically important in the analysis of algorithms?

The Satisfiability (SAT) Problem:
SAT is a decision problem in Boolean logic. Given a Boolean formula consisting of variables (like $x_1, x_2$ ), logical ANDs, ORs, and NOTs, the SAT problem asks whether there exists an assignment of truth values (True/False) to the variables that makes the entire formula evaluate to True.

Example: $(x_1 \lor \neg x_2) \land (x_2 \lor x_3)$ . Is there an assignment to $x_1, x_2, x_3$ that makes this True? (Yes, e.g., $x_1 = T, x_2 = F, x_3 = T$ ).

Historical Importance:

Cook-Levin Theorem: SAT was the very first problem proven to be NP-complete.
Benchmark for Hardness: It serves as the root of the NP-completeness tree. Thousands of problems in various domains (graph theory, scheduling, game theory) have been proven NP-complete by demonstrating a polynomial-time reduction from SAT (or 3-SAT) to the target problem.
Practical Solvers: Despite being NP-complete, modern SAT solvers use advanced heuristics to solve massive real-world instances efficiently, making SAT practically important in hardware verification and AI.

Describe the P vs NP problem. Why is it considered one of the most important open problems in computer science?

The P vs NP Problem:
The P vs NP problem asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.

P is the class of problems that can be solved in polynomial time.
NP is the class of problems whose solutions can be verified in polynomial time.

The question is whether $P = NP$ . Since $P \subseteq NP$ is trivially true, the real question is whether $NP \subseteq P$ .

Why it is important:

Fundamental limit of computation: It addresses the absolute limits of what computers can do efficiently. If $P = NP$ , it means that for any problem where a solution is easily checkable, there is an efficient way to find that solution.
Impact on Cryptography: Modern cryptography (like RSA) relies on the assumption that $P \neq NP$ (specifically, that factoring large numbers or discrete logs are hard). If $P = NP$ , public-key cryptography would break.
Everyday Optimization: Many real-world problems in logistics, scheduling, manufacturing, and AI are NP-complete. A proof that $P=NP$ (with a constructive algorithm) would revolutionize how the world optimizes resources.

Explain the Traveling Salesman Problem (TSP). Formulate both its optimization and decision versions.

Traveling Salesman Problem (TSP):
TSP is a classic algorithmic problem focused on optimization. Given a list of cities and the distances between each pair of cities, a salesperson must find the shortest possible route that visits each city exactly once and returns to the origin city.

1. Optimization Version:

Input: A complete weighted graph $G = (V, E)$ where $V$ is a set of vertices (cities) and $E$ is a set of edges with non-negative weights (distances).
Output: A Hamiltonian cycle (a cycle that visits every vertex exactly once) such that the sum of the edge weights of the cycle is minimized.
Complexity: This version is NP-hard.

2. Decision Version:

Input: A complete weighted graph $G = (V, E)$ , and a threshold value $K$ .
Output: "Yes" if there exists a Hamiltonian cycle in $G$ with a total weight $\leq K$ . "No" otherwise.
Complexity: This version is NP-complete. If we guess a path, we can verify in polynomial time if it is a valid Hamiltonian cycle and if its total weight is $\leq K$ .

What is the Clique Problem? Show that the Clique decision problem is in NP.

The Clique Problem:
In graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent (i.e., its induced subgraph is complete).
The Clique Decision Problem asks: Given an undirected graph $G = (V, E)$ and an integer $k$ , does $G$ contain a clique of size at least $k$ ?

Showing Clique is in NP:
To show a problem is in NP, we must show that a proposed solution (certificate) can be verified in polynomial time.

Certificate: The certificate is a subset of vertices $V' \subseteq V$ such that $|V'| = k$ .
Verification Algorithm:
- Check if the number of vertices in $V'$ is exactly $k$ . This takes $O(1)$ if the size is known, or $O(k)$ to count.
- Check if every pair of vertices $u, v \in V'$ has an edge in $E$ . There are $\frac{k(k-1)}{2}$ pairs to check.
- For each pair, checking adjacency takes $O(1)$ in an adjacency matrix or $O(|V|)$ in an adjacency list.
Time Complexity: The verification process takes at most $O(k^2)$ time. Since $k \leq |V|$ , the verification takes $O(|V|^2)$ time, which is polynomial relative to the input size.

Since a valid certificate can be verified in polynomial time, the Clique problem is in NP.

Define the Vertex Cover problem. How does it relate to the Clique problem?

Vertex Cover Problem:
A vertex cover of an undirected graph $G=(V, E)$ is a subset of vertices $V' \subseteq V$ such that for every edge $(u, v) \in E$ , at least one of $u$ or $v$ is in $V'$ .
The decision problem asks: Given a graph $G$ and an integer $k$ , does $G$ have a vertex cover of size at most $k$ ?

Relation to the Clique Problem:
The Vertex Cover problem is closely related to the Clique problem through the concept of a complement graph. The complement of a graph $G=(V,E)$ is $\bar{G}=(V, \bar{E})$ , where $(u,v) \in \bar{E}$ if and only if $(u,v) \notin E$ .

The fundamental relationship is:
A subset $S \subseteq V$ is a clique in $G$ if and only if $V - S$ is a vertex cover in $\bar{G}$ .

Proof sketch:
If $S$ is a clique in $G$ , then there are no edges between vertices of $S$ in the complement graph $\bar{G}$ . Therefore, any edge in $\bar{G}$ must have at least one endpoint in $V - S$ . This exactly means $V - S$ is a vertex cover for $\bar{G}$ .

This exact relationship provides a simple polynomial-time reduction between Clique and Vertex Cover, proving that since Clique is NP-complete, Vertex Cover is also NP-complete.

Unit5