DAA Review Qns

a) Explain the following terms as used in the design of algorithms
i) Space complexity
ii) Time complexity (4 marks)
b) Using a pseudo code, describe the bubble sort algorithm. (6 marks)
c) If G is an undirected graph, define the following concepts associated with the graph
i) Degree
ii) Neighbor (4 marks)
d) Briefly describe how the binary search algorithm works (4 marks)
e) Before a binary search operates on an array input of size n, what needs to be done?
(2 marks)
f) Differentiate between topological sorting and topological order as used in graph applications.
(6 marks)
g) Explain how the following graph traversal strategies work.
i. Depth First Search (DFS)
ii. Breath First Search (BFS) (4 marks)
h) Briefly describe the following graph applications
iii. Euler circuit
iv. Hamilton circuit
v. Travelling sales person problem (8 marks)
b) Define the term “recurrence relation”. (2 marks)
c) Give an explicit formula for the Fibonacci numbers (6 marks)
d) Explain a necessary and sufficient condition for a graph to have a spanning tree
(2 marks)
e) Compare dynamic programming and divide and conquer problem solving strategies.
(2 marks)
f) Describe any two computer graphs representations techniques (6 marks)
Page 1 of 5
g) Given the above graph, generate a minimum spanning tree using the Kruskal’s algorithm
(5
marks)
h) Differentiate between internal sort and external sort algorithms (4 marks)
i) Someone deposits $10,000 in a savings account at a bank yielding 5% per year with interest
compounded annually. How much money will be in the account after 30 years? (5 marks)
j) With an aid of a diagram, describe the Prim’s minimum spanning tree algorithm
(8 marks)
k) What is the maximum number of comparison required by a merge sort algorithm to sort an array
of size 6? (2 marks)
l) Show that the complexity of merge sort algorithm is O(N log2 N) (4 marks)
m) Given the following graph, sketch a Depth First Search tree. (6 marks)
i) State the meaning of an algorithm and describe what

constitutes a correct algorithm
[2 marks]
j) Distinguish between design and analysis of algorithms [4 marks]
k) Develop a computational problem and an instance for sorting an array of numbers
in descending order. Predict the output [4 marks]
l) Clearly describe the two adjacency techniques using in representing

information in graphs
[6 marks]
m) Analyze the algorithm below and state its running time in Big Oh
[5 marks]
int count_0( int N)
{
sum = 0
for i=1 to N
{
Page 2 of 5
for j=1 to N
{
If i<=j then
sum++
}
}
return sum
}
b) Use mathematical induction to prove the correctness of the following

sequence
[5 marks]
Prove 1 + 2 + 3 + … + n = n(n+1) / 2
c) Describe the Kruskal’s algorithm for solving the minimum spanning tree
problem
[4 marks]
d) State 3 advantages of carrying out correctness proof for algorithms [3

marks]
C) The following algorithm counts the number of male students enrolled in

both of 2 courses (A and B). Assume that the class sizes of both courses
are n, n>50.
function AlgorithmA(A,B)
1 result = 0;
2 for i=1 to n
3 if A[i] is male
4 for j=1 to n
5 if A[i]=B[j]
6 result = result + 1;
7 break; //stop iterating the inner for-loop.
8 return result;
Describe the best, average, and worst cases of this algorithm [Assume that
the courses are equally welcomed by male and female students, and all
students enrolled in A will enroll or not enroll in B with equal possibility]?
[6 marks]
d) Express the following recurrence using the Big Oh notation [3

marks]
2n3 + 3n2 + n
a) Discuss the following properties as they apply to formal correctness proof

techniques
[6 marks]
Page 3 of 5
i. Consistency
ii. Completeness
iii. Decidability
e) Describe the concept used in binary search to locate items in a list

[2 marks]
a) Merge sort is clearly a divide and conquer algorithm. Use a diagram as

appropriate to illustrate the divide and combine operations of merge sort on
the array A = <3, 5, 4, 2, 1, 6, 7, 6>.
[6 marks]
b) Describe the following terms as used in graph algorithms

[2 marks]
i) indegree
ii) outdegree
c) Briefly discuss the following properties as they apply to greedy algorithms
i. Greedy-Choice Property [2 marks]

ii. The Principle of Optimality [2 marks]
d) Discuss the similarity between dynamic programming and divide and conquer algorithm
design paradigms [2 marks]
e) Illustrate, step by step how bubble sort would sort the following input data
5 1 3 6 4 [4 marks]
d) You have the following coin denominations: 25c, 10c, 5c and 1c. A
customer requires a change of 63c. By listing the coins returned as change,
describe how you would apply the greedy strategy to make the change in the
most optimal manner [4 marks]
e) Discuss the relationship between tractable and polynomially bound

algorithms
[4 marks]
n) Given the following recursive algorithm, develop the iterative version

[6
marks]
Recursive algorithm:
Page 4 of 5
fib(n)
If n = = 0 or 1
Return 1
Else
Return fib(n-1) + fib(n-2);
b) Write an algorithm (in pseudocode) to compute the product of all the odd integers in a
non-empty array. [6 marks]
c) Explain 2 motivations for proving the correctness of algorithms [2 marks]
a) State 4 reasons why it is important to analyze algorithms [4 marks]

b) Describe the general strategy followed in the analysis of algorithms [5 marks]
c) Discuss the concept and motivation for an algorithm design paradigm. Give
examples [5 marks]
Page 5 of 5

DAA Review Qns

Uploaded by

Copyright:

Available Formats

DAA Review Qns

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DAA Review Qns

Uploaded by

Copyright:

Available Formats

a) Explain the following terms as used in the design of algorithms

i) State the meaning of an algorithm and describe what

l) Clearly describe the two adjacency techniques using in representing

b) Use mathematical induction to prove the correctness of the following

d) State 3 advantages of carrying out correctness proof for algorithms [3

C) The following algorithm counts the number of male students enrolled in

d) Express the following recurrence using the Big Oh notation [3

a) Discuss the following properties as they apply to formal correctness proof

e) Describe the concept used in binary search to locate items in a list

a) Merge sort is clearly a divide and conquer algorithm. Use a diagram as

b) Describe the following terms as used in graph algorithms

i. Greedy-Choice Property [2 marks]

e) Discuss the relationship between tractable and polynomially bound

n) Given the following recursive algorithm, develop the iterative version

a) State 4 reasons why it is important to analyze algorithms [4 marks]

You might also like