Instructor |
Dr. Carl Burch
| ||||||||||

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

Web page | |||||||||||

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

Tests |
The two tests and the final are planned according to the following schedule; this is subject to change.
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.
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 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; |