University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

Computer Science 715
Advanced Analysis of Algorithms
Spring 2010
Assignments

Revised April 28, 2010

Background.
It is important to have a good background in algorithms and data structures at the level of CSC 477/677.
There is background material in your textbook. See the syllabus for CSC 477/677.
Tuesday January 12, 2010.
Today I will discuss a dynamic programming problem which seems to take Θ(n2) time, but which can be greatly sped up by using a special property of the problem. We will use amortized analysis to prove the speedup.
Tuesday January 19, 2010.
Turn in Assignment 1 at the beginning of class today.
Thursday January 21, 2010.
Inverse Ackermann without pain.
Handout in postscript format..
Handout in portable document format (pdf)..
Thursday January 28, 2010.
In , he claims the result that I thought was wrong today. On page 88 of the slide show, he claims that you can achieve O(alpha(n)) query cost with a data structure of size O(n).
Note that Seidel's definition of the alpha_k differs slightly. He uses 2 instead of 3 in the definition, which indicates that he's using floor instead of ceiling, but I don't think he makes that clear.
What Seidel calls a "k-op structure" is what I call D_k(n) in the handout. What he calls a "prefix sum" is what I call a "range query." I don't know why he calls it a "prefix" sum, since it is simply the sum for any sequence of consecutive terms, not necessarily a prefix. (Maybe he explains it and I missed it.)
Tuesday February 2, 2010.
There is a connection between the inverse Ackermann function and the problem of finding row minima in triangular inverse Monge matrices, sort of "reverse SMAWK." This work was pioneered by Maria Klawe, the "K" in "SMAWK."
Thursday February 4, 2010.
Today I will finish up the (partial) proof that Knuth's algorithm takes O(n2) time.
We will start the SMAWK algorithm.
In postscript form.
In portable document format (pdf).
Tuesday February 9, 2010.
Turn in Assignment 2 at the beginning of class today.
Thursday February 18, 2010.
I am feeling much better than I did just at noon today. At this rate, I'll be in good shape in time for tomorrow's class.
I am planning to write up a handout for the FFT, but we'll see whether I have the energy tonight. The explanation in the book is far too long, IMHO.
Pseduocode for the FFT
Thursday February 25, 2010.
Turn in Assignment 3 at the beginning of class today.
Tuesday April 5, 2010.
handout in postscript form pdf form
Tuesday April 27, 2010.
FFT handout in postscript form pdf form
I went home to take a nap between classes, so I have not so far spent any additional time thinking about Problem 1(a).
As I promised, I will let you know if I discover that I was wrong, and I hope to resolve the question by early tomorrow morning.
Wednesday April 28, 2010.
Wed Apr 28 02:58:20 PDT 2010
After hours of thinking about it, I have concluded that I was wrong. I will rewrite problem 1 appropriately.
Saturday, May 1, 2010.
Final Examination. The final examination will be held noon in room TBE B170 (our regular classroom). The examination will be comprehensive.
Updated final in postscript format.
Updated final in portable document format (pdf).

Back to Course Page