Algorithms (F2008)

All the material in today’s lecture is covered in the handout titled, ‘Solving Recurrences’ in the sidebar of this webpage. This includes the Master Theorem and the Annihilator method. I’ll go over some of the material again in the beginning of next class, so that we can clear up lingering questions.

Since Monday is Labor Day, the next class is on Wednesday. On Tuesday, I have office hours from 1-3, and I’ll encourage people to stop by and chat especially since I can tell you all have many questions from today’s lecture.

I will also encourage everyone to at least skim the material to be presented ahead of time. It’s not essential, but it seems to help.

Some of you may be interested in other algorithms-related activites at the School of Computing.

I’m teaching a special topics class on randomization on Tuesdays and Thursdays at 10:45am. This is an advanced class in which students do most of the presentation. We’ll work off two standard textbooks as well as more recent surveys and papers.

In addition, I maintain a mailing list algos@cs.utah.edu for folks interested in algorithms: it mainly has news of conference deadlines, lists of papers, invited talks, and so on. If you’d like to keep abreast of such happenings, then subscribe to the mailing list by going to http://mailman.cs.utah.edu/listinfo/algos.

Homeworks:

• We will have between 6-7 homeworks, of which you may drop one.
• Homeworks must be submitted electronically or on paper by 5pm the day the assignment is due. Paper assignments will be submitted to the TA.

Exams:

• There will be one midterm and one final. Both will be take-home exams.

Grading:

• The rough weighting will be 50% homeworks, 20% midterm, and 30% final.

Late policy:

• All homeworks submitted after the due date will be subject to a 10% penalty per day following the due date (not counting weekends). After a week, no credit will be given. You get one bye, which allows you to submit one assignment upto a week late with no penalty.

Office hours:

• My office hours will be Tuesday 1-3pm, or by appointment.
• Harsh Bhatia’s office hours will be announced shortly.

Lecture 1 was all about pancakes. Well, sort of, anyway. Much of the lecture was drawn by Brian Hayes‘ excellent article entitled ‘Sorting out the genome‘ for the American Scientist. In this article you’ll find references for the results discussed in the lecture. In addition, here’s an applet for flipping signed permutations, and one for the “easier” pancake flipping problem.