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.

At the end of this course, you should 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

Required: Dasgupta, Papadimitriou, Vazirani, Algorithms, McGraw-Hill, 2006. Though I do not anticipate assigning specific readings from this book, it is a rare textbook that is genuinely worth your while to read, and I will be following it fairly closely.

www.cburch.com/cs/280/

Grades will be assigned according to the following rough distribution, which is subject to change. Letter grades will be assigned with anticipated cutoffs at 90% for an A, 80% for B, 70% for C, and 60% for D.

Programming projects (3, 7% each)	21%
Assignments (variable credit)	35%
Tests (two, 12% each)	24%
Final	20%
TOTAL	100%

The two tests and the final are planned according to the following schedule; this is subject to change.

Wed 24 Sep	Test 1
Wed 5 Nov	Test 2
Mon 15 Dec	Final, 2:00pm

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.

There will also be a variety of non-programming assignments. These may include attendance/participation grades, take-home paper-based assignments, in-class presentations, or informal oral quizzes akin to those employed by prominent employers.

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

You must properly attribute any work or ideas you use in assignments and projects 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 and projects 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 have listed “office hours,” 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 asking questions via 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.

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. Students should contact Julie Brown in Academic Support Services (505.2954; brownj@hendrix.edu) to begin the accommodation process. Any student seeking accommodation in relation to a recognized disability should inform the instructor at the beginning of the course.