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 2008
Assignments

Revised May 9, 2008

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 29, 2008.
Today I will discuss a dynamic programming problem which seems to take Theta(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.
Thursday January 31, 2008.
Turn in Assignment 1 at the beginning of class today.
Today, I plan to describe dynamic programming algorithms for several problems.
Tuesday February 5, 2008.
Monge arrays arise in many pratical applications of dynamic programming, such as finding optimal binary search trees.
When you two multiply two Monge matrices using tropical matrix multiplication, what do you get?
Arrgh! Within one minute of the end of class, I realized my error. I can now give the correct answer to 4-4 b. Can you?
Tuesday February 12, 2008.
Today I plan to present some algorithms which are "magical," in the sense that, in the not-so-distant past, no reasonable person would have thought it possible to solve those problems in that amount of time; and even today, almost no reasonable programmer is aware of them.

Finding the maximum weight interval in an array of length n (that is, given an array A[1] ... A[n], find indices i, j so as to maximize A[i] + ... + A[j]) in O(n2) time, instead of the obvious O(n3) time.
Paradigm: Don't recompute the same thing.

Finding the maximum weight interval in an array of length n in O(n log n) time. instead of the (now) obvious O(n2) time.
Paradigm: Divide and conquer.

Finding the maximum weight interval in an array of length n in O(n) time.
Paradigm: Be very clever in detecting what you don't need to compute.

Finding an optimal binary search tree in O(n2) time, instead of the obvious O(n3) time.
Paradigm: Using a version of the monotonicity property, be clever in detecting what you don't need to compute.

Finding the row-minima of a totally monotone matrix (that's a slight generalization of Monge matrix) in O(n log n) time, instead of the obvious O(n2) time. (We did that last week for Monge matrices.)
Paradigm: Using the monotonicity property, be clever in detecting what you don't need to compute.

Finding the row-minima of a totally monotone matrix in O(n) time instead of the (now) obvious O(n log n) time.
Paradigm: Using the monotonicity property, be extremely clever in detecting what you don't need to compute.
SMAWK power point presentation, thanks to Mr. Roman.
Thursday February 14, 2008.
Turn in Assignment 2 at the beginning of class today.
Thursday February 21, 2008.
Today I plan to discuss the general problem of finding minimum weight paths in weighted graphs. Hopefully we will have time to discuss several approaches to this problem.
Tuesday March 25, 2008.
Midterm exam, pdf format.
Midterm exam, postscript.
The Monge matrices I showed you in class weren't. My program that generated them was wrong. (Thanks, Mr. Gupta, for letting me know.)
Here are some that should be correct.
Here is a totally monotone matrix which is not Monge. I will probably give an example like this one on the test.
It's time to do "Special Topics." The plan for the rest of the semester (10 lectures, in total) will be to spend a very short time (perhaps even just one lecture, or even less, if warranted) on each of a number of "special topics." Each of those topics is considered "advanced,' in the sense that it would be considered over the head of an average CS 477 student.
We will start with a few of the most elementary "special topics." Here is a partial list:
  1. RSA coding (Section 31.7 of your textbook).
  2. Worst case analysis versus Las Vegas analysis.
  3. String matching (Chapter 32 of your textbook).
  4. Computational networks, such as sorting networks (Chapter 27 of your textbook).
  5. Computational Geometry (Chapter 33 of your textbook).
Tuesday March 25, 2008.
Tuesday April 22, 2008. Figure showing duality.
Thursday April 24, 2008. Here are some more "special topics":
  1. Various challenge problems from CS 677.
  2. The Ackermann function.
  3. Range query data structures.
  4. A random mix of sophisticated dynamic programming problems.
    1. 2 traveling salesmen in an acyclic directed graph.
    2. Traveler's problem with arbitrary concave cost function. (This is very hard.)
    3. Traveler's problem with arbitrary convex cost function. (This is so hard that it makes the concave version look trivial.)
    4. Limited memory layered graph minpath problem.
  5. Branch and bound.
  6. The so-called "cow" problem. (A more sophisticated version is the Canadian traveler's problem.)
Tuesday April 29, 2008.
Today I will show you how to work that layered graph problem we talked about.
I will then discuss range queries.. Here is the range query question to think of: What is the minimum size data structure needed so that every 1-dimensional range query can be answered in O(1) time? Hint: the question has no answer, as given.
New in the Afternoon. It is now after class. Let me restate the problem posed in class.
We gave a range-query structure of size O(n log n) such that each query uses at most two intervals. What is the minimum size of the structure so that each query takes at most 3 intervals? (It's asymptotically less than O(n log n)) 4 intervals? (It's asymptotically less than for 3.) 5 intervals? 6 intervals? (Maybe it's not asymptotically less than for 5, although that seems unbelievable.) Hint: the reason you don't get an answer when you say "O(1) intervals" is that the asymptotic size of the data structure depends on the exact maximum number of intervals you're allowed to use. As the number of allowed intervals rises, the minimum possible size of the data structure does not converge to a single asymptotic class.
Thursday, May 15, 2008.
Final Examination. The final examination is scheduled for 10:10 in room TBE B170 (our regular classroom). The examination will be comprehensive.

Back to Course Page