CS 6363 Design and Analysis of Algorithms Sample Exam D T Huynh Professor 1 Student Name General Remarks This exam comprises 4 problems Problem 1 is assigned 25 points Problem 2 is assigned 25 points Problem t3 is assigned 25 points and Problem 4 is assigned 25 points Thus the maximum score is 100 points Unless explicitly stated are required for your algorithms and time complexity means worst case no correctness proofs complexity Provide clean answers on the exam booklet Use aditional paper only when necessary This is a closed book exam Good Luck Problem tt 4 Let A l n if it appears all significant as a black box be an array of integers An element x EA is said to be significant at least fn 47 times in A The goal is to design an O n algorithm elements assuming the linear if they exist in A l n SELECTION algorithm to compute l The linear SELECTION algorithm assumes all elements in the input array are distinct In order to apply SELECTION A to obtain a new array B such that all elements should be linear r L e L k f n l l J show how you can modify the elements in the array of B are distinct Your algorithm o r L I vi 7 2 Noting that in case A is sorted a significant element will appear consecutively 1 n 41 times in A in linear show how to use SELECTION on B to compute all significant time Analyze the running at least elements time of your algorithm B 1 1 t J e a Q u b 8 c rrL 7 4 1 1 7 2 2 VL 7 4 6e k a I L e t I C 6 d Cl C l n 1 vi L ft I J J ov J 11v A QfaJ re p u i l 1 CCU AI f f M c PA
View Full Document
Unlocking...