=========================preview======================
(COMP171)2002_spring_midterm_exam.pdf
Back to COMP171 Login to download
======================================================
COMP 171 Data Structures and Their Algorithms
2002 Spring Semester
Midterm
Date: 23 March 2002
Time: 2:00 pm C 4:00 pm
Venue: LG4 Common Room
Lecture 2 (Instructor: Dr. Siu-Wing Cheng)
Name:
E-mail:
Student No.:
This exam is closed-book and closed-notes. No calculators are allowed. If you have a question, raise your hand. Total point value is 100 points. Good luck!
All answers will be graded on the basis of clarity, correctness, ef.ciency, and precision. You should budget your time according to the points of the questions.
Question
Score
Maximum score
1
10
2
20
3
10
4
20
5
10
6
30
TOTAL
100
1.
(10 points) Given functions g(n).nand h(n).nlog2n.nd a function f(n)so that g(n).O(f(n))and f(n).O(h(n))but g(n).6.(f(n))and f(n)6..(h(n)). Write down your function and then show why it has each of the required properties.
2.
(20 points) In this question, we deal with strings of the English alphabet. A string Xof length
nis a sequence x1x2...xn, where xiis a character in the English alphabet.
Given two strings X.x1...xnand Y.y1...yvof length nand vrespectively, where
v.n. We say that Ymatches Xat position uif yi.xu+i;1, for 1.i.v, that is,
.........
xu;1xu xu+1xu+v;2xu+v;1
jjjj... jj jj
y1 y2 ...yv;1 yv
Note that 1.u.nand u+v;1.n.
You are given a library Lof strings and a string S. The string Sis stored in an array S[1::n].
The library Lis a 2D array L[1::`.1::m]. The ith row of the array Lstores the ith string.
Although each row of Lhas mentries, a string in Lmight not take up the entire row. The
special character $ is used to signify the end of a string. For example, if the .rst string is
ABC, then L[1][1]=A, L[1][2]=B, L[1][3]= C, and L[1][4]= $; if the second string is PQ,
then L[2][1]=P, L[2][2]=Q,and L[2][3]= $. In each row, the characters appearing after $
are garbage. The following are examples of Sand Lfor n.15and `.6:
.S: AATCCGAGCTTCTAG
.L:
ATCG$
GGYAA$
CGAGCTTCTA$
TTCTAG$
AATCCGAGCT$
TCCGAGCT$
For example, the string CGAGCTTCTA in Lmatches Sat position 5, the string TTC-TAG matches Sat position 10, and the string AATCCGAGCT matches Sat position 1. CGAGCTTCTA and AATCCGAGCT are the longest strings in Lthat match Sat some posi-tion. Note that more than one string in Lmay match Sat the same position, and a string in L may match Sat more than one position.
You are required to design and describe an ef.cient algorithm to .nd the longest string in L that matches Sat some position, and output an integer pair (u.v)where uis the position at which this longest string matches Sand vis the length of this longest matching string. In case there is no match, then just say so. In case there are more than one longest string in L that matches Sat some position, you can choose any one for computing the required output (u.v). For example, for the previous example of Sand L, your algorithm can output (1,10) or(5,10).
Analyze the worst-case runni