This course is an introduction to the mathematical study of algorithms. We will examine analytic techniques including proofs of correctness, asymptotic analysis of time and space complexity, intractability, NP-completeness, and undecidability. We will examine a number of strategies for algorithm design, including brute-force, divide-and-conquer, dynamic programming, problem reduction, and greedy algorithms. We will also examine the role of advanced data structures in devising algorithmic solutions. We will examine algorithmic solutions to problems in graph theory, sorting, searching, combinatorics, and numerical computation.

Another focus of this course is the continued development of writing and oral communication skills; you will have substantial opportunities to present your work in both contexts. This component of the course is reflected in its W2 designation.

At the end of this course, you will be expected to be able to:

• Prove an asymptotic time and space bound for an algorithm
• Prove whether a problem is NP-Complete
• Explain the relationships between tractability, intractability, NP-Completeness, exponential time, and polynomial time
• Develop and analyze algorithms from the following categories:
  • Brute-force
  • Greedy
  • Divide-and-conquer
  • Dynamic programming
  • Problem reduction/transformation
• Prove that an algorithm is correct
• Model a problem using a graph, and then use a graph algorithm to solve the problem

Recommended: Dasgupta, Papadimitriou, Vazirani, Algorithms, McGraw-Hill, 2008. The published version is nice and relatively inexpensive, but you can alternatively rely on the PDFs from their final draft (official site).

www.cburch.com/cs/280/

There are a total of 1,000 points over the semester. Letter grades will be assigned with cutoffs at 900 for an A, 800 for B, 700 for C, and 600 for D. The point assignments and anticipated schedule are below.

I reserve the right to make adjustments in the entire grading scheme or in particular cases.

While I do not have a specific goal about the assigned grades, the grades I assign tend to average around 3.0. Note that I do not normally curve grades at the end of the course; instead, I monitor your progress and perform any curves as I grade tests. When I curve test scores, I add a fixed amount to all scores; as a result, some test scores may end up being above 100%. I anticipate, but will not insist, that the median test score will be around 75%. Normally, scores in the non-test categories will be higher; the average class grade will likely be a B even though the average test grade is a C.

Several points are designated for class participation. I will assign half of these points near the semester's middle, and the other half near the semester's end.

I will monitor your class attendance. If your attendance is excellent (missing one or fewer classes each half-semester), you will receive at least 60% of these attendance/participation points. If you feel your absence should be excused, please warn me about the absence a day in advance. Whether I excuse your absence is my call.

The remaining 40% of these points are for participation, including both questions during class and responses to questions during class. I may give more than full credit in unusual circumstances. Take this as an invitation: I value your active participation in class, and I expect you to show evidence of being fully tuned in during class sessions.

The course includes three assignments. You may work with one other student on each assignment; in this case, you should jointly submit a single solution.

You may also ask occassional questions of classmates when you need help. Under no circumstances should I receive two copies of identical or near-identical solutions.

For each 24-hour period after the time due, I will deduct up to 10% of the points possible.

For each of the two projects, you will be assigned a partner with whom to complete the work; and you and your partner will be assigned a topic. You will research the topic, write an exposition paper, and present results to the class. Partner and topic assignments is semi-random; however, I will tend to assign well-performing students to work with other well-performing students and assign them more interesting (and more challenging) topics. (If the number of students is odd, you may be assigned to work alone, and your topic will consequently be less challenging.)

Information imparted during class presentations is legitimate source material for later tests.

There are two take-home exams as well as a take-home portion of the final. You will be given a week to complete each. Your instructor is the only person you are allowed to consult, and your class notes and textbook are the only allowed written or electronic resource.

Quality of writing will be a significant element of how you are evaluated on these. On the take-home exams (but not the take-home final), you will be assigned 80% of the points on your first submission. The final 20% of the grade will be based on your implementation of any corrections I request. Note that if you submit well-written solutions the first time, you will not need to rewrite.

The late policy for the exams (but not the final) is a deduction of 10% of the points possible for each 24-hour period the exam is submitted late. The take-home final will not be accepted more than one day late, and the deducion will be 25% of the points possible.

The three in-class quizzes will each take the full 50-minute class period; the in-class portion of the final will be two hours.

If you miss a test, you must receive advance permission from me to receive more than a 0. (Dire medical emergencies usually constitute an exception.) If you are excused from the test, I will either double your lowest quiz or exam score or administer a make-up, at my discretion. Let me know well in advance — 24 hours for exams and quizzes, and two weeks for the final. I would like to remind you that, when e-mail is impossible, telephones exist also. Do not skip a test without my prior approval!

Note that I may require you to document your reason for absence. Travel arrangements and work schedules are not adequate reasons to miss a test.

You must properly attribute any work or ideas you use in assignments for this course which are quoted or derived from others. Plagiarism includes not only copying the ideas and the written and spoken words of others, but also copying or otherwise appropriating their computer files as well. Interfering with the work of others is also a serious academic offense. I will abide by the catalog's Academic Honesty policy in referring cases to the college's Committee on Academic Integrity.

Discussing or viewing others' solutions to assignments is officially out of bounds, as is discussing or showing your own solution to others. In practice, I realize, you may help other students; this presents a problem only when the solution you submit is substantially similar to another student's. A strong correlation between your solution and a classmate's solution constitutes evidence of cheating.

Feel free to stop by my office any time you want to talk about something related to the class. I do have office hours listed on the Web page, but they are not intended to limit you. The office hours represent when I will try to be available in my office, but I'm equally available at all times that my office door is open. I'm also happy to arrange appointments.

If you're not in the building, feel free to telephone my office. And if I'm not in my office, you can send e-mail. But please try to contact me directly before e-mail: E-mail is much less efficient.

Most Hendrix students intuitively know the appropriate bounds for behavior in class. But: Cellphone use is prohibited during class, even if calls are received outside the classroom, and even if it is only text-messaging. Use of laptops is restricted to activities directly related to what is currently being discussed; I reserve the right to prohibit them if I feel this policy is being abused.

Any inappropriate use of electronic devices (or of reading materials) is worse than an absence, since it distracts other students. It will count accordingly in the attendance/participation policy; you could potentially receive a negative score.

On tests, no electronic devices other than a simple watch are permitted.

It is the policy of Hendrix College to accommodate students with disabilities, pursuant to federal and state law. Any student who needs accommodation in relation to a recognized disability should inform the instructor at the beginning of the course. In order to receive accommodations, students with disabilities are required to contact Julie Brown in Academic Support Services at 505-2954.