CONCORDIA UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE AND SOFTWARE ENGINEERING
COMP 6651/4: Algorithm Design Techniques
Fall 2015
MidTerm - Close book exam - 3 hours
Instructor: Professor B. Jaumard
Office: EV 003.11
...
CONCORDIA UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE AND SOFTWARE ENGINEERING
COMP 6651/4: Algorithm Design Techniques
Fall 2015
MidTerm - Close book exam - 3 hours
Instructor: Professor B. Jaumard
Office: EV 003.115
Email:
[email protected]
First Name Last Name ID#
• Whenever you need to use one of the algorithms presented in the lecture slides, you need to recall
the details of that algorithm.
• Whenever you are asked to design an algorithm, you need to provide a detailed pseudo-code, as
well as the definition of all the parameters/variables used in the algorithm.
• Whenever you are asked to design an efficient algorithm, you need to provide the best algorithm
you can think of. Points will still be given for an algorithm that is not the best one, as far as it is
a correct one, and if it is not too naive/simple. However, it is better to propose a simple algorithm
than no algorithm.
||||||||||||||||||||||||||||||||||||{
Question 1. (20 points.)
An extendable array is a data structure that stores a sequence of items and supports the following
operations.
• AddToFront(x) adds x to the beginning of the sequence.
• AddToEnd(x) adds x to the end of the sequence.
• LookUp(k) returns the kth item in the sequence, or NULL if the current length of the sequence is
less than k.
Describe a simple data structure that implements an extendable array. Your AddToFront and
AddToBack algorithms should take O(1) amortized time, and your LOOKUP algorithm should take
O(1) worst-case time. The data structure should use O(n) space, where n is the current length of the
sequence.
Question 2. (20 points.)
Suppose you are given three strings A[1::n], B[1::n], and C[1::n]. Describe and analyze an algorithm
to find the maximum length of a common subsequence of all three strings. For example, given the input
strings
A = AxxBxxCDxEF; B = yyABCDyEyFy; C = zAzzBCDzEFz;
your algorithm should output the number 6, which is the length of the longest common subsequence
ABCDEF.
