CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

DHANALAKSHMI COLLEGE OF ENGINEERING

Tambaram, Chennai

Department of Computer Science and Engineering

CS8451 – Design and Analysis of Algorithms

Year / Sem : II / IV
2 Marks Q & A

UNIT - I

Department of Computer Science and Engineering Page 1

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

UNIT- I
INTRODUCTION
PART – A

1. What is an algorithm? [M/J  12]

An algorithm is a sequence of unambiguous instructions for solving a problem. It must obtain
a required output for any legitimate input in finite amount of time.

2. Give the diagrammatic representation of notion of an algorithm. [A/M  15]

Problem

Algorithm

Input Computer Output

3. What is the formula used in Euclid’s algorithm for finding the Greatest Common Divisor
of two numbers? [A/M  17]
Formula used in Euclid’s algorithm for finding the Greatest Common Divisor of two numbers
a) GCD(m, n) = GCD(n, m mod n) until m mod n is equal to 0, since GCD(m, 0) = m.
b) It is based on repeatedly applying the equality.

4. What are the three different algorithms used to find the Greatest Common Divisor of
two numbers? [M/J  15]
Three algorithms used to find the Greatest Common Divisor of two numbers
a) Euclid’s algorithm
b) Consecutive integer checking algorithm
c) Middle school procedure

5. What is meant by algorithm design technique? [A/M  13]

An algorithm design technique is a general approach to solve problems algorithmically that is
applicable to a variety of problems from different areas of computing.

6. What are the two types of algorithm efficiencies? [N/D  13]

Two types of algorithm efficiencies
a) Time efficiency: Indicates how fast the algorithm runs
b) Space efficiency: Indicates how much extra memory the algorithm needs
8. What are the fundamental steps involved in algorithmic problem solving? [A/M  12]
Steps involved in algorithmic problem solving
a) Understanding the problem b) Determine the capabilities of
computational device
Department of Computer Science and Engineering Page 2
CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

c) Choose between exact and f) Methods for specifying the

approximate problem solving algorithm
d) Decide on appropriate data g) Proving an algorithm’s
structures correctness
e) Algorithm design techniques h) Analyzing an algorithm
i) Coding an algorithm

9. What is meant by Pseudocode? [A/M  13]

A Pseudocode is a mixture of a natural language and programming language. It is usually
more precise than natural language. It is used to specify an algorithm.
Example:
if “1”
print “I am in case 1”
if “2”
print “I am in case 2”

10. Mention some of the important problem types in algorithms. [N/D  13]
Important problem types
a) Sorting e) Combinatorial problems
b) Searching f) Geometric problems
c) String processing g) Numerical problems
d) Graph problems

11. What are the two classical geometric problems?

Two classical geometric problems
a) Closest Pair Problem
b) Convex-Hull Problem

12. What are the steps involved in the analysis of framework?

Steps involved in the analysis of framework
a) Measuring the input’s size
b) Specifying unit for measuring running time
c) Determine the order of growth
d) Compute worst-case, best-case and average-case efficiencies

13. What is the basic operation of an algorithm?

The basic operation of an algorithm is the operation that consumes most of the total
running time. It is usually the most time consuming operation in the algorithm’s innermost
loop.

14. What is meant by worst-case efficiency?

The worst-case efficiency is a time complexity when an algorithm runs for a longer time. In
Linear Search, the presence of search element in the last position is an example of
worst-case efficiency.
15. What is the running time of a program implementing the algorithm?
The running time T(n) of a program implementing the algorithm is given by the following
formula T(n) ≈ Cop x C(n), where

Department of Computer Science and Engineering Page 3

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

Cop = Time of execution of an algorithm’s basic operation on a particular computer

C(n) = The number of times the basic operation needs to be executed

16. What is meant by best-case efficiency?

The best-case efficiency is a time complexity when an algorithm runs for short time.
In Linear Search, the presence of search element in the first position is an example of
best-case efficiency.

17. When is a function said to be in O-notation?

A function f(n) is said to be in O(g(n)), if f(n) is bounded above by some constant multiple
of g(n) for all large n, i.e., if there exists some positive constant c and some non-negative
integer n0 such that f(n) <= c x g(n) for all n >= n0.

It is denoted by f(n) ε O(g(n)).

