lOMoARcPSD|29302175

Problem Solving Techniques

Chapter 1

Introduction to Algorithms
1. Define an Algorithm.
An algorithm is a step by step procedure for performing some task in a
finite amount of time.
(OR)
An algorithm is a set of well defined instructions to solve a particular
problem. It takes a set of input and produces a desired output.
2. Mention the characteristics of Algorithm.
The important characteristics of Algorithm are
Finiteness: - An algorithm must always terminate after a finite number
of steps.
Definiteness: - each step or operation of an algorithm must be simple,
precise and unambiguous.
Input: - an algorithm has 0 or more input values.
Output: An algorithm produces at least one or more outputs.
Effectiveness: each operation or instruction should be able to carry out
in a finite amount of time.
Language independent: an algorithm must be language independent so
that the instructions in an algorithm can be implemented in any of the
languages.
3. What is an Instance of a problem? Give an example.
An instance of a problem consists of the input needed to compute a
solution to the problem. Ex: Input values like {30, 50, 40, 20, 10} in a
sorting algorithm.
4. How to decide which algorithm is best suited?
 It depends on how efficient the algorithm is when higher values of
input are given.
 The possible restrictions/constraints on the input values.
 The architecture of the computer and the kind of storage devices to
be used.
 The correctness of the algorithm
lOMoARcPSD|29302175

Problem Solving Techniques

5. What is correctness of an algorithm?

An algorithm is said to be correct if for every Instance, it halts with the
correct output.
6. Explain the role of algorithms in computing.
 An algorithm is a well defined procedure that allows a computer to
solve a problem or it is a sequence of unambiguous instructions.
 An algorithm is a tool for solving a well specified computational
problem. The statement of the problem specifies in general terms
the desired input or output relationship.
7. What is an efficiency of an algorithm?
Algorithmic efficiency is a property of an algorithm which relates to the
amount of computational resources used by the algorithm.
8. Why analyzing efficiency is important? Explain with an example.
Every algorithm must use up some of computers resources and internal
memory so using efficient algorithms is more important than building
faster computers.
9. Explain algorithm as a technology.

 Algorithms act as an exact list of instructions that conduct specified

actions step by step in either hardware- or software-based routines.
 Algorithms are widely used throughout all areas of IT. In
mathematics and computer science, an algorithm usually refers to a
small procedure that solves a recurrent problem.
10. Explain the different steps in problem solving.

Computer cannot solve a problem on its own,user has to provide step by

step solutions of the problem to the computer. Following are the Steps
involved in problem solving are:
lOMoARcPSD|29302175

Problem Solving Techniques

Analyzing the problem:

 User has to clearly understand a problem before we begin to

find
the solution.

 By analyzing a problem, we would be able to find out the inputs

that our program should accept and the output it should
produce.
Designing Algorithm:
 The design of an algorithm depends mainly on the problem and
chosen design technique.

 Choice of choosing algorithm depends on the effectiveness of

algorithm.
Analysis of Algorithm: it involves
 Proving the correctness of an algorithm.

 Finding out the time and space complexity of an algorithm is

efficient.
Implementation and coding:
 The process of converting the algorithm into the format
which
can be understood by the computer to generate the desired
solution.

 Converting each step of the algorithm into one or more

statements in a programming language.
Testing and Coding:
 The process of checking whether there is any error in a
program
is called Testing.
 Debugging is the process of identifying and correcting or
removing the bugs (errors).
11. Explain different design approaches to solve a problem.
There are many ways to design algorithms for a given problem. The
following are the popular design approaches.
Brute force Algorithm: it is the straight forward approach to a problem;
it is just like iterating every possibility available to solve that
problem.
lOMoARcPSD|29302175

Problem Solving Techniques

Recursive Algorithms: problem is solved by breaking into sub problems

