## Page 37

37Chapter 2: Divide and Conquer and Randomized Algorithm

same. Furthermore, the number of times we hire a new office assistant differs for

different inputs, and it depends on the ranks of the various candidates. Since this

number depends only on the ranks of the candidates, we can represent a particular

input by listing, in order, the ranks of the candidates, i.e., ((rank(1), rank(2),…rank(n) ). Given the rank list A1 = (1,2,3,4,5,6,7,8,910), a new office

assistant is always hired 10 times, since each successive candidate is better than the

previous one, and lines 5 –6 are executed in each iteration. Gi ven the list of ranks

A2 =(10,9,8,7,6,5,4,3,2,1) , a new office assistant is hired only once, in the first

iteration. Given a list of ranks A3 =(5, 2, 1, 8, 4, 7, 10, 9, 3, 6), a new office assistant

is hired three times, upon interviewing the candidates wit h ranks 5, 8, and 10.

Recalling that the cost of our algorithm depends on how many times we hire a new

office assistant, we see that there are expensive inputs such as A1, inexpensive

inputs such as A2, and moderately expensive inputs such as A3. Consider, on the

other hand, the randomized algorithm that first permutes the candidates and then

determines the best candidate. In this case, we randomize in the algorithm, not in

the input distribution. Given a particular input, say A3 above, we cannot say how

many times the maximum is updated, because this quantity differs with each run of

the algorithm. The first time we run the algorithm on A3, it may produce the

permutation A1 and perform 10 updates; but the second time we run the algorithm,

we may produce the permutation A2 and perform only one update. The third time

we run it, we may perform some other number of updates. Each time we run the

algorithm, the execution depends on the random choices made and is likely to differ

from the previous execution of the algorithm. For this algorithm and many other

randomized algorithms, no particular input elicits its worst -case behavior. Even

your worst enemy cannot produce a bad input array, since the random permutation

makes the input order irrelevant. The randomized a lgorithm performs badly only if

the random -number generator produces an “unlucky” permutation. For the hiring

problem, the only change needed in the code is to randomly permute the array.

RANDOMIZED -HIRE -ASSISTANT(n)

randomly permute the list of candidate s

best = 0 // candidate 0 is a least -qualified dummy candidate

for i = 1 to n

interview candidate i

if candidate i is better than candidate best

best = i

hire candidate i munotes.in

~~
~~
## Page 44

44ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

to the table entry corresponding to the optimal subproblem solution chosen when

computing c[i, j]. The procedure returns the b and c tables; c[m,n] contains the

length of an LCS of X and Y.

3.4 Greedy algorithm

Algorithms for optimization problems typically go through a sequence of steps,

with a set of choices at each step. For many optimization problems, using dynamic

programming to determine the best choices is overkill; sim pler, more efficient

algorithms will do. A greedy algorithm always makes the choice that looks best at

the moment. That is, it makes a locally optimal choice in the hope that this choice

will lead to a globally optimal solution. This chapter explores optim ization

problems for which greedy algorithms provide optimal solutions.

3.4.1 An activity -selection problem

The problem of scheduling several competing activities that require exclusive use

of a common resource, with a goal of selecting a maximum -size set of mut ually

compatible activities. Suppose we have a set S = {a1, a2,…an} of n proposed

activities that wish to use a resource, such as a lecture hall, which can serve only

one activity at a time. Each activity ai has a start time si and a finish time fi ,

where 0 si < fi < . If selected, activity ai takes place during the half -open time

interval (si,fi). Activities ai and aj are compatible if the intervals (si,fi) and (si,fi)

do not overlap. That is, ai and aj are compatible if si >= fj or sj >= fi. In the acti vity-

selection problem, we wish to select a maximum -size subset of mutually compatible activities. We assume that the activities are sorted in monotonically

increasing order of finish time:

f1<= f2 <= f3 <= fn1 <= fn i 1 2 3 4 5 6 7 8 9 10 11 si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 6 7 9 9 10 11 12 14 16

For this example, the subset {a3, a9, a11} consists of mutually compatible

activities. It is not a maximum subset, however, since the subset {a1, a4, a8, a11}

is larger. In fact, {a1, a4, a8, a11} is a largest subset of mutually compatible

activities; another largest subset is {a2, a4, a9, a11}. munotes.in

## Page 45

45Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm3.4.2 Elements of the greedy strategy A greedy algorithm obtains an optimal solution to a problem by making a sequence

of choices. At each decision point, the algorith m makes choice that seems best at

the moment. This heuristic strategy does not always produce an optimal solution,

but as we saw in the activity -selection problem, sometimes it does. This section

discusses some of the general properties of greedy methods. We went through the

following steps:

1. Determine the optimal substructure of the problem.

2. Develop a recursive solution.

3. Show that if we make the greedy choice, then only one subproblem remains.

4. Prove that it is always safe to make the gree dy choice. (Steps 3 and 4 can

occur in either order.)

5. Develop a recursive algorithm that implements the greedy strategy.

6. Convert the recursive algorithm to an iterative algorithm.

Elements are as follows -

Greedy -choice property The first key in gredient is the greedy -choice property:

we can assemble a globally optimal solution by making locally optimal (greedy)

choices. In other words, when we are considering which choice to make, we make

the choice that looks best in the current problem, without considering results from

subproblems.

A problem exhibits optimal substructure if an optimal solution to the problem

contains within it optimal solutions to subproblems. This property is a key

ingredient of assessing the applicability of dynamic programmin g as well as greedy

algorithms. We usually use a more direct approach regarding optimal substructure

when applying it to greedy algorithms.

The 0-1 knapsack problem is the following. A thief robbing a store finds n items.

The ith item is worth i dollars and weighs wi pounds, where i and wi are integers.

The thief wants to take as valuable a load as possible, but he can carry at most W

pounds in his knapsack, for some integer W. Which items should he take? (We call

this the 0 -1 knapsack problem because for each item, the thief must take it or leave

it behind; he cannot take a fractional amount of an item or take an item more than

once.) munotes.in

## Page 46

46ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

In the fractional knapsack prob lem, the setup is the same, but the thief can take

fractions of items, rather than having to make a binary (0 -1) choice for each item.

You can think of an item in the 0 -1 knapsack problem as being like a gold ingot

and an item in the fractional knapsack pr oblem as more like gold dust.

3.3.3 Huffman codes

Huffman codes compress data very effectively: savings of 20% to 90% are typical,

depending on the characteristics of the data being compressed. We consider the

data to be a sequence of characters. Huffman’s greedy algorithm uses a table giving

how often each character occurs (i.e., its frequency) to build up an optimal way of

representing each character as a binary string. Suppose we have a 100,000 -

character data file that we wish to store compactly. We obse rve that the characters

in the file occur with the frequencies. a b c d e f Frequency (in thousands) 45 13 12 16 9 5 Fixed-length codeword 000 001 010 011 100 101 Variable-length codeword 0 101 100 111 1101 1100

That is, only 6 different characters appear, and the character a occurs 45,000 times.

We have many options for how to represent such a file of information. Here, we

consider the problem of designing a binary character code (or code for short) in

which each character is represented by a unique binary string, which we call a

codeword. If we use a fixed -length code, we need 3 bits to represent 6 characters:

a = 000, b = 001, ..., f = 101. This method requires 300,000 bits to code the entire

file. Can we do bet ter? A variable -length code can do considerably better than a

fixed -length code, by giving frequent characters short codewords and infrequent

characters long codewords. Figure shows such a code; here the 1 -bit string 0

represents a, and the 4 -bit string 11 00 represents f.

This code requires

(45x1) + (13x3) + (12x3 ) + (16x3) + (9x4 ) + (5x4) x 1,000 = 224,000 bits.

to represent the file, a savings of approximately 25%. In fact, this is an optimal

character code for this file.

munotes.in

## Page 47

47Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm3.5 Elementary Graph Algorithms In this topic presents methods for representing a graph and for searching a graph.

Searching a graph means systematically following the edges of the graph so as to

visit the vertices of the graph. A graph -searching algorithm can discover much

about the structure of a graph. Many algorithms begin by searching their input

graph to obtain this structural information. Several other graph algorithms elaborate

on basic graph searching. Techniques for searching a graph lie at the heart of the

field of g raph algorithms.

3.5.1 Representations of graphs

A graph is a data structure that consists of the following two components:

1. A finite set of vertices also called as nodes.

2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered

because (u, v) is not the same as (v, u) in case of a directed graph(di -graph). The

pair of the form (u, v) indicates that there is an edge from vertex u to vertex v.

The edges may contain weight/value/cost.

Graphs are used to represent many real -life appli cations: Graphs are used to

represent networks. The networks may include paths in a city or telephone

network or circuit network. Graphs are also used in social networks like linkedIn,

Facebook. For example, in Facebook, each person is represented with a v ertex(or

node). Each node is a structure and contains information like person id, name,

gender, and locale. See this for more applications of graph.

Following is an example of an undirected graph with 5 vertices.

The following two are the most commonly used representations of a graph.

1. Adjacency Matrix

2. Adjacency List

munotes.in

## Page 48

48ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

There are other representations also like, Incidence Matrix and Incidence List.

The choice of graph representation is situation -specific. It totally depends on the

type of operations to be performed and ease of use.

Adjacency Matrix:

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices

in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an

edge from vertex i to vertex j. Adjacency matrix for undirected graph is always

symmetric. Adjacency Matrix is also used to represent weighted graphs. If

adj[i][j] = w, then there is an edge from vertex i to ve rtex j with weight w.

The adjacency matrix for the above example graph is:

3URV Representation is easier to implement and follow. Removing an edge

takes O(1) time. Queries like whether there is an edge from vertex ‘u’ to vertex

‘v’ are efficient and can be done O(1).

&RQV Consumes more space O(V^2). Even if the graph is sparse(contains less

number of edges), it consumes the same space. Adding a vertex is O(V^2) time.

Please see this for a sample P ython implementation of adjacency matrix.

Adjacency List:

An array of lists is used. The size of the array is equal to the number of vertices.

Let the array be an array[]. An entry array[i] represents the list of vertices

adjacent to the Lth vertex. This r epresentation can also be used to represent a

weighted graph. The weights of edges can be represented as lists of pairs.

Following is the adjacency list representation of the above graph.

munotes.in

## Page 49

49Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm

3.5.2 Breadth -first search

Breadth -first search is one of the simplest algorithms for searching a graph and the

archetype for many important graph algorithms. Prim’s minimum -spanning -tree

algorithm and Dijkstra’s single -source shortest -paths algorithm use ideas similar

to those in breadth -first search. Given a graph G = (V; E) and a distinguished source

vertex s, breadth -first search systematically explores the edges of G to “discover”

every vertex that is reachable from s. It computes the distance (smallest number of

edges) from s to each reachable vertex. It also produces a “breadth -first tree” with

root s that contains all reachable vertices. For any vertex reachable from s, the

simple path in the breadth -first tree from s to corresponds to a “shortest path” from

s to in G, that i s, a path containing the smallest number of edges. The algorithm

works on both directed and undirected graphs.

BFS(G, s)

for each vertex u א G.V - {s}

u.color = WHITE

u.d =

uʌ NIL

s.color = GRAY

s.d - 0

sʌ = NIL

Q ĳ

ENQUEUE (Q,s)

while Q ĳ

munotes.in

## Page 50

50ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

u = DEQUEUE (Q)

for each v א G.Adj[u]

if v.color = = WHITE

v.color = GRAY

v.d = u.d + 1

Yʌ u

ENQUEUE (Q,v)

u.color = BLACK

The procedure BFS works as follows. With the exception of the source vertex s,

lines 1 –4 paint every vertex white, set u:d to be infinity for each vertex u, and set

the parent of every vertex to be NIL. Line 5 paints s gray, since we consider it to

be disc overed as the procedure begins. Line 6 initializes s.d to 0, and line 7 sets the

predecessor of the source to be NIL. Lines 8 –9 initialize Q to the queue containing

just the vertex s. The while loop of lines 10 –18 iterates as long as there remain gray

vertices, which are discovered vertices that have not yet had their adjacency lists

fully examined.

munotes.in

## Page 51

51Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm

3.5.3 Depth -first search

As in breadth -first search, whenever depth -first search discovers a vertex during a

scan of the adjacency list of an already discovered vertex u, it records this event by

VHWWLQJ Y¶V SUHGHFHVVRU DWWULEXWH Yʌ WR X 8QOLNH EUHDGWK -first search, whose

predec essor subgraph forms a tree, the predecessor subgraph produced by a depth -

first search may be composed of several trees, because the search may repeat from

multiple sources. Therefore, we define the predecessor subgraph of a depth -first

search slightly dif ferently from that of a breadth -first search:

The predecessor subgraph of a depth -first search forms a depth -first forest comprising several depth -first trees. The edges in E are tree edges. As in breadth -

first search, depth -first search colors vertices during the search to indicate their

state. Each vertex is initially white, is grayed when it is discovered in the search,

and is blackened when it is finished, that is, when its adjacency list has been

examined completely. This technique guarantees that e ach vertex ends up in exactly

one depth -first tree, so that these trees are disjoint.

munotes.in

## Page 52

52ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

3.6 Minimum Spanning Trees

Minimum spanning tree. An edge -weighted graph is a graph where we associate

weights or costs with each edge. A minimum spanning tree (MST) of an edge -

weighted graph is a spanning tree whose weight (the sum of the weights of its

edges) is no larger than the weight of any other spanning tree. Assumptions. The

graph is connected.

3.6.1 Growing a minimum spanning tree

Assume that we have a connected, undi rected graph G = (V, E) with a weight

function w : E -> R, and we wish to find a minimum spanning tree for G. The two

algorithms we consider in this chapter use a greedy approach to the problem,

although they differ in how they apply this approach. This gr eedy strategy is

captured by the following generic method, which grows the minimum spanning

tree one edge at a time. The generic method manages a set of edges A, maintaining

the following loop invariant: Prior to each iteration, A is a subset of some minim um

spanning tree.

At each step, we determine an edge (u,v) that we can add to A without violating

this invariant, in the sense that AU {(u,v)} is also a subset of a minimum spanning

tree.

We call such an edge a safe edge for A, since we can add it safely to A while

maintaining the invariant.

3.6.2 Algorithms of Kruskal and Prim

Kruskal’s algorithm finds a safe edge to add to the growing forest by finding, of all

the edges that connect any two trees in the forest, an edge (u,v ) of least weight. Let

munotes.in

## Page 53

53Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm

C1 and C2 denote the two trees that are connected by (u,v). Since (u,v) must be a

light edge connecting C1 to some other tree, Corollary 23.2 implies that (u,v) is a

safe edge for C1. Kruskal’s algorithm qualifies as a greedy algori thm because at

each step it adds to the forest an edge of least possible weight. Our implementation

of Kruskal’s algorithm is like the algorithm to compute connected components. It

uses a disjoint -set data structure to maintain several disjoint sets of ele ments. Each

set contains the vertices in one tree of the current forest.

The operation FIND -SET(u) returns a representative element from the set that

contains u. Thus, we can determine whether two vertices u and belong to the same

tree by testing whether FIND -SET(u) equals FIND -SET(v) To combine trees,

Kruskal’s algorithm calls the UNION procedure.

munotes.in

## Page 54

54ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

Figure shows how Kruskal’s algorithm works. Lines 1 –3 initialize the set A to the

empty set and create |V| trees, one containing each vertex. The for loop in lines 5 –

8 examines edges in order of weight, from lowest to highest.

The loop checks, for each edge (u,v) whether the endpoints u and belong to the

same tree. If they do, then the edge (u,v) cannot be added to the forest without

creating a cycle, and the edge is discarded. Otherwise, the two vertices belong to

different trees. In this case, line 7 adds the edge (u,v) to A, and line 8 merges the

vertices in the two trees.

Prim’s algorithm

Prim's Algorithm is used to find the minimum spanning tree from a graph. Prim's

algorithm finds the subset of edges that includes every vertex of the graph such that

the sum of the weights of the edges can be minimized.

Prim's algorithm starts with the single node and explore all the adjacent nodes with

all the co nnecting edges at every step. The edges with the minimal weights causing

no cycles in the graph got selected.

Algorithm

R Step 1: Select a starting vertex

R Step 2: Repeat Steps 3 and 4 until there are fringe vertices

R Step 3: Select an edge e connecting the tr ee vertex and fringe vertex that has

minimum weight

R Step 4: Add the selected edge and the vertex to the minimum spanning tree T

[END OF LOOP]

R Step 5: EXIT

munotes.in

## Page 55

55Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm

Example –

Construct a minimum spanning tree of the graph given in the following figure by

using prim' s algorithm.

Solution –

R Step 1 : Choose a starting vertex B.

R Step 2: Add the vertices that are adjacent to A. the edges that connecting the

vertices are shown by dotted lines.

R Step 3: Choose the edge with the minimum weight among all. i.e. BD and add

it to MST. Add the adjacent vertices of D i.e. C and E.

R Step 3: Choose the edge with the minimum weight among all. In this case, the

edges DE and CD are such edges. Add them to MST and exp lore the adjacent

of C i.e. E and A.

R Step 4: Choose the edge with the minimum weight i.e. CA. We can't choose

CE as it would cause cycle in the graph.

The graph produces in the step 4 is the minimum spanning tree of the graph

shown in the above figure.

The cost of MST will be calculated as;

cost(MST) = 4 + 2 + 1 + 3 = 10 units.

munotes.in

## Page 56

56ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

3.7 Single -Source Shortest Paths

The single source shortest path algorithm (for arbitrary weight positive or negative)

is also known Bellman -Ford algorithm is used to find minimum distance from

source vertex to any other vertex. The single -destination shortest path problem, in

which we have to find shortest paths from all vertices in the directed graph to a

single destination vertex v. This can be reduced to the single -sourc e shortest path

problem by reversing the arcs in the directed graph.

3.7.1 The Bellman -Ford algorithm

The Bellman -Ford algorithm solves the single -source shortest -paths problem in

the general case in which edge weights may be negative. Given a weighted, dire cted

graph G = (V, E) with source s and weight function w : E -> R, the Bellman -Ford

algorithm returns a boolean value indicating whether or not there is a negative -

weight cycle that is reachable from the source. If there is such a cycle, the algorithm

indicates that no solution exists. If there is no such cycle, the algorithm produces

the shortest paths and their weights. The algorithm relaxes edges, progressively

decreasing an estimate :d on the weight of a shortest path from the source s to each

vertex v א V until it achieves the actual shortest -path weight (s,v). The algorithm

returns TRUE if and only if the graph contains no negative -weight cycles that are

reachable from the source.

munotes.in

## Page 57

57Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm

3.7.2 Single -source shortest paths in directed acyclic graphs

By relaxing the edges of a weighted DAG (Directed Acyclic Graph) G = (V, E)

according to a topological sort of its vertices, we can figure out shortest paths from

a single source in (V+E) time. Shortest paths are always well described in a dag,

since even if there are negative -weight edges, no negative -weight cycles can exist.

Example –

Step1: To topologically sort vertices apply DFS (Depth First Search) and then

arrange vertices in linear order by decreasing order of finish time.

munotes.in

## Page 58

58ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

Now, take each vertex in topologically sorted order and relax each edge.

1. adj [s] ĺW x

2. 0 + 3 <

3. d [t] ĸ 3

4. 0 + 2 <

5. d [x] ĸ 2

1. adj [t] ĺ r, x

2. 3 + 1 <

3. d [r] ĸ 4

4. 3 + 5 2

munotes.in

## Page 59

59Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm

1. adj [x] ĺ y

2. 2 - 3 <

3. d [y] ĸ -1

1. adj [y] ĺ r

2. -1 + 4 < 4

3. 3 <4

4. d [r] ĸ 3

Thus the Shortest Path is:

1. s to x is 2

2. s to y is -1

3. s to t is 3

4. s to r is 3

munotes.in

## Page 60

60ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

3.7.3 Dijkstra’s algorithm

4 Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum

spanning tree. Like Prim’s MST, we generate a 637VKRUWHVWSDWK

WUHH with given source as root. We maintain two sets, one set contains

vertices included in shortest path tree, other set includes vertices not yet

included in shortest path tree. At every step of the algorithm, we find a

vertex which is in the other set (set of not yet included) and has a minimum

distance fr om the source.

5 Below are the detailed steps used in Dijkstra’s algorithm to find the shortest

path from a single source vertex to all other vertices in the given graph.

Algorithm

1) Create a set VSW6HW (shortest path tree set) that keeps track of vertice s

