Ics2306:Computer Networks Question Paper
Ics2306:Computer Networks
Course:Computer Science
Institution: Meru University Of Science And Technology question papers
Exam Year:2014
1
MERU UNIVERSITY OF SCIENCE AND TECHNOLOGY P.O. Box 972-60200 – Meru-Kenya. Tel: 020-2069349, 061-2309217. 064-30320 Cell phone: +254 712524293, +254 789151411 Fax: 064-30321 Website: www.mucst.ac.ke Email: info@mucst.ac.ke
University Examinations 2012/2013
THIRD YEAR, FIRST SEMESTER EXAMINATION FOR THE DEGREE OF BACHELOR OF SCIENCE IN INFORMATION TECHNOLOGY AND COMPUTER SCIENCE
ICS 2301: DESIGN AND ANALYSIS OF ALGORITHMS DATE: AUGUST 2013 TIME: 2 HOURS
INSTRUCTIONS: Answer question one and any other two questions
QUESTION ONE – 30 MARKS
a. Briefly describe the following terms as used with algorithm analysis. (10 Marks) i. Control abstraction ii. Algorithm completeness iii. Algorithm complexity iv. Recursive function v. Algorithm efficiency
b. Dynamic programming algorithms are based on the principle of optimality. i. State the principle of optimality (2 Marks) ii. Describe optimal binary search tree problem and show that it obeys the principle of optimality. (6 Marks)
c. Briefly describe two application areas for dynamic programming algorithms. (4Marks)
d. Backtracking algorithms may be recursive or iterative. Briefly describe these options in the design of backtracking algorithms and give the difference between the two approaches. (8 Marks)
QUESTION TWO – 20 MARKS
a. Using appropriate examples, describe the two paradigms used in greedy algorithm design (6 Marks) b. Give the five components of a greedy algorithm. (5 Marks) c. Using the graph below, briefly describe the prim’s algorithm and its application in graph traversal. (9 Marks)
2
QUESTION THREE – 20 MARKS
a. Briefly describe four advantages of divide and conquer approach as an algorithm design technique. (8 Marks) b. State and briefly describe the four implementation issues for divide and conquer algorithms. (8 Marks) c. The binary search algorithm may be categorized as a “reduce and conquer” algorithm. Briefly explain this statement. (4 Marks) d. Describe one are of application for dynamic programming algorithms. (2 Marks)
QUESTION FOUR – 20 MARKS
a. Briefly describe two characteristics of each of the following algorithm design techniques (6 Marks) i. Divide and conquer algorithms ii. Brute force algorithms iii. Greedy algorithms
b. In the asymptotic analysis of algorithms, the Big-Oh notation is the most commonly used: i. Briefly describe the Big-Oh notation (2 Marks) ii. How does it differ from the theta and omega notations? (2 Marks) iii. Whys is Big-Oh the most common notation? (2 Marks)
c. Describe the branch and bound algorithm design technique and distinguish between LIFO and FIFO branch and bound. (6 Marks)
d. Brute force algorithms are commonly used in cryptanalysis for code breaking. Describe why they are the most appropriate. (2 Marks)
3
QUESTION FIVE – 20 MARKS
a. Describe three areas where divide and conquer algorithms are applicable. (6 Marks) b. Distinguish between the following concepts as used in the design and analysis of algorithms (6 Marks) i. Optimal solution and feasible solution ii. Algorithm analysis and experimentation iii. Time complexity and space complexity
c. For each of the algorithms below, describe the design strategy applied giving brief explanation of your choice. i. Insertion sort (4 Marks) ii. Merge sort (4 Marks)
More Question Papers