Description
For the programming part, your code should be easy to read and understand, and demonstrate good code design and style. 1. Asymptotic Comparison [30 pt] In each of the following situations, indicate whether � = �(�), or � = Ω � , or both (i.e. � = Θ(�)). [2 pt each] �(�) �(�) a. � − 100 � − 300 b. �!/! �!/! c. 50� + log � � + (log �)! d. � log � 100�(log 10�) e. log 2� log 5� f. 10 log � log(�!) g. �!.!” � log!� h. �!/ log � � (log �)! i. (log �)!”# ! � / log � j. � (log �)! k. �!/! 5!”#!! l. �2! 3! m. �! 2! n. (log �)!”# ! 2(!”#!!)! o. � ! ! !!! �!!! 2. Asymptotic Analysis [10 pt] Prove that (log �)!” = �(�!.!). Show all steps. Hint: Use L’Hôpital’s Rule. 3.Programming [60 pt] Make sure to write your name and BU ID in a comment at the top of the program, along with your collaborator’s name and BU ID, if any. Your program must compile and run on the lab computers. To use the compiler on the lab computers, run “module load gcc” first. 2 a) Consider the infinite sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, …. Write a program that outputs the k th (k>0) digit in this sequence. For example, the 1st digit is 0, the 3rd digit is 2, and the 12th digit is 0. The function declaration is given below. int kthDigit(int k); Your job is to implement the kthDigit function in a file named “Problem3a.cpp”. Submit the single file “Problem3a.cpp” on Blackboard. [20 pt] b) Write a program that accepts an integer array nums and returns the sum closest to 333 by adding up three integers in this array. For example, if the nums = [20, 120, 200, 5], then the function should return 340 because 340 = 200 + 120 + 20 is closer to 333 than 325 = 200 + 120 + 5. If there is a tie, output the larger sum. The function declaration is given below. int sumTo333(vector nums); Your job is to implement the sumTo333 function in a file named “Problem3b.cpp”. Submit the single file “Problem3b.cpp” on Blackboard. The most efficient solution(s) will receive an extra credit of 0.1 point. [40 pt]
