CS 170 Reading Quiz -- Week 12, 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.]

1. We say that an algorithm runs in polynomial time if there exists some constant c>0 so that the algorithm's running time is at most O(n^c), where n denotes the length of the input to the algorithm.

Does mergesort run in polynomial time? Yes or no. In a sentence or less, explain why or why not.

2. Suppose that we have an algorithm A, which periodically invokes the subroutine B. Suppose that A makes only polynomially many invocations of subroutine B, and does at most a polynomial amount of other work. Suppose that the running time of a single invocation of subroutine B is polynomial.

Are we guaranteed that the total running time of A (including all of the time spent on its calls to subroutine B) is polynomial? Yes or no. Explain why or why not.

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