THEORY EXAMINATION (SEM–VI) 2016-17 APPROXIMATION AND RANDOMIZED ALGORITHMS

APPROXIMATION AND RANDOMIZED ALGORITHMS (NCS064)

Time: 3 Hours  Max Marks: 100

SECTION–A (Short Answer Questions)

(10 × 2 = 20 Marks)

(a) Principle of optimality

The principle of optimality states that an optimal solution of a problem contains optimal solutions of its subproblems. It is the foundation of dynamic programming.

(b) Linear programming

Linear programming is a mathematical technique used to maximize or minimize a linear objective function, subject to a set of linear constraints.

(c) Solve the recurrence relation

Given:

T(n)=3T(n/2)+n,T(1)=1T(n) = 3T(n/2) + n,\quad T(1)=1T(n)=3T(n/2)+n,T(1)=1

Using Master Theorem:

a=3a = 3a=3, b=2b = 2b=2, f(n)=nf(n)=nf(n)=n

nlog⁡ba=nlog⁡23n^{\log_b a} = n^{\log_2 3}nlogb​a=nlog2​3

Since f(n)=O(nlog⁡23−ϵ)f(n) = O(n^{\log_2 3 - \epsilon})f(n)=O(nlog2​3−ϵ),

T(n)=Θ(nlog⁡23)T(n) = \Theta(n^{\log_2 3})T(n)=Θ(nlog2​3) 

(d) Order of growth

Order of growth describes how the running time or space of an algorithm increases with input size.

(e) Θ-notation

Θ-notation gives the tight bound of an algorithm, meaning it bounds the growth both from above and below.

(f) Examples of randomized algorithms

Randomized Quick Sort                                  Randomized Minimum Cut algorithm

(g) Amortized efficiency

Amortized efficiency is the average time per operation over a sequence of operations, even if some operations are expensive.

(h) Applications of approximation algorithms

Traveling Salesperson Problem (TSP)              Knapsack problem

(i) Derandomized algorithms

Derandomized algorithms are deterministic algorithms that simulate randomized algorithms by removing randomness.

(j) Bin packing

Bin packing is the problem of packing items of different sizes into a minimum number of bins of fixed capacity.

SECTION–B (Long Answer Questions)

(Attempt any FIVE – 5 × 10 = 50 Marks)

2(a) Simplex method

The simplex method is an iterative algorithm used to solve linear programming problems.

Steps:

Convert inequalities into equations using slack variables        Write initial simplex table

Identify pivot element                                                              Perform row operations

Repeat until optimal solution is obtained

Advantages:

Efficient for large problems                                                      Systematic procedure

2(b) Steps involved in analyzing an algorithm

Algorithm analysis involves:                                                     Identifying basic operations

Counting number of operations                                              Expressing time as a function of input size

Finding best, worst, and average case                                     Using asymptotic notations

Example: Linear search takes Θ(n) time in worst case.

2(c) Sorting algorithm using divide and conquer

Merge Sort uses divide and conquer:                                   Divide array into halves

Recursively sort each half                                                       Merge sorted halves

Time complexity:

T(n)=2T(n/2)+n=Θ(nlog⁡n)T(n) = 2T(n/2) + n = \Theta(n\log n)T(n)=2T(n/2)+n=Θ(nlogn) 

2(d) P, NP, and NP-Complete problems

P: Problems solvable in polynomial time

NP: Problems whose solutions can be verified in polynomial time

NP-Complete: Hardest problems in NP

If any NP-Complete problem is solved in polynomial time, then P = NP.

2(e) Linear Programming (LP)

An LP problem consists of:                                                  Linear objective function

Linear constraints                                                                Non-negative decision variables

Example: Resource allocation problems.

2(f) Permutation routing in a hypercube

Permutation routing involves sending data from each node to a unique destination node in a hypercube network.

Properties:

Parallel communication                                                      Time complexity: O(log⁡n)O(\log n)O(logn)

2(g) Euclidean Traveling Salesperson Problem (TSP)

In Euclidean TSP:                                                               Cities are points in plane

Distance is Euclidean

Approximation algorithms use:                                         Minimum spanning tree

Triangle inequality

2(h) k-median on a cycle

In k-median problem:                                                       Choose k facility locations

Minimize sum of distances

On a cycle, dynamic programming or approximation methods are used to achieve near-optimal solutions.

SECTION–C (Very Long Answer Questions)

(Attempt any TWO – 2 × 15 = 30 Marks)

3. Approximation algorithm for TSP using MST

Assumption: Triangle inequality holds.

Algorithm:                                                                    Compute Minimum Spanning Tree (MST)

Perform preorder traversal of MST                                Convert traversal into Hamiltonian cycle

Approximation ratio:

Cost≤2×OPT\text{Cost} \leq 2 \times \text{OPT}Cost≤2×OPT

Advantages:

Simple                                                                           Polynomial time

4. Approximation algorithm for Knapsack problem

For 0/1 Knapsack:                                                         Exact solution is NP-Hard

Approximation approach:                                         Sort items by value/weight ratio

Select items greedily                                                    Compare greedy solution with single highest-value item

Guarantee:
Achieves at least 50% of optimal value.

5. Randomized algorithms using inequalities and random variables

Randomized algorithms use:                                       Random variables

Expected values                                                           Probabilistic bounds

Examples:

Randomized Quick Sort                                               Randomized hashing

Basic inequalities used:                                             Markov’s inequality

Chebyshev’s inequality                                                They help analyze expected running time and error probability.