HW1

Due at the beginning of class, Wed September 6th. Each solution should take up at most one page. You should do this problem set entirely on your own.

  1. Show that \log(\sum_{i=1}^n e^{x_i}) is a convex function. Write its gradient and Hessian.
  2. Consider a one-dimensional function that is twice-differentiable everywhere. Given access to the function value, gradient and second derivative, is it possible to choose a step size \eta > 0 so that the function value f(x-\eta \frac{df}{dx}) is strictly less than f(x) ? If not, how can you use obtain a point  x with either smaller function value or |\frac{df}{dx}|\le \epsilon?
  3. A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S . For instance, if S is (5, 15, −30, 10, −5, 40, 10) then (15, −30, 10) is a contiguous subsequence, but (5, 15, 40) is not. Give a linear time algorithm for the following task:
    Input: A list of numbers, (a_1, a_2, . . . , a_n) .
    Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero).
    For the preceding example, the answer would be (10, −5, 40, 10), with a sum of 55.
  4. Suppose a CS curriculum consists of n courses, all of them mandatory.  Additionally, some of these courses require one or more prerequisite courses to have been taken in a previous semester.  All such classes have a higher course number than their prerequisites (so there can never be a loop of classes that require each other).   Assuming that a student can take any number of courses in a given semester, give an algorithm that takes the courses and prerequisites as input and computes the minimum number of semesters necessary to complete the curriculum. The running time of the algorithm should be linear in the number of courses and prerequisites.
  5. You are given an infinite array a in which the first n cells contain positive integers in sorted order and the rest of the cells are not defined. By not defined, we mean that if an algorithm probes a position i > n then the program returns an error message. You are not given the value of n . Describe an O(\log n) comparison algorithm that takes a positive integer x as input and finds a position in the array containing x , if such a position exists, and returns NO otherwise.
  6. Let a = (a_1, . . . , a_n) be an array of n distinct unsorted numbers. Say that a pair 1 \leq i < j \leq n is an inversion on a if and only if a_i > a_j .  Give an O(n \log n) comparison algorithms that determines the number of inversions of a given array of n distinct unsorted integers.
  7. A vertex coloring of a graph is an assignment of natural number labels called colors to each vertex.  A valid vertex coloring of a graph is a vertex coloring such that no pair of adjacent vertices share the same color.  Consider the following algorithm for greedily coloring the vertices of a graph: for each vertex in the graph (taken in a random order), set that vertex’s color to be the lowest natural number that is not shared by any adjacent vertex.  Give a brief argument explaining why this algorithm results in a valid coloring. What is the maximum number of colors the algorithm might use?
Advertisement