Scribd
Upload
105 views2 pages

Analysis & Design of Algorithms

This document is an exam paper for a course on Analysis and Design of Algorithms. It contains 7 questions testing students' knowledge of key algorithm concepts: 1) Question 1 asks students to explain Big O, Omega, and Theta notation and give pseudocode for recursive and iterative Fibonacci algorithms. 2) Question 2 asks students to define LIFO, FIFO data structures and explain tree terminology like leaf and root. It also asks students to construct a heap from sample data. 3) Question 3 asks students to explain divide-and-conquer strategies and merge sort, and compare quicksort to mergesort. So in summary, this exam tests foundational algorithm analysis concepts like asymptotic notation, common

Uploaded by

Manish Shrestha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
105 views2 pages

Analysis & Design of Algorithms

This document is an exam paper for a course on Analysis and Design of Algorithms. It contains 7 questions testing students' knowledge of key algorithm concepts: 1) Question 1 asks students to explain Big O, Omega, and Theta notation and give pseudocode for recursive and iterative Fibonacci algorithms. 2) Question 2 asks students to define LIFO, FIFO data structures and explain tree terminology like leaf and root. It also asks students to construct a heap from sample data. 3) Question 3 asks students to explain divide-and-conquer strategies and merge sort, and compare quicksort to mergesort. So in summary, this exam tests foundational algorithm analysis concepts like asymptotic notation, common

Uploaded by

Manish Shrestha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

ZPOKHARA UNIVERSITY

Level: Bachelor Semester – Fall Year : 2005


Programme: BE Full Marks: 100
Course: Analysis & Design of Algorithms Time : 3hrs.
Candidates are required to give their answers in their own words as far
as practicable.
The figures in the margin indicate full marks.
Attempt all the questions.

1. a) Explain the difference between the Big Oh notation, Omega notation 3


and Theta notation, and how they are used in measuring the
performance of algorithms.
b) Write pseudo-code for the algorithms for calculating the nth number 8
in the Fibonacci sequence (using fn = fn-1 + fn-2 for n > = 2, where fo =
f1 = 1), both as a recursive algorithm and an iterative algorithm.
c) What is meant by a randomised algorithm? Briefly explain the 4
difference between Las Vegas and Monte Carlo algorithms.
2. a) What is meant by a LIFO or FIFO data structure? Give an example of 3
each.
b) Explain what is meant by a tree data structure. In this context, include 7
the meaning of the following terms – leaf, root, degree, forest,
ancestors, depth.
c) Draw a sequence of diagrams showing how a heap is constructed 5
from the following data set {25, 99, 19, 100, 42, 63, 71}
3. a) What is meant by the “divide and conquer” strategy, and explain how 2
it is used to tackle large problems?
b) Explain how the merge sort algorithm works – you may find it helpful 6
to include pseudo code and/or a numerical example.
c) How is the basic quick sort algorithm different from merge sort? How 3+2+2
does it perform in the average case? What is the worst case?
4. a) Given the following symmetric cost matrix (i.e. costs are the same in 10
both directions), generate the corresponding multistage graph. Hence
determine both the minimum cost and the maximum cost between
point 1 and point 6.
1 2 3 4 5 6
1 0 2 4   
2 2 0 -3 1 5 
3 4 -3 0 -4 -2 
4  1 -4 0 4 8
5  5 -2 4 0 6
6    8 6 0
b) Explain the concept of optimal binary search trees, and give an 5
example of a situation where they can be used.
5. a) What are the differences between breadth-first search and depth-first 10
search? Use example diagrams and/or pseudo code to show how the
search process occurs in both cases.
b) Explain the concept of spanning trees, and how they apply to search 5
techniques.
6. a) Explain the backtracking approach to solving problems where there 10
are some constraints for choosing the solution, giving an example if
appropriate. What is it’s advantage compared to the “brute force”
method?
b) What is a Hamiltonian Cycle? Draw an example of a graph which has 5
a Hamiltonian Cycle (and show it clearly), and an example of a graph
which doesn’t have one.
7. Write short notes on (Any Two) 25
a) The 8-Queens problem.
b) The travelling salesman problem.
c) Matrix multiplication algorithms.
d) The Greedy method.

You might also like