MCS-375: Algorithms (Fall 2005)

Overview

MCS-375 will help you design and analyze algorithms and data structures with an eye to efficiency. You will learn to ask and answer questions such as the following: Which of these ways of solving this problem is faster on the average? Which is faster in the worst case? Could there be a yet faster method? How might a good algorithm for a new problem be found? We will learn these skills almost exclusively by working concrete example problems, introducing the tools as we discover uses for them. Although this course is of great practical utility, we will focus on honing our abilities of mathematical analysis and design of data structures and algorithms outside of the context of a specific computer platform or programming language.

The prerequisites for the course are MCS-178 and MCS-256. You should have already seen much of the material from Chapters 2 and 3 in Kleinberg/Tardos. Be sure to review these chapters in the text during the first week and let me know if you are uncomfortable with the material covered.

Reaching me

All office, phone and schedule information will be maintained on my web page. I'll try to keep it updated with any temporary changes to my schedule as well. In short, if my office door is open you are welcome; if I'm busy, we'll set up an appointment. Email and phone calls work, too.

All course handouts will be available through my World Wide Web page, and some supplementary materials such as code to use as a starting point in assignments may be available there as well. The URL for this course is http://www.gac.edu/~wolfe/375/.

Text and references

Our text for the course, Kleinberg and Tardos, Algorithm Design is unique in its detailed motivation for each algorithm. We will get to know this book through the course, but for students who want to seek out another reference, I'll mention a few.

Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (Second Edition), is a great reference and has a thorough introduction to the most important topics in the area. CLRS is excellent for explaining algorithms, but has a few long-winded proofs. A less encyclopedic text is Manber, Introduction to Algorithms: A Creative Approach. Manber has clear proofs, with clear motivation for the algorithms presented. The book's main drawback is its hang-up on mathematical induction as the only intuition for developing algorithms. Baase, Computer Algorithms, is another good reference; you'll want the 2nd edition. The library has copies of most of these, and I have copies which I'm happy to lend out as well.

Honor

Students are encouraged to discuss the course, including issues raised by the assignments. However, the solutions to homework assignments should be individual original work unless otherwise specified. If an assignment makes you realize you don't understand the material, ask a fellow student a question designed to improve your understanding, not one designed to get the assignment done. To do otherwise is to cheat yourself out of understanding, as well as to be intolerably dishonorable.

Any cheating may lead to failure in the course and notification of the Dean. This includes copying anyone else's work, deliberately facilitating copying and failing to give credit for solutions not discovered on your own. Failure to cite a source (written or verbal) on any component of the course is considered cheating. Each citation should be specific: Do not merely say, ``I worked with so-and-so on this homework set.'' Each problem should have specific information spelling out the nature of the collaboration, such as, ``On problem #3, so-and-so helped me to find an algebra mistake.''

The same standards regarding plagiarism apply to team projects as to the work of individuals, except that the author is now the entire team rather than an individual. Anything taken from a source outside the team should be be properly cited.

One additional issue that arises from the team authorship of project reports is that all team members must stand behind all reports bearing their names. All team members have quality assurance responsibility for the entire project. If there is irreconcilable disagreement within the team it is necessary to indicate as much in the reports; this can be in the form of a ``minority opinion'' or ``dissenting opinion'' section where appropriate.

Assignments and Grading

There will be about ten homework sets (50%), three exams (30%), and one final (20%). If you get 80% or more of the points, you will earn an A, 75% for an A-, 70% for a B+ and down by 5 percentage points each to the lowest passing grade of 35% for a D. There is no curve. However, I reserve the right to subjectively adjust your final grade. Please see me if you have any question how you stand.

We will use a system of mastery homework problems in this course. Each homework set will be assigned with an initial due dates. On the due date, you should submit a thoughtful attempt at each problem on a separate page. If you know you haven't solved a problem yet, clearly write not yet solved at the top, followed by a short description of what you've tried so far. You can miss the initial due date 72 hours once and by 24 hours once; any more late will be heavily penalized. (This very liberal policy is intended to accommodate illness or conflict. Please do not ask for additional exceptions unless your situation is unusual.)

I will return the homework problems to you as quickly as I can, normally with only an indication of whether it is acceptable or needs more work. (Sometimes I may give a brief indication of what area it needs more work in.) If a problem needs more work, and you aren't sure what sort of work it still needs, you should treat that as an invitation to come talk with me about it. Once you've done the additional work, you may turn the problem in again. In fact, you may turn in each problem in as many times as you like before the start of the next exam review class until it is marked as acceptable. (We will typically discuss solutions to homeworks in detail when reviewing on the last class before each exam.) Your grade for the homework portion of the course will be based on the fraction of homework problems that you eventually did acceptably.

I encourage you to work with other students on the homework provided that you do so in such a way that every one in your group learns the material. The most effective way to do this is to first discuss each problem as a group and then have each person work on the problem individually. When you're done (or stuck) compare your work and discuss it. Remember that doing the homework is how you learn the material; and that you are not allowed to work cooperatively on tests.

If you do work with other students on the homework, I would like you to follow these guidelines:

Each person should write up the answers independently.
Each person should be able to work each one of the problems independently.
Each person gives credit to the others who helped. (See Honor for the nature of the citation.)

Additionally, you may also write up a homeowork problem consisting of a proof cooperatively with one other student provided the following:

Each of the two students must complete at least one draft of the problem submission, and
You cannot work with any other one student on more than one problem writeup.

Many problems ask you to find an efficient algorithm for a specified task. A solution to such a problem includes three items:

A clear description of the algorithm. Usually your description should be in paragraph form, but pseudo-code might be included if it helps to clarify your description. In any case, in my experience, pseudo-code alone is rarely clear and therefore seldom acceptable.
A proof of correctness of the algorithm. A clear proof that the algorithm, in fact, solves the problem. This can be omitted if obvious.
An assessment of the running time of the algorithm. Assess the running time of the algorithm using big-O notation in terms of the relevant parameters. For example, for a graph problem, the relevant parameters are typically |V| and |E|, (the number of vertices and edges of the graph, respectively). You should include an explanation of your assessment of the running time if it's not obvious.

Grade disputes should be made before the final exam. I will fix obvious grading errors promptly (and will thank you for pointing them out). For students especially fond of debate, I reserve the right to regrade a whole homework or exam.

Schedule

I like to run this course on a week-to-week basis, covering topics according to my own interests and students' interests. In general, we'll be covering the textbook in order, but will gererally skip sections in each chapter.