Syllabus for MCS-375: Algorithms (Fall 2011)

Overview

This course will help you design and analyze algorithms and data structures. You will learn to ask and answer questions such as the following:

• Given two alternative ways to solve the same problem, which 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 in the context of working example problems, learning general tools along the way. In order to make our work reasonably concrete, we'll occasionally pause to code an algorithm up in Python, but our primary focus will be on design and analysis rather than programming implementation.

Due to the one-semester scope of this course, we won't be able to cover all the material in our textbook, and even that massive book doesn't cover the entire breadth of the field. Our emphasis will be on sequential algorithms for discrete, symbolic problems; we will cover parallel algorithms only lightly and won't discuss continuous, numeric problems at all. Also, we will primarily discuss algorithms that guarantee exact answers, spending only a few days on approximation algorithms for problems that are infeasible to solve exactly.

Office hours

I will be available in my office (OHS 306) 10:30-11:20 on Mondays, Tuesday, Thursdays, and Fridays, as well as by appointment. Or try your luck: just stop by and see whether my door is open. You may send me electronic mail at max@gustavus.edu or call me at extension 7466. I'll try to put any updates to my office hours on my web page, so check there if in doubt.

World Wide Web

Text

Homework assignment policy

The schedule shows a due date for each of the eight homework assignments. In order to receive any credit for a problem, you must submit a reasonable initial attempt at a solution by this due date. I will return graded homework as quickly as I can, but ordinarily with only a numerical grade, no comments. The reason why I don't write comments is because I want you to come talk with me face-to-face. If a problem needs more work, you should treat that as an invitation to come talk with me about it. Once you've done the additional work, you may turn in a revised solution for regrading. Please attach the graded original to your resubmission. All revised submissions are due one week after the original graded versions are returned to you. You are welcome to consult with me as many times as you like throughout the process of producing your initial submission, your revised submission, and even thereafter.

I am adopting my colleague San Skulrattanakulchai's policy on homework collaboration, which he describes as follows: "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."

Tests

There will be two intra-term tests as shown on the schedule below and a final exam as scheduled by the registrar. If you have a conflict with a testing time, please contact me as soon as possible to make an alternative arrangement.

Exams will be closed-book and mostly closed-notes. You may, however, use a single 8 1/2 by 11 sheet of paper with hand-written notes for reference. (Both sides of the sheet are OK.)

Honor

Any substantive contribution to your solution by another person or taken from a publication or online source should be properly acknowledged in writing. Failure to do so is plagiarism and will necessitate disciplinary action.

You are expected to be familiar with the college academic honesty honor code policy and to comply with that policy. If you have any questions about it, please ask.

Grading

You will earn up to 200 grade points for your work on homework and tests, divided as follows. Each of the 8 homeworks will be graded on a scale of 12 points, totaling 96 points. Each of the two tests that happens during the semester, in class, will be graded on a scale of 32 points, for 64 more points. The remaining 40 points will come from the comprehensive final exam. In addition to these 200 points, you can earn extra-credit points as described in separate guidelines. Your course grade will be recorded as follows:

Please point out any arithmetic or clerical error I make in grading, and I will gladly fix it. You may also request reconsideration if I have been especially unjust.

Style guidelines

Accessibility

Gustavus Adolphus College is committed to ensuring the full participation of all students in its programs. If you have a documented disability (or you think you may have a disability of any nature) and, as a result, need reasonable academic accommodation to participate in class, take tests or benefit from the College's services, then you should speak with the Disability Services Coordinator, for a confidential discussion of your needs and appropriate plans. Course requirements cannot be waived, but reasonable accommodations may be provided based on disability documentation and course outcomes. Accommodations cannot be made retroactively; therefore, to maximize your academic success at Gustavus, please contact Disability Services as early as possible. Disability Services (https://gustavus.edu/advising/disability/) is located in the Advising and Counseling Center.

Support for English Language Learners (ELL) and multilingual students is available via the College's ELL Support staff person, Andrew Grace (agrace@gustavus.edu or x7395). He can meet individually with students to consult about academic tasks and to help students seek other means of support. In addition, ELL and multilingual students can seek help from peer tutors in the Writing Center. Please let me know if there is any accommodation in the course that would enable you to more fully show your abilities; for example, I would consider allowing extra time on tests, as well as allowing a dictionary in an otherwise closed-book test.

Schedule