pay for math 324 midterm homework solution alberta university

Question - CMPUT 204 | Winter 2011
Algorithms I
Section B1 (Stewart) Midterm Exam 1
February 18, 2011 Last name:
First name:

Time allowed: 50 minutes.
 Place all answers in the spaces provided on the question pages. JUSTIFYeach answer appropriately.
 This exam counts 15% toward your nal grade in this course.
 This exam is worth 32 points in total.
 The weight of each question is indicated in square brackets by the question number.
 There are 4 questions in this exam. Please check that your exam booklet is complete.
 This is a CLOSED BOOK exam { you may refer to one 8 1 2

11 inch double-sided sheet of notes
during the exam. No other aids allowed . Question Mark Out Of
1 9
2 6
3 9
4 8
TOTAL 32

Question 1
[9 marks]
a) [5 marks] In this questi ...Read More on, f(n ) and g(n ) are nonnegative functions dened on the set of natural numbers.
Place a checkmark beside all and only those statement(s) below that imply that g(n ) 2 ( f(n )).
 g(n ) 2 O(f (n )) and f(n ) 2 O(g (n ))
 g(n ) 2 O(f (n )) and g(n ) 2
( f(n ))
 There exist a positive real number cand a natural number n
0 such that
g (n ) = c
f (n ) 8n  n
0
 f(n ) = ( g(n ))
 f(n ) 2
( g(n )) and g(n ) 2 O(f (n ))
b) [4 marks] Are the statements below true or false? Justify your answers. 1. ( n+ 1) 2
2 ( n2
)
2. if f(n ) + g(n ) 2 ( nlog n) then f(n ) 2
( nlog n)
2

Question 2
[6 marks] All parts of this question refer to the following algorithm.
ALGORITHM Q(n )
//Input: An integer n 0
if n= 0 return 1
else return Q(n 1) + Q(n 1)
a) [3 marks] Write a recurrence relation A(n ) for the number of additions done by the above algorithm in
terms of n. (Count one addition for each time the last statement: returnQ(n 1) + Q(n 1) is executed.)
Remember the boundary condition, that is, be sure to give an expression for A(0).
b) [2 marks] Express your recurrence from part (a) using  notation. No justication required.
c) [1 mark] What does algorithm Q(n ) compute?
3

Question 3
[9 marks] This question concerns a variant of mergesort. Let c >2 be a constant . Rather
than splitting A[0 ::n 1] into two half-size arrays for the purpose of merge sorting, we do the following. If
n  c, we separate A[0 ::n 1] into carrays of roughly equal size, sort each recursively, and then merge the
c sorted arrays. If n < c, we use selection sort to sort the array.
a) [4 marks] Describe an algorithm for merging csorted arrays containing a total of nelements into one
array of size n. Make your algorithm as ecient as you can. Note: It is possible to do it in ( nlog c) time.
b) [3 marks] Give a recurrence relation describing the worst-case complexity of this variant of mergesort
when nis a power of c. Remember the boundary condition, that is, give the value of the recurrence for
n < c . You may assume that csorted arrays containing a total of nelements can be merged in ( nlog c)
time. Do not solve the recurrence.
c) [2 marks] What is the asymptotic worst-case complexity of this variant of mergesort? Remember: cis a constant .
4

Question 4
[8 marks] This question concerns breadth-rst search and depth-rst search of undirected graphs.
The algorithms BFS and DFS are reproduced for you on the back of this page.
a) [4 marks] Show how to add statements to BFS and DFS so that the algorithms check whether the input
undirected graph is a tree (a connected acyclic graph). The altered algorithms should print yesif the input
graph Gis a tree and noifG is not a tree. Add your statements to the pseudocode on the back of
this page.
b) [4 marks] Give an example of an undirected graph Gsuch that one of the algorithms discovers that Gis
not a tree after examining only a few vertices whereas the other search must explore the entire graph before
it can detect that it is not a tree. In order to specify the vertex at which the searches start and the order
in which each vertex's neighbours are examined, label the vertices a, b, c, ...and assume the searches
start at aand that each vertex's neighbours are examined in alphabetical order.
5 ...Read Less

Solution Preview - Exam 1 PARTIAL ANSWERS Question 1 [9 marks] a) [5 marks] In this question, f(n ) and g(n ) are nonnegative functions dened on the set of natural numbers. Place a checkmark beside all and only those statement(s) below that imply that g(n ) 2 ( f(n )). p g(n ) 2 O(f (n )) and f(n ) 2 O(g (n )) p g(n ) 2 O(f (n )) and g(n ) 2 ( f(n )) p There exis

Original Question Documents

N/A