Exam 1: Asymptotic Analysis and Beyond

This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date.

There are five problems on this examination. You must do your best to answer all of them. The problems are not necessarily of equal difficulty. Problems may include subproblems. If you complete five problems correctly or mostly correctly, you will earn an A. If you complete four problems correctly or mostly correctly, you will earn a B. If you complete three problems correctly or mostly correctly, you will earn a C. If you complete two problems correctly or mostly correctly, you will earn a D. If you complete fewer than two problems correctly or mostly correctly, you will earn an F. If you do not attempt the examination, you will earn a 0. Partially correct solutions may or may not earn you a partial grade, depending on the discretion of the grader.

I rarely give makeup problems because my experience in past semesters is that students spend a lot of effort on such problems but do not significantly improve their grade.

Read the entire examination before you begin.

I expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. In particular, this exam is likely to take you about ten hours, depending on how well you've learned the topics and how fast you work.

In the interest of fairness, I prefer to do blind grading on my examinations. I will assign you a random number. You should write your random number on every page of the exam. You should do your best to avoid including any information that woudl personally identify you within the exam.

In addition to your examination, you will turn in a separate cover sheet that provides your name, random number, and academic honesty statements (see below for details).

After grading the anonymous examinations, I will merge them with the cover sheets before returning them to you.

This examination is open book, open notes, open mind, open computer, and open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than as restricted by that limitation, you should feel free to use all reasonable resources available to you.

As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately. If you use code that you wrote for a previous lab or homework, cite that lab or homework and the other members of your group. If you use code that you found on the course Web site, be sure to cite that code. You need not cite the code provided in the body of the examination.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web. (You certainly should not post them to GitHub unless you create a private repository for your exam.) And, in case it's not clear, you may not ask others (in person, via email, via IM, via IRC, by posting a “please help” message on StackOverflow or elsewhere, or in any other way) to put answers on the Web.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say “This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing the exam.” You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.

You must include both of the following statements on the cover sheet of the examination.

Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky (that's me).

You will only present your exam to me in physical form.

Physical copy: You must write all of your answers using the computer, print them out, number the pages; and put your assigned number on the top of every page. You must turn in a separate cover sheet on which you hand write, sign, and date each of the academic honesty statements (provided you are able to do so). If you fail to number the printed pages, you may suffer a penalty. If you fail to turn in a legible version of the exam, you are also likely to suffer some sort of penalty.

Partial Credit: I may give partial credit for partially correct answers. I am best able to give such partial credit if you include a clear set of work that shows how you derived your answer. You ensure the best possible grade for yourself by clearly indicating what part of your answer is work and what part is your final answer.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the issue you have observed and attempt to reword the question in such a way that it is answerable. You should also feel free to send me electronic mail at any time of day.

I will also reserve time at the start of each class before the exam is due to discuss any general questions you have on the exam.

As you likely realized, the summation problems you did in Skiena exist because we see many nested loops in our algorithms and want to carefully analyze those nested loops. For example, consider the standard implementation of selection sort.

  for i = 0 to n-1
    min = i
    for j = i+1 to n-1
      if (A[j] < A[min]) then min = j
    end for
    swap(A, i, j)

We would model this algorithm as a pair of nested sums, the outer sum running from 0 to n-1, the inner sum running from i+1 to n-1.

Find an interesting algorithm with triply-nested loops, write the corresponding summation, and solve that summation. Then indicate the asymptotic running time of the algorithm.

Consider the recurrence relation: T(1) = 1; T(n) <= 2T(n/3) + T(2n/3) + cn

(a) Draw the recurrence tree for this relation.

(b) Using the master theorem, your recurrence tree, and/or an informal top-down or bottom-up analysis, find lower and upper bounds on T(n).

(c) Optional: Prove that your closed form correctly models the recurrence relation.

I will likely assess your answer to part b on the care with which you do your analysis.

Prove the three following properties of Big-O.

a. We can ignore lower-order terms.

b. We can ignore constant multipliers.

c. The bound of the sum of two functions is the bound of the two functions.

My colleague, Henry Walker, is fond of saying “Red-black trees are just an encoding of 2-3-4 trees in binary trees.”

What's a 2-3-4 tree? It's much like a 2-3 tree, except that we have the rules that:

In the equivalence model between red-black trees and two-three trees, we can think of combinations of nodes in the red-black trees as equivalent to a single node in the 2-3-4 tree. In particular, a black node and all of its red children in a red-black tree correspond to a single node in the 2-3-4 tree.

Show the equivalence between the insertion algorithm for 2-3-4 trees and the insertion algorithm for red-black trees.

We've seen that merge sort provides a nice sorting routine because it is both stable and has guaranteed O(nlogn) running time. However, in the typical implementation, it requires overhead of at least n extra spaces.

Can we do better? Certainly. It turns out that you can write a fairly simple, general version of merge sort by using only an array of size n/2, which you allocate at the beginning of the algorithm.

Using pseudocode, C, Java, or Scheme, implement a version of merge sort that only allocates one extra array, and limits the size of that array to ceiling(n/2).