18. When is a function said to be in Ω-notation?
A function f(n) is said to be in Ω(g(n)), if f(n) is bounded below by some constant multiple
of g(n) for all large n, i.e., if there exists some positive constant c and some non-negative
integer n0 such that f(n) >= c x g(n) for all n >=n0.

It is denoted by f(n) ε Ω(g(n)).

19. When is a function said to be in θ-notation?

A function f(n) is said to be in θ(g(n)), if f(n) is bounded both above and below by some
constant multiple of g(n) for all large n, i.e., if there exists some positive constants c1, c2 and
some non-negative integer n0 such that c2 x g(n) <= f(n) <= c1 x g(n) for all n >= n0.

Department of Computer Science and Engineering Page 4

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

It is denoted by f(n) ε θ(g(n)).

20. What are the basic asymptotic efficiency classes?

Basic asymptotic efficiency classes

Class Name
1 Constant
log n Logarithmic
N Linear
n log n Linearithmic
Class Name
2
n Quadratic
n3 Cubic
2n Exponential
n! Factorial

Department of Computer Science and Engineering Page 5

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

21. What is meant by algorithm visualization?

Algorithm visualization is a technique in which images or animations are used to convey
the useful information about algorithm.

22. What are the two variations of algorithm visualization?

Variations of algorithm visualization
a) Static algorithm visualization: It shows the algorithm’s progress through a series of still
images.
b) Dynamic algorithm visualization: It shows the algorithm’s progress through a continuous
movie like representation.

23. What is meant by order of growth?

The order of growth is a method to find the growth of an algorithm for the different values
of the input size n. It is also known as rate of growth.

24. What are the different types of substitution method?

Types of substitution method
a) Forward substitution
b) Backward substitution

PART – B
1. Explain about algorithm with suitable example (Notion of algorithm).
An algorithm is a sequence of unambiguous instructions for solving a computational
problem, i.e., for obtaining a required output for any legitimate input in a finite amount of
time.

Algorithms – Computing the Greatest Common Divisor of Two Integers

(gcd(m, n): the largest integer that divides both m and n.)
Euclid’s algorithm: gcd(m, n) = gcd(n, m mod n)

Department of Computer Science and Engineering Page 6

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

Step1: If n = 0, return the value of m as the answer and stop; otherwise, proceed to
Step 2.
Step2: Divide m by n and assign the value of the remainder to r.
Step 3: Assign the value of n to m and the value of r to n. Go to Step 1.
Algorithm Euclid(m, n)
//Computes gcd(m, n) by Euclid‘s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n ≠ 0 do
r m mod n
m n
n r
return m
About This algorithm
o Finiteness: how do we know that Euclid‘s algorithm actually comes to a stop?
o Definiteness: no ambiguity
o Effectiveness: effectively computable.

Consecutive Integer Algorithm

Step1: Assign the value of min{m, n} to t.
Step2: Divide m by t. If the remainder of this division is 0, go to Step3; otherwise, go
to Step 4.
Step3: Divide n by t. If the remainder of this division is 0, return the value of t as the
answer and stop; otherwise, proceed to Step4.
Step4: Decrease the value of t by 1. Go to Step2.

About This algorithm

o Finiteness
o Definiteness
o Effectiveness
procedure
Step1: Find the prime factors of m.
Department of Computer Science and Engineering Page 7
CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

Step2: Find the prime factors of n.

Step3: Identify all the common factors in the two prime expansions found in Step1 and
Step2. (If p is a common factor occurring Pm and Pn times in m and n, respectively, it
should be repeated in min{Pm, Pn} times.)
Step4: Compute the product of all the common factors and return it as the gcd of the
numbers given.

2. Write short note on Fundamentals of Algorithmic Problem Solving

o Understanding the problem

 Asking questions, do a few examples by hand, think about special cases, etc.
o Deciding on
 Exact vs. approximate problem solving
 Appropriate data structure
o Design an algorithm
o Proving correctness
o Analyzing an algorithm

Department of Computer Science and Engineering Page 8

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

 Time efficiency : how fast the algorithm runs

 Space efficiency: how much extra memory the algorithm needs.
o Coding an algorithm

3. Discuss important problem types that you face during Algorithm Analysis.

Sorting
 Rearrange the items of a given list in ascending order.
 Input: A sequence of n numbers <a1, a2, …, an>
 Output: A reordering <a´1, a´2, …, a´n> of the input sequence such that a
