Study Guides (238,613)
Canada (115,253)
CS 240 (5)


12 Pages
Unlock Document

University of Waterloo
Computer Science
CS 240
Jiahua Chen

IDENTIFICATION University of Waterloo Final Preparation Examination Spring 2008 Course Number:CS 240 Course Title: Data Structures and Data Management Sections: 001, 002 Instructors: Amir H. Chinaei and Eric Y. Chen Date of Exam: | Time Period: | Duration: 2.5 hours Exam Type: Closed Book Instructions Prob Mark Max Init. † Calculators are not allowed. 1 6 † Do not open the examination until the start of the exam is 2 8 announced. 3 9 † Do not separate the pages of the examination. 4 6 † If you need additional space, use the back of the previous 5 5 page, and indicate clearly that you have done so. If you make a mistake be sure to cross it out clearly so we are sure 6 5 which answer to mark. 7 8 † In the interests of fairness and to treat all students equally, 8 6 we cannot answer any questions about the examination. If you believe there to be an error in the examination paper, 9 9 you may bring it to our attention. If we determine that there 10 2 is an error, we will inform the entire class. † Please sign your initials in the space at the bottom-right Total 69 corner of each page. CS 240 Final Page 1 of 12 Initials: 1. = 6 True/False Write either True or False in the box, and justify your answer brie°y. (a) A radix sort algorithm always take O(n) time to sort n keys. (b) Using the LZW algorithm, we compress two pieces of text (ASCII coded) into two strings of bytes (8-bits per byte). If two substrings, one from each compressed text are the same, then the two substrings in the original text corresponding to these substrings are the same. (c) Given a Hufiman tree and the correct compressed text, we consider two sub strings of bits 1 and s 2 in the compressed text. If 1 and s2are the same, then the original text represented by s 1nd s a2e also the same. CS 240 Final Page 2 of 12 Initials: 2. = 8 Running-Time Analysis Analyze the running time (in terms of n) for each of the following code fragments, using £-notation, and justify your answer brie°y. (a) = 4 int one count(n) f // base case: 1 if n == 0 return 0 // base case: 2 if n == 1 return 1 m ˆ dlogne nlˆ n >> dm=2e << dm=2e n ˆ n ¡ n r l nlˆ n >l dm=2e return one count(n l + one count(n )r g Assume n is a non-negative integer, and it can flt in one machine word. Shifting operations can be done in O(1) time. Bit 0 will be shifted in from both the left and right ends. Hint: consider the length of the bit representation of n CS 240 Final Page 3 of 12 Initials: = 4 (b) int A(n) f sum ˆ 0 for i from 1 to n for j from 1 to 3 sum++ return sum g CS 240 Final Page 4 of 12 Initials: = 9 3. Hash Tables Operations Given input 4070, 1020, 6070, 4090, 4372, 9690, 1983 and a hash function h(x) = x mod 10, show the resulting hash table (of size 10) if we resolve collisions with (a) = 3 Chaining 0 1 2 3 4 5 6 7 8 9 = 3 (b) Open addressing with linear probing 0 1 2 3 4 5 6 7 8 9 (c) = 3 Open addressing with double hashing where the second hash function is h (x) = (xmod3) + 1 0 1 2 3 4 5 6 7
More Less

Related notes for CS 240

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.