DUKE UNIVERSITYDepartment of Computer ScienceTest 1 Review QuestionsPROBLEM 1 : (Short Ones (12 points))A. Consider the following lines of code:Integer i = null;Integer j = null;Integer k = null;i= new Integer(72);j=i;k= new Integer(72);What is the value of the following expressions:I. i == jII. i == kIII. i.equals(k)IV. 72 == j.intValue()B. Evaluate each of the following expressions:I. (((13 > 0) || (4 < 3)) && (21 % 7 == 0))II. 7 * 8 % 10 / (-2 * -2.0)C. (2) Which of the following functions grows fastest as n grows large:I. n log nII. 1 + 2 + 3 + ··· + n −1 + nIII. n log n2IV. 1 + 1/2 + 1/4 + ···+ 1/2n−1+ 1/2nV. n√nVI. There is a tie among two or more functions for fastest growth rateD. (2) The following table gives approximate running times for a program with n inputs, for various valuesof n.n time1000 5 seconds2000 20 seconds5000 2 minutes10,000 8 minutesWhich of the following best describes the likely running timeof this program for n = 100, 000?A. A few minutesTest 1 Review Questions 2B. Half an hourC. A few hoursD. Half a dayE. A few daysF. A few weeksG. (3) Bill shows you an algorithm to optimally choose classes for all students at Duke. You, being agood Computer Science student, notice that the big-Oh complexity of the algorithm is O(2n) where nis the number of students. However, Bill demonstrates the program for a sample of 100 students andit returns the schedules almost immediately.Bill says that his algorithm is good enough for Duke. He mentions something about Moore’s Lawand states that “Computers are getting faster at an exponential rate. That is, every 18 months, theydouble in speed. Even if the program is not fast enough now, it will be soon.”Bill is off a little bit on what Moore’s law means. However, given that computers continue doubling inspeed every 18 months, will the O(2n) algorithm ever be practical? Explain why or why not?H. (4) Suppose that b[] is an array of 100 elements, with all entries initialized to 0, and a[] is an arrayof N elements, each of which is an integer between 0 and 99. What is the effect of the following loop?(select all that apply)for (int j = 0; j < N; j++)b[a[j]]++;I. Sets b[0] to 0, b[1] to 1, b[2] to 2, etc.II. Sets b[0] to the number of 0s in a[], b[1] to the number of 1s in a[], etc.III. Sets b[0] to a[0], b[1] to a[0] + a[1], b[2] to a[0] + a[1] + a[2], etc.IV. Sets all entries of b[] to 1.V. Out-of-bounds array access (i.e. ArrayIndexOutOfBoundsException.VI. None of the above.I. (1) Name an interesting subarea of computer science. If you spend more than one minute on thisproblem, you’ve spent way too much time.PROBLEM 2 : (Majority (5 points))Write a method majority that takes three boolean inputs and returns the most common value. For example,majority(false, false, true) should return false, while majority(false, true, true) returns true.PROBLEM 3 : (Analyze (18 points))A. In this problem, you will analyze the big-Oh for 2 solutions sorting an array of integers.Your job is to analyze the two algorithms below, mark the line(s) of code where the majority of timeis spent, and give the tight big-Oh bounds with justification. n is the number of elements in the arraya.I. (4) Analyze sort1Test 1 Review Questions 3public static void sort1(int[] a) {for (int i = 1; i < a.length; i += 1) {int x = a[i];int j;for (j = i; j > 0 && x < a[j-1]; j -= 1)a[j] = a[j-1];a[j] = x;}}II. (4) Analyze sort2public static void sort2(int[] a ){TreeSet<Integer> set = new TreeSet<Integer>();for (int i = 0; i < a.length; i += 1)set.add(i);int k = 0;for (int elem: set){a[k] = elem;k = k + 1;}}III. (2) In most cases, sort1 and sort2 will produce the same correct results. However, in somecases, sort2 will not sort a? Describe when and why sort2 will not produce the proper result.B. Below are two examples of counting unique words from class. Your job is to analyze the two algorithmsbelow, mark the line(s) of code where the majority of time is spent, and give the tight big-Oh boundswith justification. n is the number of elements in the array list.I. (4) Analyze uniqueCountpublic class SortingUniqueCounter implements IUniqueCounter {public int uniqueCount(String[] list) {Arrays.sort(list);String last = list[0];int count = 0;// Invariant: count is number of unique words in list[0..k)for (int k = 1; k < list.length; k++) {if (!list[k].equals(last)) {last = list[k];count++;}}return count;}}II. (4) Analyze uniqueCountpublic class SlowUniqueCounter implements IUniqueCounter {public int uniqueCount(String[] list) {int count = 0;int diffSize = list.length;Test 1 Review Questions 4// Invariant: all words in range list[0..k] are unique// Elements in list[diffSize..) are duplicates of those in// list[0..diffSize)for (int k = 0; k < diffSize; k++) {String word = list[k];count++;for (int j = k + 1; j < diffSize; j++) {if (list[j].equals(word)) {list[j] = list[diffSize - 1];diffSize--;}}}return count;}}PROBLEM 4 : (Analyze (8 points))In this problem, you will analyze the big-Oh for 2 solutions to the Maximum Contiguous Subsequence Prob-lem. Given possibly negative integers A1, A2, . . . , An, find the maximum value ofPjk=iAk. The maximumcontiguous subsequence would be zero (the empty sequence) if all integers all negative. For example, if theinput is {−2, 11, −4, −13, −5, 2}, then the answer is 20 for the subsequence in bold (elements 2-4). Yourjob is to analyze the two algorithms below, mark the line(s) of code that is executed the greatest number oftimes, and give the tight big-Oh bounds with justification. n is the number of elements in the array a.A. (4 points) Analyze maxSubSum1public static int maxSubSum1(int[] a ){int seqStart, seqEnd;int maxSum = 0;for( int i = 0; i < a.length; i++ )for( int j = i; j < a.length; j++ ){int thisSum = 0;for( int k = i; k <= j; k++ )thisSum += a[ k ];if( thisSum > maxSum ){maxSum = thisSum;seqStart = i;seqEnd = j;}}return maxSum;}B. (4 points) Analyze maxSubSum2public static int maxSubSum2(int[] a ){Test 1 Review Questions 5int seqStart, seqEnd;int maxSum = 0;int thisSum = 0;for( int i = 0, j = 0; j < a.length; j++ ){thisSum += a[ j ];if( thisSum > maxSum ){maxSum = thisSum;seqStart = i;seqEnd = j;}else if( thisSum < 0 ){i = j + 1;thisSum = 0;}}return maxSum;}PROBLEM 5 : (Pix (17 points))In this problem, you will create a Pixmap Command that changes the target Pixmap by sorting each rowof Colors according the average of its three components (i.e., its grey-scale value). Thus, for each row of thePixmap, the
View Full Document
Unlocking...