of the same type and calling own self again and again until the problem is
solved.
Ex: Factorial of a number, Fibonacci series
etc
Divide and Conquer: The divide and conquer strategy involves dividing
the problem into sub-problem, recursively solving them, and then
recombining them for the final solution Ex: Merge sort, Quick sort.
Greedy Approach: it is a type of algorithm that is typically used for
solving optimization problems to extract the maximum in minimum time
or with minimum resources. Ex: prim’s algorithms, kruskals algorithm.
Dynamic programming: it works by remembering the results of a
previous run and using them to arrive at new results.
Ex: knapsack problem, Floyd warshalls
algorithm.
Backtracking Algorithms: it solves a sub problem and if and when it
fails to solve the problem, the last step is undone and one starts looking
for
the solution again from the previous point.
12. Mention the Qualities of Good
Algorithm.
 They are simple but powerful and general
solutions.
 They can be easily understood by others.
 They can be easily modified if necessary.
 They are correct for clearly defined
situations.
 They are able to be understood on a number
of levels.
 They are economical in the use of computer time, computer storage
and peripherals.
 They are not dependant on being run on a particular computer or
particular programming language.
 They are able to be used as sub procedure or functions for other
problems.
13. What is analysis or performance analysis of algorithms?
Algorithms analysis refers to the task of determining the computing
time and storage space requirement of an algorithm.
 We can analyze an algorithm by two ways
1. By checking the correctness of an algorithm
2. By measuring time and space complexity of an algorithm.
lOMoARcPSD|29302175

Problem Solving Techniques

Time factor: time is measured by counting the number of key

operations such as comparisons in the sorting algorithms.
Space factor: space is measured by counting the maximum
memory
space required by the algorithm.
14. Explain priori and posterior
analysis

Priori analysis Posterior

analysis
It means checking the algorithm It means checking the algorithm
before its implementation after its implementation
Analysis is the process of Profiling is the process of executing
determining how much computing the correct program on data sets
time and storage an algorithm will and measuring the time and space
require it takes to compute the results.
This is independent of machine This is machine dependent
programming language and won’t programming language and the
involve the execution of program. compiler used.
It give approximate answer It will give exact
answer.
It uses the asymptotic notations to It doesn’t use asymptotic notations
represent how much time the to represent the time complexity of
algorithm will take in order to an algorithms
complete its execution
15. What is the difference between debugging and
profiling?

Debugging: it is the process of executing programs on sample data

sets that determine whether we get proper results, if faults occur it
has to be corrected.
Profiling: it is the process of executing a program on actual data
sets and measuring the time and space it takes to compute the
results during execution. The actual time taken by the algorithm to
process the data is called profiling.

16. Define Time complexity of an

algorithm.
Time complexity:
 The amount of time needed by a program to complete its
execution is known as Time complexity.
 The measurement of time is done in terms of number of
instructions executed by the program.
lOMoARcPSD|29302175

Problem Solving Techniques

 Thus Time Complexity depends on the Size of the program and

type of the algorithm being
 We have an algorithm A, then time complexity will be:
T (A) = C (A) + R (A) Where:
T (A) means Time Complexity
C (A) means Compile Time
R (A) means Run Time
17. Define space
complexity of an
algorithm.
The amount of memory needed by a program during its
execution is known as Space complexity.
Total memory space need by the program is the sum of
following two memory
a)Fixed Size Memory: It means the space required by simple
variables, constants, Instructions. Ex. Array.

b) Variable size Memory: It means the space required by variable

to which memory is allocated during run time. It also contains
space required while function is calling itself.
We have an algorithm A, then space complexity will be:
S (P) = C (P) + S (P) Where:
S (P) means space Complexity
C (P) means fixed size memory
S (P) means Variable size Memory
18. Write a note on operation
count and step count.
Operation count: Time is measured by counting the number of
basic operations or key operations.
Step count: Time is spent in all parts of the
program.
19. What do you mean by running time of an
algorithm?
 The running time of an algorithm refers to the length of time it
takes for it to run as a function.
 An algorithm’s running time for a given input depends on the
number of operations executed.
 Running time increases at most linearly with the size of the input.

