This is the home page for CMPSCI 611x, the video-only version of CMPSCI 611 offered through the PEEAS program. Students will view lectures from the Fall 2005 version of CMPSCI 611 and will complete new homework assignments and exams to be designed for this version. CMPSCI 611 is the graduate core course in the theory of algorithms and will deal with analysis techniques, algorithmic paradigms, and NP-completeness in a mathematically sophisticated way.

**Instructor Contact Info:**
David Mix Barrington, 210 CMPSCI
building, 545-4329, office hours Wed 2:30-3:30, Thu 1-3, or by appointment.
I also answer email fairly reliably.

- Course Requirements and Grading (to come, but see Lecture 1)
- Homework Assignment Directory (with HW#3)
- Exam Directory (with midterm and solution)
- Questions and Answers on Homework
- Syllabus
- Lecture Transparencies

The course is primarily intended for graduate students in computer science, and forms one of the core courses for the Master's and Ph.D. programs. Other qualified students, such as undergraduate, non-degree, and engineering graduates students, will be admitted if space allows. The minimal prerequisite is a good undergraduate discrete mathematics course (such as our CMPSCI 250) and the mathematical sophistication expected of a computer science graduate student (e.g., a good background in linear algebra and statistics). Most students will have taken an undergraduate course in algorithms comparable to our CMPSCI 311 -- those who haven't will have to acquire some of this background on the fly.

The required textbook will be lecture notes from previous versions of this course
given by Prof. Micah Adler, who is on
sabbatical leave. These will be available **by hardcopy only**, through
Collective Copies
in downtown Amherst. Most but not
all of the material of the course is covered in published books, which you may or may not
want to buy. The most popular text for a course like this is *Introduction to Algorithms*
by Cormen, Leiserson, Rivest, and Stein. Another good recent text is *Algorithm Design*,
by Kleinberg and Tardos.

The grade for the course will be based on a midterm (to be scheduled individually sometime in March) a final exam (in May), and five or six problem sets. I have a somewhat nuanced acedemic honesty policy for problem sets, which even some graduate students have had difficulty following, so I set it out here:

Solutions to homework problems must be entirely the student's own work **in
presentation**. You may get the idea of how to solve a problem from a variety of
sources, such as the instructor, the TA, fellow students, books, or the web. In your
writeup of the solution, you must **indicate if and where you got such help** and
**present the writeup in your own words**. A good way to ensure your own presentation
is to write up your solution without other written material in front of you. Handing in
work that is substantially identical to another student's work or to your reference is
**plagiarism** and will lead to sanctions. These may include **failure for the course**
and a report to the Graduate School, **even on a first offense**. (Any discplinary
action by me is subject to appeal to the Graduate School according to the established
procedures.)

The most common violation of these procedures in a live class
comes when two or more
students hand in solutions
that are substantially identical to each other.
In video classes I have had problems with improper copying from internet
sources, particularly without attribution.
**Please don't do this.** Identical answers are usually
a matter of excessively close collaboration rather than deliberate copying, but if I can't
distinguish it from the latter I have to treat it as the latter. With reasonable care on
your part to write up your own solutions, this shouldn't happen.

The primary avenue for course announcements will be the list/blog below:

**Announcements (6 April 2006):**

- (6 Apr) The HW#3 assignment is now up.
- (5 Apr) The midterm and its solution are posted. I have graded HW#2 and the midterm and will mail individual grade reports to each of you today. I don't have HW#3 ready yet but will try to get it today as well. The HW#2's ranged from 31 (C+) to 61 (B+) with a scale of A=80 and B=50. The midterms ranged from 69 (B) to 91 (A), as I kept the scale as A=90 and B=60 although the midterm turned out to be rather easy.
- (17 Feb) Sorry for the delay in posting the HW#1 assignment. It is due in two weeks, on Friday 3 March. I don't have a homework index page yet -- I will probably get to this tonight.
- (1 Feb) There seems to be some confusion at Collective Copies about the Adler notes. If you phone tomorrow between 8:00 am and 3:00 pm and ask for Tom Pelissier, he should be able to help you.
- (1 Feb) I've heard from everyone now, thanks. I was wrong about the DVD's -- they are being mailed next Monday according to PEEAS. (Normally PEEAS courses run a week or two behind ordinary on-campus courses because many of them use the lectures from an on-going campus course.) So there is not much for you to do with the course at the moment, except order the Adler notes from Collective Copies (phone 413-256-6425).
- (31 Jan) I've just established the new course web site. Would each of you please send me an email so we can establish communication? You should all have received the DVD's I think -- have a look at the first lecture or two. I'll decide on the content and due date of HW#1 within the next few days.

Last modified 6 April 2006