CS 170 Reading Quiz -- Week 2, Monday

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

Name:

SID: [No spaces and no dashes.]

Login ID :

1. (a) Suppose I tell you that the polynomial p(x) has real coefficients and degree 3. If I told you the value of p(x) at four different values of x, is this enough to uniquely determine p(x)? (b) Does your answer to part (a) depend upon what four values of x I choose? (c) Would your answer change if p(x) had degree 4 instead of degree 3?

2. Write a Java implementation of binary search, by filling in the following template. Make sure that your code is correct on all valid inputs and that it runs in O(lg n) time. 
/* Requires the array A to be sorted.  Checks to see if the
 * value v appears in the array A.  If it does, returns an
 * index where v appears (i.e., a value i such that A[i]==v);
 * otherwise, returns -1 if v does not appear in A. */
public static int bsearch(int[] A, int v) {
    int l=0, r=A.length;
    while (l < r) {
        int midpoint = l + (r-l)/2;
        ???
    }
    return -1;
}

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 170 home page