Instructor Dr. Carl Burch
 E-mail: Telephone: 450–1377 (office); 499–9892 (home) Office: MCRey 310 Office hours: T 8:30–9:30, W 9:30–10:30, R 2:00–3:00, F 9:30–10:30 drop-ins, appointments always welcome
Objectives

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
Textbook

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.

Web page

www.cburch.com/cs/280/

Evaluation

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%
Tests

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.

Assignments

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.

Projects

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.

Cheating

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.

Office hours

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.

Electronics

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.

Disabilities

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.