included in shortest path tree, i.e., whose minimum distance from

source is calculated and finalized. Initially, this set is empty.

2) Assign a distance value to all vertices in the input graph. Initialize all

distance values as INFINITE. Assign distanc e value as 0 for the

source vertex so that it is picked first.

3) While VSW6HW doesn’t include all vertices

a) Pick a vertex u which is not there in VSW6HW and has minimum

distance value.

b) Include u to VSW6HW.

c) Update distance value of all adjac ent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and

weight of edge u -v, is less than the distance value of v, then update

the distance value o f v.

6 Let us understand with the following example:

munotes.in

## Page 61

61Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm

7 The set VSW6HW is initially empty and distances assigned to vertices are {0,

INF, INF, INF, INF, INF, INF, INF} where INF indicates infinite. Now pick

the vertex with minimum distance value. The vertex 0 is picked, include it

in VSW6HW. So VSW6HWbecomes {0}. After including 0 to VSW6HW, update distance values of its adjacent vertices. Adjacent vertices of 0 are 1 and 7.

The distance values of 1 and 7 are updated as 4 and 8. Following subgraph

shows vertices and their distance values, only the vertices with finite distance values are shown. The vertices included in SPT are shown in green

colour.

8

9 Pick the vertex with minimum distance value and not already included in

