Algorithms (F2008)

Hi all,
I see that some of you have been having trouble with the I/O routines for question 5. I’m attaching here two routines that I know to work (for C and C++). In the comments to the homework 1 post, some people have also posted other examples that work.

I don’t see an example for Java, so if you have one and don’t mind sharing, email it to me and I’ll add it to this post (or post it in the comments and I’ll lift it to the post). Only post things that you know work.

C/C++ Code using scanf (two flavors):
int main ()
{
int left = 0;
int right = 0;
while (scanf("%d%d", &left, &right) != EOF)
{
cout << left << " " << right << " " << findMaxCycleLength(left, right)<< endl;
}
}

or…

int main(int argc, char **argv)
{
int lo, hi;

while( scanf(”%d%d”, &lo,&hi) != EOF ) {
printf(”%d %d %d\n”, lo, hi, FindMax(lo,hi));
}
}

Code using cin (from Mike Clark):
int one, two;
while(cin>>one>>two) {
// logic goes here
}


Java code (from John Meier):
Input…
Scanner inputScanner = new Scanner(System.in);
while (inputScanner.hasNext()) {
run(inputScanner.nextLong(), inputScanner.nextLong());
}

and output…
//Output the result
System.out.format("%d %d %d\n", i_orig, j_orig, max_cycle_length);


Although the material in this lecture comes from the book, I found that it was more effective to write my own notes. They are linked here: please skim them before class.

I particularly want to make sure that you at least read

• The section on complex numbers
• The section describing the FFT

This is tough material (in my experience) and will take some effort to get through.

The standard ToH problem has 3 pegs, and the resulting recurrence for the number of steps needed to transfer n blocks from peg 1 to peg 3 solves to .

Suppose we had FOUR pegs ? One strategy (which is conjectured to be optimal, but is not known to be so) is the following: Take the first n-k blocks and move them from 1 to 2 using all four pegs. Take the remaining k blocks and move them from 1 to 4 without using 2 (which is a three-peg problem). Take the n-k blocks on 2 and move them to 4, using all four pegs (we can do this because any of these blocks can sit on top of the blocks currently on 4, so it’s as if 4 was empty.

There are two questions that result from this algorithm.

• For some fixed k, can we write down the resulting recurrence and solve it ?
• What is the right value of k to pick to get the overall best solution ?

It’s probably best to solve the first question and obtain the solution as a function of n and k. You can then try to minimize this expression with respect to k. Enjoy

You can post questions in the comments: use a SPOILER alert if you’re going to post a solution though.

Hi all,
just a quick poll while you’re pondering HW1: I’d like to get a sense of the different reasons why people are attending the class. The answers will help me shape the contents of the lectures (and the emphasis) as we proceed. So I’d appreciate it if you’d take a few seconds to vote, or fill in your own choice of answer.

n

Homework 1 is due Wednesday, Sep 10 @ 5pm.

LaTeX source for this assignment is here, and the style file you’ll need (assign.cls) is linked on the sidebar on the right.

Instructions:

• The assignment includes one programming question that uses the ACM online judge: instructions for using the judge are given in the assignment.
• Code may be written in C/C++/Java/Pascal (!). Please use the appropriate extension for your code when submitting it.
• I strongly prefer assignment submission using the CADE handin software. In order to submit the assignment, you run the command
  

  handin cs6150 <file.pdf> <code-file>

  from your directory. In any case, your code MUST be submitted using this mechanism. Do NOT email me your assignment. I will merely ignore it. Note that the handin software logs the most recent submission time for your assignment.

• If you do not have access to CADE, please contact me.
• If for some reason you must submit the written portion of the assignment on paper, slip it under my door BEFORE 5pm.

For any other questions, you may post a comment on this post (PREFERRED), or email me.

In today’s lecture we’ll cover the basics of divide and conquer, looking at

• Mergesort
• Integer multiplication
• Closest pair (among points in the plane)

All of this can be found in the textbook, in chapter 5.

Divide and conquer is intimately connected with recursion. Paradoxically though, the ability to implement a divide and conquer algorithm has more to do with the ability to combine than the ability to recurse. In the three examples, we’ll see that the merge step is the start of the process by which we design a D&C algorithm, and the merge step gets more and more complicated as we go along.

After notes:

• One point I omitted to make: once we construct the grid of side length D/2 in the merge step of the closest pair algorithm, we can make the strong claim that AT MOST one point lies in each of the grid cells. this is because any cell lies either wholly on the left or wholly on the right. If two points occupied a single grid cell, then they’d be closer than D apart (check this!) and that would contradict the claim that D was the closest pair distance on that side. This is important, because if a cell could contain more than one point, then we’d need to recurse once again inside this cell, messing up the analysis.
• Some people raised the question of whether this algorithm works in three dimensions (i.e find a splitting plane, recurse, and then do a merge as before, with cubes instead of squares). In fact, this can be done: the trick is that the running time involves numbers that are exponential in the dimension (4*4*4 = 64 in 3D, and so on), but the n log n part stays the same.