Algorithms (F2008)

The material for this lecture is drawn partially from the textbook: however, I’ll be following Jeff Erickson’s notes more closely.

HW3 (LaTeX) is due Oct 4Oct 8, 2008.

We introduced the idea of a flow network, and the concept of a flow from a source to a sink. We then asked the question: “How can we maximize the flow from source to sink”, and developed the Ford-Fulkerson augmenting-path-based algorithm for this problem. A deep relationship to cuts in a graph proved the optimality of this method.

The material is drawn from Sections 7.1 and 7.2 of the textbook.

Mean: 81.53
Median: 89.5
STDDEV: 19.24
Min: 20
Max: 100

Many of you have asked me what to do when we get complex roots to the annihilator equations resulting from solving a recurrence. My answers to date have been very unsatisfying: basically I said to ignore them. This is in fact wrong (!). Here’s an explanation why, with a solution for what you need to do.

Suppose we’re solving some recurrence and get a collection of roots that includes some complex numbers. In particular, let’s say we’re solving an (ahem) 3rd order recurrence, and we get three roots, a, b, and c. The first thing to note is that complex roots occur in conjugate pairs (I’ll leave you to ponder why that is). So if a is the real root of this equation, and b and c are the complex roots, we can write .

By the standard argument, we know that the recurrence solution is of the form

where , and are constants.

Now since T(n) only takes real values, the complex numbers need to “cancel out” the imaginary parts, which can only happen if (why?). In this case, we can simplify the second and third terms as

Finally, this gives us
, which we can now solve for s_1 and s in the usual way.

What does this mean overall ? It means that if you get complex roots, then find the absolute value (the absolute value of a complex number is ), and then continue as before.

All you needed to know, right here.

Hi all,
Harsh found some useful suggestions on one of the online forums: these might help. In short:

• Don’t invoke the sqrt() function till the very end (this is a hack that I use all the time in my code when doing geometric stuff). Since the sqrt() function is monotonic, the closest pair you obtain is the same whether or not you use distance or distance^2, and the sqrt() function is very expensive. You will need it at the end to report answers
• Don’t assume that inputs are integers
• There are trick inputs with a single point. Be careful not to return garbage in that case (one commenter recommended returning INFINITY)

One trick that probably doesn’t matter for getting the solution accepted, but does matter for getting the best running time: figure out when you want to stop the recursion and just use brute force. It’s comon to find that running the d&c all the way to n=1 is not the most optimized strategy.

In this lecture, we will cover two dynamic programming-based methods for computing shortest paths in graphs. The first one is called the Bellman-Ford algorithm and is used to find all shortest paths from a single source. The second one is the Floyd-Warshall algorithm for finding all shortest paths between all pairs of vertices in a graph.

In both cases, the graphs under consideration have edge weights that could be negative, which complicates matters. However, as long as there are no cycles of negative weight, we can return meaningful answers.

The Bellman-Ford algorithm is in Chapter 6 of the textbook. The Floyd-Warshall algorithm is NOT in the textbook. It can be found in ‘Introduction to algorithms’ by Cormen, Leiserson, Rivest and Stein (Chapter 25). A brief but complete description of the algorithm is presented in Wikipedia.

Hi all,
since not all of you are on the mailing list, and we’re not sure how many of you use the UNID@utah.edu mailing addreses, we’d like to have contact information for each of you that we can associate with

• your uNID
• your CADE account name

so that we can maintain the grading database accurately, and be able to email grades out properly.

So please fill out this form with the requested information. Remember to use an email address that you check at least occasionally, as this is where all contact will be sent. We promise not to spam you

Here’s the PDF (the latex will be arriving shortly) and here’s the LaTeX