International University of East Africa
Faculty of Science and Technology
$2102: Algorithm Analysis and Design
Test 1: Marking Guide
11 October 2013; Time 8:30- 10:00am
1. (a) What is an Algorithm? [2 marks]
v + An Algorithm is sequence of unambiguous instructions for solving
a problem, i.e. for obtaining the required output for any legitimate
input in a finite amount of time or
* An algorithm is any well-defined computational procedure that takes
some value, or set of values, as input and produces some value, or set
of values, as output
s/o) Explain the five characteristics of an Algorithm [5 marks]
‘* Input: Zero or more quantities’are externally supplied
‘* Definiteness: Each instruction is clear and unambiguous
+ Finiteness: The algorithm terminates in a finite number of steps.
* Effectiveness: Each instruction must be primitive and feasible
Output: At least one quantity is produced
_J- (a) Define the term Running time ofan algorithm [4 marks]
+ The running time of an algorithm specifies the time the algorithm takes
to produce an output. It is claculated by identifying and counting the
basic operation(s) in the algorithm
” Explain the factors that affect the running time of an algorithm, [8 marks]
« speed of CPU, bus and peripheral hardware
« design think time, programming time and debugging time
© language used and coding efficiency of the programmer
* quality of input (good, bad or average)
3. The size of inputs to an algorithm is governed by three factors. With an examples list
down these factors.(6 marks]
© the data representation, e.g, matrix
« the operations of the algorithm, e.g. spell-checker
‘* the properties of the objects in the problem, e.g. checking if a given integer is a
prime number m4 Die the pseudo. code given below. By i c
, de given below. By counting the basic operation; what is the
running time of the algorithm assuming that each baste operation takes a constant amount
/ of time, [10 marks]
0 for int i= 0; 4 < nj t+ do
o2 | intt=ali);
os | int js
oa | for j=i-1; 720; && t
eoen teak) 1
asset :
wet 1
} 3
@
—
“ Step Count
(om) roganey
fortis :tercen nn
‘ oo
het at 1 ont
a0
1 gram
1 name
in
oom
(b)
Total step counts
= (n—1) 40+ (n= 1) 40+ (n— I)n/2+ (n= 1)n/2+(n—1) + (0-1)
fe hy) ra =nP+3n—4
5. (a) Explain the importance of algorithm Analysis in Algorithm design and implementa
+ tion [2 marks] —_ 4
ay, Algorithm analysis provides tools/methods for analyzing the efficiency
of different methods of algorithm, The efficiency of the algorithm is
determined by its coat time and space ngedéd to accommodate it.
We analyze an algorfthms to make sure it will correctly solve the prob-
lem at hand.
J») Define the term asymptotic growth for an algorithm, (2 mark]
+ Asymptotic growth of an algorithm refers to the rate at which the
storage or time grows as a function of the problem size or size of
input. The absolute growth depends on the machine used to execute
the program, the compiler used to construct the program, and many
other factors. These asysmptotic growth help us in
— They give a simple characterization of an algorithm’s efficiency.
— They allow the comparison of the performances of various algorithms.
\©) Explain the three types of asymptotic growth of an Algorithm [6 Marks]
° Given a particular function g(n) , then
* Little oh : o(g(n)): defines the set of functions f(n) that grow slower than
g(n)
© Theta: 6(g(n)): defines the set of functions f(n) that grow at same rate as (7)
« Little omega: w(g(n)): defines the set of functions f(n) that grow faster than
a(n)
(a) Consider the following functions fi(n) = 3n? + 2; fa(n) = n® and fa(n) = n+1
Using the definition of limits, show that f2(n) € O(fi(n)) and fs(n) € O(fi(n)) [5
marks]
© foln) € O(fi(n)) = limp soo fin = c where ¢ is a constant
; 20) — limy-soo gg = littn seo GPE =F
Timn-ro0 #9 In-ro0 FAT aya s
@ fs(n) € O(fr(n)) = littn soo ot =, where c; is a constant
‘ fsln) — nel _ seta _
Tintin soo EF = linn-ro0 tig = littn-+00 aa = o
END