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.

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/.

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.

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.

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.)

- 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.