Get premium membership and access revision papers, questions with answers as well as video lessons.

Got a question or eager to learn? Discover limitless learning on WhatsApp now - Start Now!

Comp 302: Analysis Of Algorithms Question Paper

Comp 302: Analysis Of Algorithms

Course:Bachelor Of Science In Computer Science

Institution: Chuka University question papers

Exam Year:2010

CHUKA UNIVERSITY
UNIVERSITY EXAMINATIONS
THIRD YEAR EXAMINATION FOR THE AWARD OF THE DEGREE OF
BACHELOR OF SCIENCE (COMPUTER SCIENCE)

COMP 302: ANALYSIS OF ALGORITHMS

STREAM: B.SC (COMP. SCIENCE) Y3S1 TIME: 2 HOURS

DAY/DATE: TUESDAY 2/8/2011 2.30 P.M. – 4.30 P.M.
INSTRUCTIONS

1. Answer question ONE and any other two questions
2. Marks are awarded for clear and concise answers

Question ONE (30 Marks) – Compulsory
(a) While defining what an algorithm is, give FOUR of its characteristics. [5 marks]
(b) What is the order of growth of [6 marks]
(i) n3 + n2?
(ii) n3 + 1000000 n2
(iii) (n3 + n) * (n + 1)

(c) Consider the algorithm below that finds mean of a set of n numbers stored in an array.
1. Initialize the sum to 0
2. Initialize the index variable, i, to 1
3. When i<=n do the following
3.1 Increment i by 1
3.2 Add x[i] to sum;
4. Calculate and return mean sum/n
(i) Compute T(n)
(ii) Using the ‘big oh’ notation show that T (n) = O (n) [4 marks]

(d) Prove that the fractional knapsack problem has the greedy-choice property. [4 marks]
(e) Briefly describe a general sequence of steps for design of a greedy algorithm. [6 marks].
(f) How can one tell if a greedy algorithm will solve a particular optimization problem? [2 marks]
(g) Divide and conquer algorithms were developed in order to break complex problems into small subproblems whose solutions can be combined to solve the big complex problem .Outline the THREE steps followed by divide and conquer algorithms. [3 Marks]

Question TWO (20 Marks)
The procedure HIRE-ASSISTANT, given below, expresses the strategy for hiring in pseudocode. It assumes that the candidates for the office assistant job are numbered 1 through n. The procedure assumes that you are able to, after interviewing candidate i, determine if candidate i is the best candidate you have seen so far. To initialize, the procedure it creates a dummy candidate, numbered 0, who is less qualified than each of the other candidates.
HIRE-ASSISTANT(n)
1 best ? 0 ? candidate 0 is a least-qualified dummy candidate
2 for i ? 1 to n
3 do interview candidate i
4 if candidate i is better than candidate best
5 then best ? i
6 hire candidate i

(a) What is the cost (running time) of procedure HIRE-ASSISTANT described above? [5 marks]
(b) Express this cost in the ‘big oh’ notation’ [3 marks]

(c) Study the following TWO algorithms and answer the questions that follow;
ALGORITHM 1
for (i=0;i<3;i++)
{
print<<"enter dates dd:mm:yy";
read>>dates[i].day;
print>>dates[i].month;
read>>dates[i].year;
}

ALGORITHM 2
for (i =0;i< MAX ;i++)
{
for (j= MAX downto i+1; j--)
If A[j] < A[j-1] then
Exchange A[j] ? A[j-1]
}

(i) Derive running time for each of the algorithm. [8 marks]

(ii) Compare their running times. [4 marks]

Question THREE (20 Marks)

(a) What is a hash function? [2 marks]

(b) Diagrammatically show how a hash function reduces searching to O(1) Space. [4 marks]

(c) Compare the running time of sequential search and binary search. [4 marks]

(d) We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct-address dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O (1) time each; and the initialization of the data structure should take O(1) time.
[10 marks]

Question FOUR (20 Marks)

One application of dynamic programming is an algorithm that solves the problem of matrix-chain multiplication. We are given a sequence (chain) of n matrices to be multiplied, and we wish to compute the product.
The way we parenthesize a chain of matrices can have a dramatic impact on the cost of evaluating the product.
(a) Considering the cost of multiplying two matrices, give a standard algorithm (pseudocode) to do this. Use attributes rows and columns to represent the numbers of rows and columns in a matrix. [4 marks]
(b) Compute the running time for this algorithm and identify one problem with this strategy.
[4 marks]
(c) How can dynamic programming solve a general problem of Matrix chain multiplication?
[4 marks]
(d) Suppose you have one machine and a set of n jobs a1, a2, ..., an to process on that machine. Each job aj has a processing time tj, a profit pj, and a deadline dj. The machine can process only one job at a time, and job aj must run uninterruptedly for tj consecutive time units. If job aj is completed by its deadline dj, you receive a profit pj, but if it is completed after its deadline, you receive a profit of 0. Give an algorithm to find the schedule that obtains the maximum amount of profit, assuming that all processing times are integers between 1 and n. What is the running time of your algorithm? [8 marks]

Question FIVE (20 Marks)

(a) Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(n W) time, where n is number of items and W is the maximum weight of items that the thief can put in his knapsack. [8 marks]

(b) While analyzing their running times, compare the following sorting algorithms:

- Selection and insertion sort [4 marks]

- Merge sort and bubble sort [4 marks]

(c) The development of a dynamic-programming algorithm can be broken into a sequence of four steps. List them. [4 marks]

--------------------------------------------------------------------------------------------------------------
BYE KAPKWEN@CU2014

Comp 302: Analysis Of Algorithms Question Paper

More Question Papers

Popular Exams