CS 512 - Algorithm Design

Fall 1999

It would be very difficult these days to take a job and approach programming in that sort of algorithm and design sense, [but] it's a solace to think that there are places where people think deeply about algorithms in a general and abstract way and have notions of elegance and beauty.

- Ellen Ullman, The Art of Don E. Knuth
Salon, 16 September 1999

Table of Contents

Course Description

This is a graduate-level course in algorithm design and and analysis. The course catalog entry has general information about CS 512.

You should be a proficient programmer and have a working knowledge of basic algorithms and data structures. The prerequisites for this class are Computer Science 509, Advanced Programming II.

The course is divided into seven two-week sections. See the syllabus for details.

The class meets in Edison 113 on Tuesdays and Thursdays, 6:00 p.m. to 7:50 p.m. There will be no class on Thursday, 25 November.


The course objectives are to develop skills in algorithm design and analysis. At the end of this course, you should:


R. Clayton, Howard B-13, rclayton@monmouth.edu, 732 263 5522. Office hours are Tuesday 5 p.m. to 6 p.m. I'm also usually happy to talk to you any time you can catch me; setting up an appointment is recommended, finger rclayton@monmouth.edu for my schedule.


There will be seven homework sets and seven tests, one homework set and test for each of the seven sections; see the syllabus for the schedule. Tests will be given in class, and are closed book with no notes; calculators and computers will not be necessary. The tests are cumulative, covering everything taught up to and including the class before the test; however, it's a good bet that each test will concentrate on the material taught in the section preceding the test. Tests should take no more than an hour to complete, and will be given in the first half of the class. Test answers will be made available off the syllabus.

Each homework set will be made available on the syllabus at the start of the associated section. Homework is due two weeks later on the day of the test. Homework answers will be made available on the syllabus.

The final grade is a straight, unweighted average of test scores and homework grades; that is, there are fourteen grades total - seven from tests and seven from homework - and each grade constitutes one-fourteenth of your final grade.

I use the usual grade ranges: 90 or above rates an A; from 80 (inclusive) to 90 (exclusive) rates a B; and so on. No grades are adjusted to a curve.

The final grades.



The textbook is Introduction to Algorithms: A Creative Approach by Udi Manber, Addison Wesley, 1989. Also check out the annotated bibliography of books on algorithm analysis and design.


You should feel free to send me e-mail. Unless I warn you beforehand, I'll usually respond within a couple of hours during the usual work days; if I don't respond within a day, resend the message.

Home page

If you're reading this on paper, you can find the class home page at http://www.monmouth.edu/rclayton/f99-512/index.html. I'll make the class notes, assignments, and tests available off the syllabus; you should get in the habit of checking the home page and syllabus regularly.



People who need assistance or accommodations above and beyond what is usually provided in class should contact the University's ADA/504 coordinator to set about getting those needs met. See me or the Disability Services page for more details.


I have no attendance policy; you may attend class or not as you see fit. However, I hold you responsible for knowing everything that goes on in class; "I wasn't in class for that." is not an acceptable excuse for a wrong answer, or for giving no answer at all.

Monmouth University does have an attendance policy, which you can find in the Academic Information chapter of the Student Handbook. To the extent that I need to keep the record straight, I will take attendance. Attendance lists, however, are entirely for the University's benefit; I will make no use of them in grading.


Cheating's not nice; don't do it. Anyone caught cheating fails the course. The chapters on Academic Information and the Student Code of Conduct in the Student Handbook describe academic honesty and how it can be violated.

Late Assignments

Homework assignments must be turned in by the end of class on the day that it's due; homework turned in after the end of class on the day that it's due is late. Late homework is penalized five points a day for each day it's late. I use a 24-hour clock running from midnight to midnight to measure days; note this means that homework handed in the day after the test is penalized ten points: five for the day of the test and five for the next day.

Missing Tests

Seven test is a lot of tests, and there may occasionally be a conflict between taking a test and doing something else, particularly among those working full time. If you're going to be out of town, or on jury duty, or whatever, on a test day, let me know beforehand and we'll schedule a makeup test. The make-up test must be scheduled within the two weeks following the missed test; if the missed test is not made up by the time of the next test, you get a zero for the missed test. I will give only one make-up test; if more than one person misses the same test, those people will have to coordinate among themselves to pick a mutually agreeable date within the following two weeks.


A serendipitous list of links to algorithm and data-structure Web pages.

Other courses in algorithms and data structures

The man who started it all.

This page last modified on 5 January 2000.