Dr. Carl Burch
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
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:
- 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
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.
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)
|Assignments (variable credit)
|Tests (two, 12% each)
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
Discussing or viewing others' solutions to assignments and projects
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
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; firstname.lastname@example.org) 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.