´1≤a´2 ≤… ≤a´n.
 A specially chosen piece of information used to guide sorting. I.e., sort
student records by names.
Examples of sorting algorithms
 Selection sort
 Bubble sort
 Insertion sort
 Merge sort
 Heap sort …
Evaluate sorting algorithm complexity: the number of key comparisons.
 Two properties
 Stability: A sorting algorithm is called stable if it preserves the
relative order of any two equal elements in its input.
 In place: A sorting algorithm is in place if it does not require extra
memory, except, possibly for a few memory units.
Searching
 Find a given value, called a search key, in a given set.
 Examples of searching algorithms
o Sequential searching
o Binary searching…
String processing

Department of Computer Science and Engineering Page 9

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

 A string is a sequence of characters from an alphabet.

 Text strings: letters, numbers, and special characters.
 String matching: searching for a given word/pattern in a text.
Graph problems
 Informal definition
o A graph is a collection of points called vertices, some of
which are connected by line segments called edges.
 Modeling real-life problems
 Modeling WWW
 communication networks
 Project scheduling …
Examples of graph algorithms

 Graph traversal algorithms

 Shortest-path algorithms
 Topological sorting
Combinatorial problems
 The traveling salesman problem and the graph coloring problem are examples of
combinatorial problems. These are problems that ask, explicitly or implicitly, to find a
combinatorial object—such as a permutation, a combination, or a subset—that satisfies
certain constraints.
 A desired combinatorial object may also be required to have some additional property such
as a maximum value or a minimum cost.
Geometric problems
 Geometric algorithms deal with geometric objects such as points, lines, and polygons.
 The closest-pair problem is self-explanatory: given n points in the plane, find the closest
pair among them.
 The convex-hull problem asks to find the smallest convex polygon that would include all
the points of a given set.
Numerical problems
 Numerical problems, another large special area of applications, are problems that involve
mathematical objects of continuous nature: solving equations and systems of equations,
computing definite integrals, evaluating functions, and so on.

Department of Computer Science and Engineering Page 10

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

4. Discuss Fundamentals of the analysis of algorithm efficiency elaborately.

 Algorithm‘s efficiency
 Three notations
 Analyze of efficiency of Mathematical Analysis of Recursive Algorithms
 Analyze of efficiency of Mathematical Analysis of non-Recursive Algorithms

Analysis of algorithms means to investigate an algorithm’s efficiency with respect to

resources: running time and memory space.
 Time efficiency: how fast an algorithm runs.
 Space efficiency: the space an algorithm requires.
 Measuring an input‘s size
 Measuring running time
 Orders of growth (of the algorithm‘s efficiency function)
 Worst-base, best-case and average efficiency
Measuring Input Sizes
 Efficiency is defined as a function of input size.
 Input size depends on the problem.
 Example 1, what is the input size of the problem of sorting n numbers?
 Example 2, what is the input size of adding two n by n matrices?
Units for Measuring Running Time
o Measure the running time using standard unit of time measurements, such as
seconds, minutes?
o Depends on the speed of the computer.
o count the number of times each of an algorithm‘s operations is executed.
o Difficult and unnecessary
o count the number of times an algorithm‘s basic operation is executed.
o Basic operation: the most important operation of the algorithm, the operation
contributing the most to the total running time.
o For example, the basic operation is usually the most time-consuming operation in
the algorithm‘s innermost loop.

Department of Computer Science and Engineering Page 11

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