20. Explain why analysis of an algorithm

depends on the input
size ‘n’?
 Input size n is very much important in analyzing the algorithms.
lOMoARcPSD|29302175

Problem Solving Techniques

 Some algorithms require more than one parameter to indicate the

size of their inputs.
21. What are the units for measuring running time?

Following are the some of the methods of computing the running

time of algorithms.
Operation counts: measured by counting the number of basic
operations or key operations.
Step count: time spent in all parts of the program.
Asymptotic notations (Mathematical Analysis): it is used to
describe the running time of an Algorithms.
22. Explain Orders of Growth.
 The order of growth of an algorithm is an approximation of
the time required to run a computer program as the input
size increases.

 The order of growth ignores the constant factor needed for fixed
operations and focuses instead on the operations that increase
proportional to input size.
O (1) < O (log n) < O (n) < O (n log n) < O (n2) < O (n3) < O (2n) < O (n!)

23. Briefly explain best case, average case,

and worst case time
complexity of an algorithm.
Worst case complexities:
 Considers the maximum of the time over all the inputs of size n.
 Algorithm runs the longest among all possible inputs of that size.

 It is used to find an upper bound on algorithm performance.

Best case complexities:
 Considers the minimum of the time over all the inputs of size n.
 Algorithm runs the fastest among all possible inputs of that size.

 it is used to find an lower bound on algorithm performance

Average case complexities:
 Considers the average of the time over all the inputs of size n.
 Determines the average (or expected) performance.
lOMoARcPSD|29302175

Problem Solving Techniques

24. Explain growth of functions with suitable examples.

 Growth functions are used to estimate the number of steps an
algorithm uses as its input grows.
 The largest number of steps needed to solve the given problem using
an algorithm on input of specified size is worst-case complexity.
25. What are the advantages and disadvantages of Algorithms?
Advantages:
 It is a step by step representation of a solution to a given problem,
which makes it easy to understand.
 It is not dependent on any programming language, so it is easy to
understand for anyone even without programming knowledge.
 Every step in an algorithm has its own logical sequence so it is easy
to debug
 The problem is broken down into smaller pieces or steps hence it is
easier for programmers to convert it into program
 An algorithm acts as a blueprint of a program and helps during
program development.
 An algorithm uses a
definite procedure.

Disadvantages:
 Writing algorithm takes
a long time
 Difficult to show
branching and looping in
algorithms
 Understanding and writing complex logic through algorithms can
be very difficult.

26. Explain Asymptotic notations and give an example for each.

Asymptotic notations are the mathematical notations used to
describe the running time of an algorithm when the input tends
towards a particular value or a limiting value.
There are mainly three asymptotic notations:
lOMoARcPSD|29302175

Problem Solving Techniques

 Big-O
notation
 Omega
notation
 Theta
notation

Big-O Notation (O-notation)

Big-O notation represents the upper bound of the running time of an

algorithm. Thus, it gives the worst-case complexity of an algorithm.

Big-O gives the upper bound of a function

The above expression can be described as a function f(n)belongs to the

set O(g(n)) if there exists a positive constant c such that it lies
between 0 and c g(n) for sufficiently large n
or any value of n the running time of an algorithm does not cross the time
provided by O(g(n)).
Since it gives the worst-case running time of an algorithm, it is widely
used
to analyze an algorithm as we are always interested in the worst-case
scenario.

Omega Notation ( Ω-
notation)
lOMoARcPSD|29302175

Problem Solving Techniques

Omega notation represents the lower bound of the running time of an

algorithm. Thus, it provides the best case complexity of an algorithm.

Omega gives the lower bound of a function

The above expression can be described as a function f(n) belongs to the

set Ω(g(n)) if there exists a positive constant c such that it lies
above cg(n), for sufficiently large n.
For any value of n, the minimum time required by the algorithm is given
by Omega Ω(g(n)).
Theta Notation (Θ-
notation)