SPT (not in sptSET). The vertex 1 is picked and added to sptSet. So sptSet

now becomes {0, 1}. Update the distance values of adjacent vertices of 1.

The distance value of vertex 2 beco mes 12.

10 Pick the vertex with minimum distance value and not already included in

SPT (not in sptSET). Vertex 7 is picked. So sptSet now becomes {0, 1, 7}.

Update the distance values of adjacent vertices of 7. The distance value of

vertex 6 and 8 becomes finite (15 and 9 respectively).

munotes.in

## Page 62

62ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

11 Pick the vertex with minimum distance value and not already included in

SPT (not in sptSET). Verte x 6 is picked. So sptSet now becomes {0, 1, 7,

6}. Update the distance values of adjacent vertices of 6. The distance value

of vertex 5 and 8 are updated.

12 We repeat the above steps until VSW6HWdoes include all vertices of given

graph. Finally, we get the following Shortest Path Tree (SPT).

munotes.in

## Page 63

63Chapter 3: Advanced Design And Analysis Techniques - Role Of Algorithm

3.8 Let us Sum Up

In this section, we have studied dynamic programming, greedy approach, graph

algorithm, spanning tree and single source shortest path algorithm precisely.

3.9 List of References

1. https://www.javatpoint.com/prim -algorithm

2. Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E.

Leiserson, Ronald L. Rivest, Clifford Stein, PHI Learning Pvt. Ltd -New Delhi

(2009) .

3.10 Exercises

1. Determine an LCS of (1, 0, 0, 1, 0, 1, 0, 1) and (0, 1, 0, 1, 1, 0, 1, 1, 0).

2. Prove that the fractional knapsack problem has the greedy -choice property.

3. Show how to solve the fractional knapsack problem in O (n) time.

4. Given an adjacency -list representation of a directed graph, how long does it take

to compute the out -degree of every vertex? How long does it take to compute the

in-degrees?

munotes.in

## Page 64

64ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

Unit I II

4 NUMBER -THEORETIC ALGORITHMS

AND NP – COMPLETENESS

Unit Structure: -

4.0 Objective.

4.1 Introduction.

4.2 Number Theory.

4.3 Elementary number -theoretic notions

4.3.1 Divisibility and Divisors.

4.3.2 Prime and Composite Numbers.

4.4 Greatest Common divisor.

4.4.1 Euclid’s Algorithm.

4.5 Modular Arithmetic.

4.6 The Chinese Remainder theorem.

4.7 Powers of an element.

4.8 The RSA public -key cryptosystem

4.9 NP -Completeness.

4.9.1 Dec ision vs Optimization Problems

4.9.2 What is Reduction?

4.9.3 How to prove that a given problem is NP complete?

4.10 Approximation Algorithms.

4.10.1 Introduction to Approximation Algorithms.

4.10.2 The vertex -cover problem.

4.10.3 The traveling -salesman problem.

4.10.4 The set -covering problem.

4.10.5 Subset -sum problem munotes.in

## Page 65

65Chapter 4: Number-Theoretic Algorithms and NP – Completeness

4.11 Summary

4.12 References

4.13 Bibliography

4.14 Exercise

4.0 Objective

Algorithms are heavily based on Number Theory. So many day to day problems

can be solved with simple numerical methods. We are trying to include such

materials in this topic.

4.1 Introduction

Number theory was once viewed as a beautiful but largely useless subject in pure

mathematics. Today number -theoretic algorithms ar e used widely, due in large part

to the invention of cryptographic schemes based on large prime numbers. These

schemes are feasible because we can find large primes easily, and they are secure

because we do not know how to factor the product of large prime s (or solve related

problems, such as computing discrete logarithms) efficiently. This chapter presents

some of the number theory and related algorithms that underlie such applications

4.2 Number Theory

Number Theory is widely used in Computer science as well as Mathematics.

Many algorithms and techniques are dependent on Number Theory. Mostly

Number theory is used in cryptographic study.

4.3 Elementary number -theoretic notions

This section provides a brief review of notions from elementary number theory

concerning the set of integers and the set of natural numbers.

4.3.1 Divisibility and divisors

Let us consider set Z= {…., - 2, -1,0,1, 2….} of Integers and Set N = {0, 1, 2

….}, the divisibility and divisors are defined as follows:

The notation d | a (d divides a ) means a = kd for some integer k. d is called as

divisor of a. munotes.in

## Page 66

66ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

4.3.2 Prime and composite numbers

Let us consider set Z= {…., - 2, -1,0,1, 2….} of Integers and Set N = {0, 1, 2

….}, Prime and composite numbers are defined as follows:

An integer a > 1 whose only divisors are the trivial divisors 1 and a is a prime

number or, more simply, a prime. Primes have many special properties and play a

critical role in number theory. The first 2 0 primes, in order, are

2, 3, 5, 7 ,11, 13, 17, 19; 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

if integer a > 1 is not prime then it is a composite number.

4.4 Greatest common divisor

In this section, we describe Euclid’s algorithm for efficiently computing the

greatest common divisor of two integers. When we analyze the running time, we

shall see a surprising connection with the Fibonacci numbers, which yield a

worst -case input for Euclid’s algorithm.

3.4.1 Euclid’s algorithm

Euclid’s algorithm is recursive program to find out GCD of a non -negative

number. In principle, we can compute gcd(a,b), for positive integers a and b from

the prime factorizations of a and b. The inputs a and b are arbitrary non -negative

numbers. EUCLID (a,b) if(b = = 0) return a else return EUCLID(b, a mod b)

Consider example of calculating GCD( 30,21) EUCLID (30, 21) EUCLID (30, 21) = EUCLID (21, 30 mod 21) = EUCLID (21, 9) EUCLID (21, 9) = EUCLID (21, 21 mod 9) = EUCLID (9, 3) EUCLID (9, 3) = EUCLID (3, 9 mod 3) = EUCLID (3, 0ddd) munotes.in

## Page 67

67Chapter 4: Number-Theoretic Algorithms and NP – Completeness

The worst case time complexity is calculated with the sum of a + b. As all

positive integers have common divisor as 1, time complexity will have an upper

bound of O(a+b).

4.5 Modular Arithmetic

Modular Arithmetic is system of integers where we are considering the

rema inders. This concept is highly used in cryptographic services. Given an

integer x > 1, defined as modulus, two integers a and b are said to be congruent

