CS624: Analysis of Algorithms

This course does not involve any programming per se, although without a doubt your experiences in building serious programs will help you understand many of the issues we deal with.

In fact, the course could well be regarded as a mathematics course. I will be proving things in class, and you will be expected to write formal proofs in your assignments and on exams. If this is something you are not ready to come to grips with, you should wait until you are ready to take this class.

There is a style to writing proofs. In fact, there are several styles. Your goal should be to write proofs that are easy to read and that illuminate the reason why something is true. This is not easy to do. Good writing of any kind is difficult, and we will work hard at it all term.

Probably the single most important proof technique in this area is mathematical induction. I will assume not only that you are familiar with this, but are comfortable using it. I will not teach it, but I will expect to see inductive proofs written out clearly and well.

I also expect you to be familiar with standard mathematical notations such as summations (and of course, integrals). Some of this is reviewed in Appendix A of the text. I will not review this in class. I expect you to know it, and we will be using it a lot.

One thing is very important to bear in mind: like any other kind of writing, a proof must be understandable. If I can't understand what you are writing, then it can't be correct. And I'm not going to try to guess what you had in mind. If you are uncertain how to express something, please just talk to me or send me email, and I'll try to help. But don't even bother writing something that can't be understood.

Think of this like you would when writing a computer program. If the compiler or interpreter can't understand it, it's wrong. And you have to be really careful with your use of language and terms. For instance, one thing beginning programmers often get mixed up about is the correct use of "or" and "and". The meaning in computer languages is not the same as in English (or any other natural language, so far as I know). The same is true in proofs. We use language in very precise and fixed ways in proofs, and we do this so that what we write can be understood in its exact meaning by anyone at any time, anywhere in the world.

Just for a simple example: the sentence "All horses are not white." does not mean the same as "Not all horses are white." At least, not when writing proofs. In ordinary English, these two sentences are generally regarded as equivalent. But for our purposes they are not. You have to be careful about this.

Here's another example: The symbol "==>" means "implies". It does not mean "then". So you can write

   if x = 3 then x + 5 = 8

   x = 3 ==> x + 5 = 8

   if x = 3 ==> x + 5 = 8   !!! WRONG !!!

On-line resources:

Two web sites that you might profitably look at are:

• The course as it was taught at MIT in 2005 by Charles Leiserson (one of the authors of our main text) and Erik Demaine: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm

• The course as it has been taught at Stony Brook by Steven Skiena (the author of our other text): http://www.algorist.com

On both these web sites you can find lecture notes and videos of course lectures.

Accommodations:  Section 504 of the Americans with Disabilities Act of 1990 offers guidelines for curriculum modifications and adaptations for students with documented disabilities. If applicable, students may obtain adaptation recommendations from the Ross Center for Disability Services, Campus Center, UL Room 211, (617-287-7430). The student must present these recommendations and discuss them with each professor within a reasonable period, preferably by the end of Drop/Add period.

Student Conduct:  Students are required to adhere to the University Policy on Academic Standards and Cheating, to the University Statement on Plagiarism and the Documentation of Written Work, and to the Code of Student Conduct as delineated in the catalog of Undergraduate Programs. The Code is available online at: http://www.umb.edu/life_on_campus/policies/code/

Academic Honesty:  Please read this note about plagiarism and cheating: honesty.pdf