Orders of Growth
o consider only the leading term of a formula
o Ignore the constant coefficient.
Worst-Case, Best-Case, and Average-Case Efficiency
o Algorithm efficiency depends on the input size n
o For some algorithms efficiency depends on type of input.
Example: Sequential Search
o Problem: Given a list of n elements and a search key K, find an element equal to K,
if any.
o Algorithm: Scan the list and compare its successive elements with K until either a
matching element is found (successful search) of the list is exhausted (unsuccessful
search)
Worst case Efficiency
 Efficiency (# of times the basic operation will be executed) for the worst case input of size
n.
 The algorithm runs the longest among all possible inputs of size n.
Best case
 Efficiency (# of times the basic operation will be executed) for the best case input of size n.
 The algorithm runs the fastest among all possible inputs of size n.
Average case:
 Efficiency (#of times the basic operation will be executed) for a typical/random input of
size n.
 NOT the average of worst and best case

5. Explain Asymptotic Notations

Three notations used to compare orders of growth of an algorithm‘s basic operation count a.
O(g(n)): class of functions f(n) that grow no faster than g(n)

A function t(n) is said to be in O(g(n)), denoted t(n) <=O(g(n)), if t(n) is bounded

above by some constant multiple of g(n) for all large n, i.e., if there exist some positive
constant c and some nonnegative integer n0 such that t(n) <= cg(n) for all n  n0

Department of Computer Science and Engineering Page 12

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

b. Ω(g(n)): class of functions f(n) that grow at least as fast as g(n)

A function t(n) is said to be in Ω (g(n)), denoted t(n) >=(g(n)), if t(n) is bounded below by some
constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some
nonnegative integer n0 such that t (n) >=cg(n) for all n > n0

c. Θ (g(n)): class of functions f(n) that grow at same rate as g(n)

A function t(n) is said to be in Θ (g(n)), if t(n) is bounded both above and below by
some positive constant multiples of g(n) for all large n, i.e., if there exist some positive
constant c1 and c2 and some nonnegative integer n0 such that c2 g(n) <= t(n) <= c1 g(n) for
all n > n0

Department of Computer Science and Engineering Page 13

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

6. List out the Steps in Mathematical Analysis of non-recursive Algorithms.

Steps in mathematical analysis of non-recursive algorithms:
 Decide on parameter n indicating input size
 Identify algorithm‘s basic operation
 Check whether the number of times the basic operation is executed depends
only on the input size n. If it also depends on the type of input, investigate
worst, average, and best case efficiency separately.
 Set up summation for C(n) reflecting the number of times the algorithm‘s
basic operation is executed.
Example: Finding the largest element in a given array
Algorithm MaxElement (A[0..n-1])
//Determines the value of the largest element in a
given array //Input: An array A[0..n-1] of real
numbers //Output: The value of the largest element in
A

Department of Computer Science and Engineering Page 14

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

maxval A[0]
for i 1 to n-1 do
if A[i] > maxval
maxval A[i]
return maxval

7. List out the Steps in Mathematical Analysis of Recursive Algorithms.

 Decide on parameter n indicating input size

 Identify algorithm‘s basic operation
 Determine worst, average, and best case for input of size n
 Set up a recurrence relation and initial condition(s) for C(n)-the number of times the basic
operation will be executed for an input of size n (alternatively count recursive calls).
 Solve the recurrence or estimate the order of magnitude of the solution
F(n) = 1 if n = 0
n * (n-1) * (n-2)… 3 * 2 * 1 if n > 0
Recursive definition

F(n) = 1 if n = 0
n * F(n-1) if n > 0
Algorithm F(n)
if n=0
return 1 //bast case
else
return F (n -1) * n //general case
Example Recursive evaluation of n ! (2)
Two Recurrences

The one for the factorial function value: F(n)

F(n) = F(n – 1) * n for every n > 0
F(0) = 1
The one for number of multiplications to compute n!, M(n)
M(n) = M(n – 1) + 1 for every n > 0
M(0) = 0
Department of Computer Science and Engineering Page 15
CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

M(n) ∈ Θ (n)

8. Explain in detail about Tower of Hanoi.

 In this puzzle, there are n disks of different sizes and three pegs. Initially, all the disks are
on the first peg in order of size, the largest on the bottom and the smallest on top.
 The goal is to move all the disks to the third peg, using the second one as an auxiliary, if
necessary. On1y one disk can be moved at a time, and it is forbidden to place a larger disk
on top of a smaller one.

1 3

2
The general plan to the Tower of Hanoi problem.
The number of disks n is the obvious choice for the input's size indicator, and so is moving one
disk as the algorithm's basic operation. Clearly, the number of moves M(n) depends on n only, and
we get the following recurrence equation for it:
M(n) = M(n-1)+1+M(n-1)
With the obvious initial condition M(1) = 1, the recurrence relation for the number of moves M(n)
is:
M(n) = 2M(n- 1) + 1 for n> 1, M(1) = 1.

Department of Computer Science and Engineering Page 16

CS8451- DESIGN AND ANALYSIS OF ALGORITHMS IV Semester CSE

The total number of calls made by the Tower of Hanoi algorithm: n-1

= 2n-1

Department of Computer Science and Engineering Page 17