Theta notation encloses the function from above and below. Since it
represents the upper and the lower bound of the running time of an
algorithm, it is used for analyzing the average-case complexity of an
algorithm.
lOMoARcPSD|29302175

Problem Solving Techniques

Theta bounds the function within constants factors

The above expression can be described as a function f(n) belongs to the

set Θ(g(n)) if there exist positive constants c1 and c2 such that it can be
sandwiched between c1g(n) and c2g(n), for sufficiently large n.
If a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n ≥
n0, then f(n) is said to be asymptotically tight
bound.

27. Write a algorithm to exchange the

values of two variables
using temporary variable.

Step 1: start
Step 2: Declare three variables a, b and t
Step 3: Input first number and second number ‘a’ and ‘b’
Step 4: set t = a
Step 5: set a=b
Step 6: set b=t
Step 7: print a and b
Step 8: stop
lOMoARcPSD|29302175

Problem Solving Techniques

28. Write a algorithm to exchange the

values of two variables
without using temporary variable.
Step 1: start
Step 2: Declare three variables a, b and t
Step 3: Input first number and second number ‘a’ and ‘b’
Step 4: set a= a + b
Step 5: set b=a - b
Step 6: set a=a - b
Step 7: print a and b
Step 8: stop
29. Write a algorithm to
count the number of
students(counting)
who scored 50 and
above marks in
examination.
Step 1: start
Step 2: Declare the
variables n, count,
and i
Step 3: read ‘n’ marks
to be processed
Step 4: Initialize
counter to zero
Set count=0
Step 5: Initialize i to
1
Set i =1
Step 6: while i is less than or equal to n, do the following
steps.
a) Read ith marks
b) If marks is greater than or equal to 50 then increment
count by 1
c) Increment i value by 1
Step 7: print count
Step 8: stop
30. Write an algorithm for summation
of ‘n ’ numbers.
Step 1: start
Step 2: Declare the variables n, sum and
i
lOMoARcPSD|29302175

Problem Solving Techniques

Step 6: while i is less than or equal to n, do the following

steps. a) Read ith number

b) Add ith number to the current value of sum
(Sum = sum + ith number)
c) Increment i value by 1
Step 7: print the value of sum
Step 8: stop
31. Write an algorithm to find the factorial of a number ‘n’.
Step 1: start
Step 2: Declare the variables n, fact
Step 3: read a number n
Step 4: Initialize fact to 1
Set fact =1
Step 5: while n is greater than or equal to 1, do the following
steps.
a) Calculate fact = fact * n

b) Decrement n value by 1
Step 6: print the value of fact
Step 7: stop
32. Write an algorithm to generate first ’n’ terms of Fibonacci
sequence.
Step 1: start
Step 2: Declare the variables a,b, c, n, i
Step 3: Initialize variable a = 0, b = 1and i = 3
Step 4: read a number n
Step 5: print a and b
Step 6: while i is lesser than or equal to n, do the following
steps.
a) c = a + b
b) print c
c) a = b
d) b = c

e) increment i by 1 ( i = i +1)
Step 7: stop
lOMoARcPSD|29302175

Problem Solving Techniques

33. Write an algorithm for reversing the digits

of an integer.
Step 1: start
Step 2: Declare the variables number, reverse,
lastdigit
Step 3: Initialize reverse to 0 i.e. set reverse=0
Step 4: read a number n
Step 5: while n not equal to 0, do the following
steps.

a) lastdigit = number % 10
b) reverse = (reverse * 10) + lastdigit
c) number = number/10
Step 6: print reverse
Step 7: stop
34. Write an algorithm to convert character representation of a
number to its equivalent decimal format.
Step 1: start
Step 2: Declare the variables n, i and value
Step 3: Initialize value to 0 i.e. set value = 0
Step 4: read character representation of an integer number n.
Step 5: loop over the characters in n from left to right ,do the following
Steps

For i=1 to n
Value = value *
10 + (ASCII
value of i th
character –
ASCII value
of
‘0’)
Step 6: print value
Step 7: stop