Computer Science > EXAM > FinalExam_COMP_6651_Fall_2015 (All)

FinalExam_COMP_6651_Fall_2015

Document Content and Description Below

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. Jaumar ... d 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. [Show More]

Last updated: 3 years ago

Preview 1 out of 3 pages

Buy Now

Instant download

We Accept: