=========================preview======================
(comp271)[2009](f)midterm~cs_fmh^_10193.pdf
Back to COMP271 Login to download
======================================================
COMP 271 Design and Analysis of Algorithms Fall 2009 Midterm Exam
1. Quick-Answer Questions (4 5 =20pts)
Foreach questionbelow,writedowntheasymptotic(using ) result. Youdonotneed to justify your answers.
n ..i
. 2
1.1 What is ?
3
i=1
1.2 What is the solution of the recurrence T (n)=8 T (n/2)+(n),T (1)=1?Youcan assume that n is a power of 2.
1.3 How many random numbers does Randomized Quicksort need to generate when sorting n elements?
1.4Supposethat onedayyougot a magicunion-.nd structurethat supports Create-Set, Union, and Find-Set operations all in O(1) time per operation. If you use this magic union-.nd structure in Kruskals algorithm on a graph whose edges are giveninaweight-sorted order,what willbetherunning timeofKruskalsalgorithm? Express your result in terms of |V |and |E|, the number of vertices and the number of edges in the graph, respectively.
1.5 In an undirectedgraph with n vertices and no cycles, whatisthe maximumpossible number of edges?
2.
(20pts) In Homework 1 you designed an algorithm to .nd a local minimum in an array. Now you are to do the same on a binary tree. More precisely, you are given a complete binary tree T . A completebinary tree ofheight h has exactly n =2h .1 nodes. Each node stores a real number. We assume that all these numbers are distinct. A local minimum on a binary tree is a node whose number is smaller than all of its neighbors. Note that the root of the tree has two neighbors, a leaf has one neighbor, while any other node has three neighbors. In the example below, the nodes numbered with 1, 5, and 6 are all local minima. Your algorithm only needs to .nd one if there are multiple local minima. Note that there is at least one local minimum no matter how the numbers are stored; in particulartheglobalminimumisalwaysalocal minimum,but .ndingtheglobal minimum takes O(n)time. For full credits your algorithm should run in O(logn)time.

3.
(20 pts)To celebrate the .nishing of the midterm exams you get drunk at the university bar. Then you try to get back to your dorm using your remaining sense of directions. To make things simple lets assume that UST is on an in.nite one-dimensional line as illustrated below, and there are n steps from the bar to the dorm. Starting from the bar you begin to perform a random walk towards your dorm. As you get soberer your sense of directions improves: During the i-th second, with probability 1 . 1 you take



i
one step towards your dorm, while with probability 1 you take one step away from your
i
1
dorm. After n seconds,howfar awayfromthedorm willyoube(in number of steps) in expectation?
dorm
UST bar n steps

1
prob.
You prob. 1 . 1
ii
4.
(20 pts)Given a connected, undirected graph G =(V, E). In Homework 2 you designed an algorithm to detect if there is a cycle in G. Now you are in addition given a vertex s in thegraph, andyourjobis todesign an algorithm thatdetectsif thereis a cyclein G that passes t