=========================preview======================
(COMP171)2007springmidtermSol.pdf
Back to COMP171 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
Department of Computer Science and Engineering
COMP171: Data Structures and Algorithms
Spring 2007
Midterm Examination
SOLUTION C Please DO NOT take away
Instructors
L1: Albert C. S. CHUNG
L2: Long QUAN
L3: Huamin QU
Date: Thursday, April 12th, 2007
Time: 1900 C 2100
Venue: LTA & LTB
Your answers will be graded according to correctness, efficiency, precision and clarity.
This is a closed books, closed notes examination.
You should put aside your cell phones, PDAs, etc.
This booklet has 11 pages, you should check it carefully.
Student Name: _________________ Student ID: _________________
Email Address: _________________ Tutorial Session: _________________
I did not cheat in this examination: _________________ (Signature)
Problem
Marks
Maximum
1
29
2
22
3
15
4
17
5
17
Total
100
1. Design and Analysis of Algorithms (29 marks)
4 5 2 1 3
Let A[1..n] and B[1..n] be two different sorted arrays of size n. Each array contains exactly n elements that are sorted in an increasing order. Your task is to design an algorithm of O(log n) in time complexity for FindMedian. FindMedian finds the median of 2n distinct elements in the arrays A and B. The median can be either the middle element or the average of two middle elements. It is assumed for simplicity that n = 2k + 1 for a positive integer k, that is, k = 1,2,3,..., and n = 3,5,9,17,
Remarks:
1) You cannot merge the two arrays A and B to make a new array with the 2n elements sorted.
2) You cannot use any extra array, vector, linked list or other larger pointer structures as intermediate storage.
3) If the arrays A and B have only 2 elements each, e.g. a1, a2, b1 and b2, you can assume that the median can be found simply by calling a function MedianOfFour(a1, a2, b1, b2) in O(1) time.
(a) (5 marks) Suppose that A={1,3,5,7,9,11,13,15,17} and B={2,4,6,8,10,12,14,16,18}. The elements 9 and 10 are the medians of the two arrays, A and B, respectively. Since 9 < 10, so the median of A is smaller than the median of B, is it possible that the elements smaller than 9 in A and the elements larger than 10 in B be the candidate for the median of all 18 elements in the arrays A and B?
. Please answer this question with Yes or No.
. Please explain your Yes/No answer.
No
Because elements less than 7 in A is less than half of the elements in A and less than at least half of the elements in B. So no elements less than 7 in A could be the median we want. Similarly no elements bigger than 8 in B could be the median we want either. Median of 2n elements should be bounded by the median of A and the medi