modulo x, if x is a divisor of their difference (i.e., if there is an integer x such that

DíE N[

Congruence modulo x is a congruence relation, meaning that it is an equivalence

relation that is compatible with the operations of addition, subtraction, and

multiplication. Congruence modulo n is denoted:

A === b mod x.

Solving modular linear equations: -

We now consider the problem of finding solutions to the equation

ax === b (mod n)

Where a > 0 and n > 0. This problem has several applications like RSA public -

key cryptosystem. Assuming a, b, and n are given, and aim to find all values of x,

modulo n, that satisfy equation The equation may have zero, one, or more than

one such solution. MODULAR-LINEAR-EQUATION-SOLVER (a,b,n) G[¶\¶ = EXTENDED-(8&/,'DQ«««««««[0 [¶EGmod n if d | b for i = 0 to d-1 print (x0 + i( n | d) ) mod n else print “no solutions”

MODULAR -LINEAR -EQUATION -SOLVER performs O ( lg n + gcd (a, n))

arithmetic operations, since EXTENDED -EUCLID pe rforms O(lg n) arithmetic

operations, and each iteration of the for loop of lines 4 –5 performs a constant

number of arithmetic operations. munotes.in

## Page 68

68ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

4.6 Chinese Remainder Theorem.

Let us consider set of pairwise relatively prime integers m1, m 2, . . . , m r. Then the

system of simultaneous congruence’s

[ŁD1 (mod m 1)

[ŁD2 (mod m 2)

.

.

.

[ŁDr (mod m r)

The above equation has a unique solution modulo M = m 1,m2, · · · m r, for any

given integers a 1, a2, . . . , a r.

Proof of CRT.

Put M = m 1 · · · m r and for each k = 1, 2, . . . , r let Mk =M /mk.

Then gcd(M k, m k) = 1 for all k.

Let y k be an inverse of M k modulo m k, for each k. Then by definition of inverse

we have M kyk ŁPRGP k). Let ,

x = a 1M1x1 + a 2M2x2 + · · · + a rMrxr.MOD M

Here x is the solution for above problem. Since operator m 1, . . . , m r are pairwise

relatively prime, any two simultaneous solutions to the system must be congruent

modulo M. Thus the solution is a unique congruence class modulo M, and the value

of x computed above is in that class.

Example: -

x===1 (mod 5)

x=== 1(mod 7)

x=== 3(mod 11)

Here 5, 7 and 11 are co -prime to each other therefore we will find out solution with

Chinese Remainder Theorem.

As all numbers are relatively co -prime. We can write

gcd ( 5,7) = gcd (7,11) = gcd(5, 11) =1 munotes.in

## Page 69

69Chapter 4: Number-Theoretic Algorithms and NP – Completeness

Find M,

We have formula for M = m 1 * m2 * m 3. ( m 1…..m n are co -prime numbers)

Here m 1 = 5, m 2 = 7, m 3 = 11.

Therefore, M = m 1 * m 2 * m 3. = 5 * 7 * 11 = 385.

Modulo M 1…M n are defined as M i = M / m i

Therefore,

M1 = M / m 1 = 385 / 5 = 77.

M2 = M / m 2 = 385 / 7 = 55.

M3 = M / m 3 = 385 / 11 = 35.

Now we have to calculate x i value,

Mixi (mod m i) = 1.

Let us Calculate x1

M1x1 (mod m 1) = 1

77. x 1 (mod 5) = 1

2. x 1 (mod 5) = 1 …… (77 mod 5 = 2)

x1 = 3 ………. ( (2 * 3 ) mod 5 = 1)

Let us Calculate x 2

M2x2 (mod m 2) = 1

55. x2 (mod 7) = 1

6. x2 (mod 7) = 1 …… ( 55 mod 7 = 6)

x2 = 6 ………. ( ( 6 * 6 ) mod 7 = 1)

Let us Calculate x 3

M3x3 (mod m 3) = 1

35. x 3 (mod 11) = 1

2. x3 (mod 11) = 1 …… ( 35 mod 11 = 2)

X3 = 6 ………. ( ( 2 * 6 ) mod 11 = 1) munotes.in

## Page 70

70ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

Let us find out x

x = (a1M1x1 + a 2M2x2 + · · · + a rMrxr.) mod M

= ((77 * 3 * 1) + (55 * 6 * 1) + (35 * 6 * 3)) mod 385

= (231 + 330 + 631 ) mod 385

= 1191 mod 385

= 36

4.7 Powers of an element:

Just as we often consider the multiples of a given element a, modulo n, we consider

the sequence of powers of a,modulo n.

a0, a1, a2, a3,…

modulo n. Indexing from 0, the 0th value in this sequence is a0 mod n D 1, and the

ith value is ai mod n. For example , the powers of 3 modulo 7 are i 0 1 2 3 4 5 6 7 8 3i mod 7 1 3 2 6 4 5 1 3 2 4.8 The RSA public -key cryptosystem

In the RSA public -key cryptosystem, a participant creates his or her public and

secret keys with the following procedure:

1. Select at random two large prime numbers p and q such that p =/ q. The

primes p and q might be, say, 1024 bits each.

2. Compute n = pq.

3. Select a small odd integer e that is relatively prime to pi (n) which, by

equation equals (p-1)(q-1)

4. Compute d as the multiplicative inverse of e, modulo pi(n) . guarantees that d

exists and is uniquely defined. We can use the technique of

5. Publish the pair P =(e, n) as the participant’s RSA public key.

6. Keep secret the pair S =(d,n)as the participant’s RSA secret key. munotes.in

## Page 71

71Chapter 4: Number-Theoretic Algorithms and NP – Completeness

4.9 NP -Completeness: -

P v/s NP Problem is very famous issue in computer Science. The Abbrevations are

defined as follows: -

P is set of problems that can be solved by a deterministic Turing machine in

Polynomial time.

NP is set of decision problems that can be solved by a Non -deterministic Turing

Machine in Polynomial time.

Here, Polynomial time is defined as fixed or known amount of interval. Further we

can say, P is subset of NP (any prob lem that can be solved by deterministic machine

in polynomial time can also be solved by non -deterministic machine in polynomial

time).

Informally, NP is set of decision problems which can be solved by a polynomial

time via a “Lucky Algorithm” ,a magical algorithm that always makes a right guess

among the given set of choices.

NP-complete problems are the hardest problems in NP set. A decision problem L

is NP -complete if:

1) L is in NP (Any given solution for NP -complete problems can be verified

quickly, but there is no efficient known solution).

2) Every problem in NP is reducible to L in polynomial time (Reduction is defined

below).

4.9.1 Decision vs Optimization Problems: -

NP-completeness applies to the realm of decision problems. It was set up this way

because it’s easier to compare the difficulty of decision problems than that of

optimization problems. In reality, though, being able to solve a decision problem

in polynomial time will often permit us to solve the corresponding optimization

problem in polynomial time (using a polynomial number of calls to the decision

problem). So, discussing the difficulty of decision problems is often really

equivalent to discussing the difficulty of optimization problems. (Source Ref 2).

For example, cons ider the vertex cover problem (Given a graph, find out the

minimum sized vertex set that covers all edges). It is an optimization problem.

Corresponding decision problem is, given undirected graph G and k, is there a

vertex cover of size k? munotes.in

## Page 72

72ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

4.9.2 What is Reduction?

Let L1 and L2 be two decision problems. Suppose algorithm A2 solves L2. That

is, if y is an input for L2 then algorithm A2 will answer Yes or No depending upon

whether y belongs to L2 or not.

The idea is to find a transformation from L1 to L2 s o that the algorithm A2 can be

part of an algorithm A1 to solve L1.

Learning reduction in general is very important. For example, if we have library

functions to solve certain problem and if we can reduce a new problem to one of

the solved problems, we sav e a lot of time. Consider the example of a problem

where we have to find minimum product path in a given directed graph where

product of path is multiplication of weights of edges along the path. If we have

code for Dijkstra’s algorithm to find shortest pa th, we can take log of all weights

and use Dijkstra’s algorithm to find the minimum product path rather than writing

a fresh code for this new problem.

4.9.3 How to prove that a given problem is NP complete?

From the definition of NP-complete, it appears impossible to prove that a problem

L is NP -Complete. By definition, it requires us to that show every problem in NP

is polynomial time reducible to L. Fortunately, there is an alternate way to prove

it. The idea is to take a kn own NP -Complete problem and reduce it to L. If

polynomial time reduction is possible, we can prove that L is NP -Complete by

transitivity of reduction (If a NP -Complete problem is reducible to L in polynomial

time, then all problems are reducible to L in p olynomial time).

4.10 Approximation Algorithms: -

An Approximate Algorithm is considered as solution for NP-COMPLETENESS in

a optimized way. E.g. vertex cover problem, the optimization problem is to find

the vertex cover with fewest vertices, and the app roximation problem is to find the

vertex cover with few vertices.

4.10.1 Introduction to Approximation Algorithms

An approximation scheme for an optimization problem is an approximation

algorithm that takes as input not only an instance of the problem, but also a value ܭ

>0 such that for any fixed ܭ ,the scheme is a (1 + ܭ )approximation algorithm. We

say that an app roximation scheme is a polynomial -time approximation scheme if munotes.in

## Page 73

73Chapter 4: Number-Theoretic Algorithms and NP – Completeness

for any fixed ܭ >0, the scheme runs in time polynomial in the size n of its input

instance.

The running time of a polynomial -time approximation scheme can increase very

rapidly as ܭ decreases. For example, the running time of a polynomial -time

approximation scheme might be O(n2/ܭ .)Ideally, if ܭ decreases by a constant factor,

the running time to achieve the desired approximation should not increase by more

than a constant factor (though not n ecessarily the same constant factor by which ܭ

decreased).

4.10.2 Vertex Cover

The vertex -cover problem is to find a vertex cover of minimum size in a given

undirected graph. We call such a vertex cover an optimal vertex cover. This

problem is the optimi zation version of an NP -complete decision problem. A vertex

cover of a graph is a subset of vertices which covers all edges. An edge is said to

be covered if its endpoints are covered.

A vertex cover of an undirected graph G =(V, E) is a subset V ’ ᄬ V such that if

(u, v) is an edge of G, then either u א V’or v א V’ (or both). The size of a vertex

cover is the number of vertices in it.

APPROX -VERTEX -COVER(G)

C =

E’ = G. E

While E ്

let (u, v) be an arbitrary edge of E’

C = C ሼݑǡݒሽ

remove from E’ every edge incident on either u or v

return C munotes.in

## Page 74

74ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

The operation of APPROX -VERTEX -COVER.

(a) The input graph G, which has 7 vertices and 8 edges.

(b) The edge (b, c), shown heavy, is the first edge chosen by APPROX -

VERTEXCOVER. Vertices b and c, shown lightly shaded, are added to the

set C containing the vertex cover being created. Edges (a, b), (c, e), and (c,

d), shown dashed, are removed since they are now covered by some vertex

in C.

(c) Edge (e, f) is chosen; vertices e and f are added to C.

(d) Edge (d, g) is chosen; vertices d and g are added to C.

(e) The set C, which is the vertex cover produced by APPROX -VERTEX -

COVER, contains the six vertices b , c, d, e, f, g.

(f) The optimal vertex cover for this problem contains only three vertices: b, d,

and e.

4.10.3 Travelling Salesman Problem (TSP):

Given a set of cities and distance between every pair of cities, the problem is to find

the shortest possible route that visits every city exactly once and returns to the

starting point.

munotes.in

## Page 75

75Chapter 4: Number-Theoretic Algorithms and NP – Completeness

Note the difference between Hamiltonian Cycle and TSP. The Hamiltoninan cycle

problem is to find if there exist a tour that visits every city exactly once. Here we

know that Hamil tonian Tour exists (because the graph is complete) and in fact

many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.

APPROX -TSP-TOUR(G,c)

select a vertex r א G. 9to be a “root” vertex

compute a minimum spanning tree T for G from root r

Let H be a list of vertices, ordered according to when they are first visited in a

preorder tree walk of T

return the hamiltonian cycle H

The operation of APPROX -TSP-TOUR.

(a) A complete undirected graph. Vertices lie on intersections of i nteger grid

lines. For example, f is one unit to the right and two units up from h. The cost

function between two points is the ordinary Euclidean distance.

(b) A minimum spanning tree T of the complete graph, as computed by MST -

PRIM. Vertex a is the roo t vertex. Only edges in the minimum spanning tree

are shown. The vertices happen to be labeled in such a way that they are

added to the main tree by MST -PRIM in alphabetical order.

(c) A walk of T , starting at a. A full walk of the tree visits the verti ces in the

order a, b, c, b, h, b, a, d, e, f, e, g, e, d ,a. A preorder walk of T lists a vertex

just when it is first encountered, as indicated by the dot next to each vertex,

yielding the ordering a, b, c, h, d, e, f, g.

munotes.in

## Page 76

76ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

(d) A tour obtained by visiting the vertices in the order given by the preorder

walk, which is the tour H returned by APPROX -TSP-TOUR. Its total cost is

approximately 19:074. (e) An optimal tour H * for the original complete

graph. Its total cost is approximat ely 14,715.

4.10.4 The set -covering problem

The set -covering problem is an optimization problem that models many problems that require resources to be allocated. Its corresponding decision problem generalizes the NP -complete vertex -cover problem and is therefore also NP -hard.

The approximation algorithm developed to handle the vertex -cover problem

doesn’t apply here, however, and so we need to try other approaches.

GREEDY -SET-COVER(X, F)

U = X

C = D

while U ്

select an S א F that maximizes |S תU |

U = U - S

C = C {S}

return C

An instance (X, F) of the set -covering problem, where X consists of the 12 black

points and F = {S1, S2, S3, S4, S5, S6}. A minimum -size set cover is C = {S3,

S4, S5} , with size 3. The greedy algorithm produces a cover of size 4 by selecting

either the sets S1, S4, S5, and S3 or the sets S1, S4, S5, and S6, in order .

munotes.in

## Page 77

77Chapter 4: Number-Theoretic Algorithms and NP – Completeness

The subset sum problem is a decision problem in computer science. In its most

general formulation, there is a multiset S of integers and a target sum T, and t he

question is to decide whether any subset of the integers sum to precisely T.[1] The

problem is known to be NP -complete. Moreover, some restricted variants of it are

NP-complete too, for example:[1]

The variant in which all input integers are positive.

The variant in which input integers may be positive or negative, and T = 0. For

example, given the set { 7, -3,-2,9000,5,8|}.{ 7, -3,-2,9000,5,8}, the answer is yes

because the subset{ -3,-2,5\}{-3,-2,5} sums to zero.

Subset sum can also be regarded as an opti mization problem: find a subset whose

sum is as close as possible to T. It is NP -hard, but there are several algorithms that

can solve it reasonably fast in practice.

4.10.5 The Subset Sum Problem: -

For the given the set S = {x 1, x2, x3, … x n } of positive integers and t, is there a

subset of S that adds up to t . Subset Sum is an optimization problem, what subset

of S adds up to the greatest total <= t . Here, w e use the notation S + x = { s+x : s

S}. we have a merge lists algorithm that run s in time proportional to the sum of

the lengths of the two lists .

EXACT -SUBSET -SUM (S,t)

1 n <- |S|

2 L 0 = <0>

3 for i = 1 to n

4 L i = MERGE -LISTS (Li-1, Li-1 +xi)

5 remove from Li every element that is greater than t

6 return the largest element in L n

4.11 Summary :-

Generally algorithm writing is a novel idea. Writing optimized algorithm is

necessary thing in computer science. Here we have attempted to provide timewise

and spacewise running of given algorithm. munotes.in

## Page 78

78ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

4.12 References: -

• Algorithms, Sa njoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani,

McGraw -Hill Higher Education (2006)

• Grokking Algorithms: An illustrated guide for programmers and other curious people, MEAP, Aditya Bhargava, http://www.manning.com/bhargava

• Research Methodology, Methods and Techniques, Kothari, C.R.,1985,

third edition, New Age International (2014) .

• Basic of Qualitative Research (3rd Edition), Juliet Corbin & Anselm

Strauss:, Sage Publications (2008)

4.13 Bibliography: -

• Introduction to Algorithms, Third Edi tion, Thomas H. Cormen, Charles E.

Leiserson, Ronald L. Rivest, Clifford Stein, PHI Learning Pvt. Ltd -New

Delhi (2009).

• Researching Information Systems and Computing, Brinoy J Oates, Sage

Publications India Pvt Ltd (2006).

• https://en.wikipedia.org/wiki/NP_ (complexity)

4.14 Exercise: -

• What is NP Problem?

• Explain Vertex Cover Problem?

• Explain Set Cover Problem?

• How travelling salesman problem comes under NP Problem?

• What is running time of Vertex Cover problem in worst case? munotes.in

## Page 79

79Chapter 5: Number-Theoretic Algorithms and NP – Completeness

Unit IV

5 RESEARCHING COMPUTING

Unit Structure

5.0 Introduction,

5.1 Purpose and products of research,

5.2 Overview of research process,

5.3 Internet research,

5.4 Participants and research ethics,

5.5 Reviewing literature,

5.6 Design and creation,

5.7 Experiments,

5.8 Quantitative data analysis,

5.9 Presentation of research .

5.10 References and Bibliography

5.11 Exercise

5.0 Introduction

Generally, Research is creation and presentation of new knowledge, ideas based on

existing concept. These ideas can be presented in regular or creative approaches.

These are used to generate new ideas, concepts ,methodologies and products as an

output. One need to thoroughly

5.1 Purpose of research

To add to the body of knowledge

To solve a problem munotes.in

## Page 80

80ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

To find out what happens

To find the evidence to inform practice

To develop a greater understanding of people and their world

To predict, plan and control

To contribute to other people's wellbeing

To test or disprove a theory

To come up with a better way

To understand another person's point of view

To create more interest in the r esearcher;

5.1 Products of research

A new or improved product

A new theory

A re-interpretation of an existing theory

A new or improved research tool or technique

A new or improved model or perspective

An in-depth study of a particular situation

An exploration of a topic, media, or field

A critical analysis.

5.2 The Research Process

Research writing is an innovative idea to work on. It is nothing but organization of

new concepts with the support of old concepts and hypothesis. One need to present

his / her ideas in a logical way and lar ger context. There are few steps which

together make research.

• Identify a Research Problem

The problem is based on general topic and issues. We need to find out the correct

issue and problem to find out the exact solution. munotes.in

## Page 81

81Chapter 5: Number-Theoretic Algorithms and NP – Completeness

• Review the Literature

Literature is nothing but the available material which will decide the direction

of the research. Literature is findings of experienced person and we can embed

their experienced views in our research.

• Determine Research Question

Any Research should be guid ed with a proper research question. A good

question should have following characteristics: -

R It must be understandable to researcher and to others.

R It should be capable of developing into a manageable research design, so

data may be collected in relation to it. Extremely abstract terms are

unlikely to be suitable.

R Connect with established theory and research. There should be a literature

on which you can draw to illuminate how your research question(s) should

be approached.

R Be neither too broad nor too narrow. See Appendix A for a brief explanation of the narrowing process and how your research question,

purpose statement, and hypothesis(es) are interconnected.

• Develop Research Methods :-

A good research is based on good research methods. Research m ethods

provides input required to carry out a research. The Data is retrieved from

Online/Offline Survey, Field visit and past research papers or documentation.

• Collect & Analyze Data

Collecting and analyzing data provides an excellent view regarding to ou tput

of the problems.

• Document the Work

Writing or documenting work is a disciplined work. While presenting

research process is quite difficult to organize the data and presenting.

• Communicate Your Research

It is very important to verify your result with targeted audience. While

communicating your research researcher should follow research methods

followed while developing research work. s munotes.in

## Page 82

82ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

5.3 Internet research

Internet research is a research method in which information and data collected from

Internet. Various qualitative journals and articles are available which are used to

retrieve the information. As a practice there are variety of journals available which

can be used to support the research.

One can collect various reviews and surveys through internet. There are various

tools and techniques available to categorize the information. After searching you

can get thousands of quick results for some topics. You c an subscribe freely to

several sites to receive updates regarding to your topic. You can subscribe to

several groups also. Internet research is not like offline resource who are bound to

certain limitation. Offline resources also makes restriction on avail ability. Internet

research can provide quick, immediate, and worldwide access to information,

although results may be affected by unrecognized bias, difficulties in verifying a

writer's credentials (and therefore the accuracy or pertinence of the informati on

obtained) and whether the searcher has sufficient skill to draw meaningful results

from the abundance of material typically available.[2]

5.4 Participants and research ethics

• Discuss intellectual property frankly

Researcher can work on any predefined or well -known topic. It is highly

possible that there might be a valuable research that is carried out by other.

Even there are so many people who directly or indirectly support and

contribute your research. It is impo rtant to give credit in the form of citation

to all people and resources who support in your research. Here authorship

should reflect the contribution.

Researchers also need to meet their ethical obligations once their research is

published: If authors lea rn of errors that change the interpretation of research

findings, they are ethically obligated to promptly correct the errors in a

correction, retraction, erratum or by other means.

• Be conscious of multiple roles

Perhaps one of the most common multiple roles for researchers is being both

a mentor and lab supervisor to students they also teach in class. Psychologists

need to be especially cautious that they don't abuse the power differential

between themselves and s tudents, say experts. They shouldn't, for example, munotes.in

## Page 83

83Chapter 5: Number-Theoretic Algorithms and NP – Completeness

use their clout as professors to coerce students into taking on additional

research duties.

• Follow informed -consent rules

Experts also suggest covering the likelihood, magnitude and duration of harm

or ben efit of participation, emphasizing that their involvement is voluntary

and discussing treatment alternatives, if relevant to the research. Keep in

mind that the Ethics Code includes specific mandates for researchers who

conduct experimental treatment resea rch. Specifically, they must inform

individuals about the experimental nature of the treatment, services that will

or will not be available to the control groups, how participants will be

assigned to treatments and control groups, available treatment alter natives

and compensation or monetary costs of participation. If research participants

or clients are not competent to evaluate the risks and benefits of participation

themselves --for example, minors or people with cognitive disabilities --then

the person who's giving permission must have access to that same information, says Koocher.

• Respect confidentiality and privacy

It is very important to preserve confidentiality and privacy of your concepts

and idea. One should also keep privacy on research method also.

5.5 Reviewing literature

Literature review is nothing but analyzing , summarizing previous work and

opinion of expert researchers. There are two kinds of literature review : -

Dissertation literature review

Researcher can write literature review for d issertation purpose. In this kind of

analysis researcher has to focus on detailed analysis. Researcher should write brief

summery on given topic.

Stand -alone literature review

If Researcher are writing a stand -alone paper, give some background on the topic

and its importance, discuss the scope of the literature you will review (for example,

the time period of your sources), and state your objective.

We can write review in following columns. munotes.in

## Page 84

84ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

• Introduction

Introduction is used to define focus and objective of literature review.

• Body

This section is more divided into subsections depending on length of the

review. This is quite important and interesting section of writing. One has to

be very dedicated while writing this section. There are some guidelines to

write the statement which is listed below: -

R Summarize and synthesize:

Give an overview of the main points of each source and combine them

into a coherent whole

R Analyze and interpret:

Don’t just paraphrase other researchers —add your own interpretations

where possible, discussing the significance of findings in relation to

the literature as a whole

R Critically evaluate:

Mention the strengths and weaknesses of your sources

R Write in well -structured paragraphs:

Use transition words and topic sentences to draw connections, comparisons and contrasts

5.6 Defining Design and Creation

Research design is the framework of research methods and techniques that allows

researchers to work in research methods that are suitable for the subject matter and

set up their studies up for success. It includes the type of research (experimental,

survey, correlational, semi -experimental, review) and also its sub -type

(experimental design, research problem, descr iptive case -study). Design is made

up of three categories viz. Data collection, measurement, and analysis.

The essential elements of the research design are:

• Accurate purpose statement

• Techniques to be implemented for collecting and analyzing research

• The method applied for analyzing collected details munotes.in

## Page 85

85Chapter 5: Number-Theoretic Algorithms and NP – Completeness

• Type of research methodology

• Probable objections for research

• Settings for the research study

• Timeline

• Measurement of analysis

Following characteristics are considered while developing research design: -

• Neutra lity:

The design should be neutral, it should not be in influence of any other pre -

concept.

• Reliability:

Research design should be according to standard rules and regularity which

improves reliability.

• Validity:

Design must be validated and verified wit h available tools.

• Generalization:

The outcome of your design should apply to a population and not just a

restricted sample.

Research design is broadly categorized in five categories: -

• Descriptive research design:

In a descriptive design, a researcher is solely interested in describing the

situation or case under their research study. It is a theory -based design

method which is created by gathering, analyzing, and presenting collected

data.

• Experimental research de sign:

Experimental research design establishes a relationship between the cause

and effect of a situation. It is a causal design where one observes the impact

caused by the independent variable on the dependent variable.

• Correlational research design: munotes.in

## Page 86

86ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

Correlational research is a non -experimental research design technique that

helps researchers establish a relationship between two closely connected

variables.

• Diagnostic research design:

In diagnostic design, the researcher is looking to evaluate the und erlying

cause of a specific topic or phenomenon. This method helps one learn more

about the factors that create troublesome situations.

5.7 Experimental research

Experimental research is research conducted with a scientific approach using two

sets of v ariables. The first set acts as a constant, and second as Quantitative research

methods . This method is used when we don’t have previous data and we need to

generate new data.

There are three primary types of experimental design:

• Pre-experimental research design : A group, or various groups, are kept

under observation after implementing factors of cause and effect.

• True experimental research design: True experimental research relies on

statistical analysis to prove or disprove a hypothesis, making it the m ost

accurate form of research.

• Quasi -experimental research design: The word “Quasi” indicates similarity. A quasi -experimental design is similar to experimental, but it is

not the same. The difference between the two is the assignment of a control

group.

Advantages of experimental research

• Experimental research allows you to test your idea in a controlled environment before taking it to market. It also provides the best method to

test your theory, thanks to the following advantages:

• Researchers have a stronger hold over variables to obtain desired results.

• The su bject or industry does not impact the effectiveness of experimental

research. Any industry can implement it for research purposes.

• The results are specific. munotes.in

## Page 87

87Chapter 5: Number-Theoretic Algorithms and NP – Completeness

• After analyzing the results, you can apply your findings to similar ideas or

situations.

• You can id entify the cause and effect of a hypothesis. Researchers can further

analyze this relationship to determine more in -depth ideas.

• Experimental research makes an ideal starting point. The data you collect is

a foundation on which to build more ideas and cond uct more research.

• Whether you want to know how the public will react to a new product or if a

certain food increases the chance of disease, experimental research is the best

place to start. Begin your research by finding subjects using QuestionPro

Audienc e and other tools today.

5.8 Quantitative Data: Definition

Quantitative data is defined as the value of data in the form of counts or numbers

where each data -set has an unique numerical value associated with it.

Quantitative data use various available tools for measuring

The most common types of quantitative data are as below:

Counter: Count equated with entities.

Measurement of physical objects: Calculating measurement of any physical

thing.

Sensory calculation: Mechanism to naturally “sense” the me asured parameters to

create a constant source of information.

Projection of data: Future projection of data can be done using algorithms and

other mathematical analysis tools.

Quantification of qualitative entities: Identify numbers to qualitative inform ation.

Quantitative Data: Collection Methods

There are two main Quantitative Data Collection Methods:

Surveys: Traditionally, surveys were conducted using paper -based methods and

have gradually evolved into online mediums. It is always effective method of

collecting data. Questions are based on relative topics. munotes.in

## Page 88

88ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

Longitudinal Studies: A type of observational research in which the market

researcher conducts surveys from a specific time period to another, i.e., over a

considerable course of time, is called lo ngitudinal survey.

Cross -sectional Studies: A type of observational research in which the market

research conducts surveys at a particular time period across the target sample is

known as cross -sectional survey. This survey type implements a questionnaire to

understand a specific subject from the sample at a definite time period.

Online/Telephonic Interviews: Telephone -based interviews are no more a novelty but these quantitative interviews have also moved to online mediums such

as Skype or Zoom. Irrespect ive of the distance between the interviewer and the

interviewee and their corresponding time zones, communication becomes one -click

away with online interviews. In case of telephone interviews, the interview is

merely a phone call away.

Computer Assisted P ersonal Interview: This is a one -on-one interview technique

where the interviewer enters all the collected data directly into a laptop or any other

similar device. The processing time is reduced and also the interviewers don’t have

to carry physical questi onnaires and merely enter the answers in the laptop.

Advantages of Quantitative Data

• Conduct in -depth research: Since quantitative data can be statistically

analyzed, it is highly likely that the research will be detailed.

• Minimum bias: There are instances in research, where personal bias is

involved which leads to incorrect results. Due to the numerical nature of

quantitative data, the personal bias is reduced to a great extent.

• Accurate results: As the results obtained are objective in nature, they are

extremely accurate.

Disadvantages of Quantitative Data

• Restricted information: Because quantitative data is not descriptive, it

becomes difficult for researchers to make decisions based solely on the

collected information.

• Depends on ques tion types: Bias in results is dependent on the question

types included to collect quantitative data. The researcher’s knowledge of

questions and the objective of research are exceedingly important while

collecting quantitative data. munotes.in

## Page 89

89Chapter 5: Number-Theoretic Algorithms and NP – Completeness

5.9 Presentation i n brief:

While presenting a research you should clearly mention your objective and research

question before audience. Author or Presenter should reach along with research

question an solution . It is very important, when considering your audience, to

know:

• who they are ?

• what their prior knowledge of the topic will be ?

• why they are likely to be interested ?

• what their needs are and how you can help them ?

The presentation should include: a short intro, your hypotheses, a brief description

of the methods, tab les and/or graphs related to your findings, and an interpretation

of your data.

The trick to giving good presentations is distilling your information down into a

few bulleted lists, diagrams, tables and graphs.

The Presentation should be divided into following groups:

• Introduction . Explain why your work is interesting. Place the study in

context – how does it relate to / follow from the scientific literature on this

subject. If it relates to any applied issues (e.g., environmental problems),

mention this here. Use some pretty visual s (photographs, drawings, etc.) to

get the audience excited about the issue and questions you are addressing.

Clearly state your hypotheses .

• Materials and Methods . Clearly summarize the design. Show s a picture of

your organisms and justify why they are ap propriate for addressing the

questions mentioned above. Show a picture of your lab setup and/or of a

person doing some of the lab work. Show a diorama of your experimental

design (with sample sizes, number of replicates, sampling frequency, etc.).

Mention what parameters you measured but do not go into detail on exact

procedures used. Do state what statistical tests you used to analyze your data.

• Results. First show a photograph (or sketch) that shows an interesting

qualitative results (e.g., trays of plant s in which one set is noticeably bigger munotes.in

## Page 90

90ANALYSIS OF ALGORITHMS AND RESEARCHING COMPUTING

than the other, a drawing of a happy Daphnia) and state that result. Then

display the results in graphical form, reminding the audience of your

hypothesis and stating whether it was supported as you do so. Use simple ,

clean, clearly labeled graphs with proper axis labels (no extraneous 3 -D

effects please). Do not use light colors (yellow, light green, or pink) in your

figures, they do not show up well when projected. Indicate the results of the

statistical tests on th e slides by including values (or asterisks/letters that

indicate the significance level) on the same slides with the graphs.

• Implications and Conclusions . Correctly interpret your results.

Constructively address sources of error and methodological difficulties.

Place your results in context and draw mplications from them.

• Acknowledgments. Thank anyone who provided advice or assistance.

Verbally thank your audience for their attention and tell them you would be

happy to answer any ques tions.

5.10 References and Bibliography

• Introduction to Algorithms, Third Edition, Thomas H. Cormen, Charles E.

Leiserson, Ronald L. Rivest, Clifford Stein, PHI Learning Pvt. Ltd -New Delhi

(2009).

• Researching Information Systems and Computing, Brinoy J Oates, Sage

Publications India Pvt Ltd (2006).

• Algorithms, Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani,

McGraw -Hill Higher Education (2006)

• Grokking Algorithms: An illustrated guide for programmers and other curious

people, MEAP, Aditya Bh argava, http://www.manning.com/bhargava

• Research Methodology, Methods and Techniques, Kothari, C.R.,1985, third

edition, New Age International (2014) .

• Basic of Qualitative Research (3rd Edition), Juliet Corbin & Anselm Strauss:,

Sage Publications (2008)

munotes.in

## Page 91

91Chapter 5: Number-Theoretic Algorithms and NP – Completeness

5.10 Exercise: -

• What is research?

• What do you mean by plagiarism?

• What research ethics should be followed by researcher?

• How to write a research paper?

munotes.in