CIS 775, Analysis of Algorithms, Fall 2008
Basics
- Classes are MWF, 3:30-4:20pm, in N122.
- The Captain's log
gives up-to-date information about
what has been covered so far and what is expected to happen
in the near future.
-
K-State Online is used
to report grades, to upload the slides used during the lectures,
etc.
-
The mailing list
cis775-l@listserv.ksu.edu is
for questions and issues of general interest
(note that you cannot mail attachments).
-
Email: tamtoft hat ksu dot edu
-
Office: 219C Nichols
-
Office Hours: 2-3pm, Tue & Thu, and by appointment
-
Phone: 532-7917
TA: Aaron Chavez
-
Email: mchav hat ksu dot edu
-
Office: 219G Nichols
-
Office hours: 9:30-10:30am, Mon & Fri.
Required Textbook
Algorithms:
A Top-Down Approach, Rodney Howell, 7th draft
References
Introduction to Algorithms,
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2nd Ed., McGraw Hill, 2001
Prerequisites
Students are expected to have the following background:
-
significant experience with programming in some
high-level programming language
-
familiarity with standard data structures such as lists, trees, graphs, etc.
-
understanding of basic concepts of set theory, and of propositional and predicate logic
-
understanding of fundamental mathematics such as
functions, solution of equations, limits, summations,
derivatives and integrals, combinatorics
-
ability to write rigorous proofs
Expected Outcome
Students should master the following knowledge and skills:
-
The design of efficient algorithms
-
Mathematical analysis of algorithms
-
Mathematical rigor in solving theoretical problems
In addition, students should become familiar with NP-completeness
and related topics.
Topics
The early part of the course will be based on
selections from Parts I and II of Howell's textbook;
much of this material may be review, but it is necessary to
cover it in order that the proper foundations are laid. The core of
the course is taken from Parts III, IV, and V of Howell's textbook.
Grading
-
Homework: 25 %
-
Exam 1, October 1: 15 %
-
Exam 2, October 29: 15 %
-
Exam 3, December 3: 15 %
-
Final Exam, December 17: 30 %
In addition, you can earn up to 10 percent of extra credit for
constructive and interesting comments and questions,
as subjectively judged by me.
You should expect that it requires
80 % to earn an A,
60 % to earn a B, 40 % to earn a C, and 20 % to earn a D.
In general, my approach to grading is expressed well by
this
piece by S.A. Miller.
Homeworks
are due almost every week. They can be submitted either to me in class,
or to the homework tray in the CIS office, Nichols 234 (please make
sure to include your name, my name, the course number,
and that they stamp it with not only the date but also
the time of day).
Assignments that are late
will not be graded,
unless in case of documented medical or family emergencies.
Exams
will probably be closed-book. The final is comprehensive,
but with emphasis on the last part of the course.
Grievances
If you think that the instructor or the TA has made an oversight
when grading your test or your homework, you are of course
very welcome to ask for clarification. But complaints about
judgment calls, like how much credit to give for a partially
correct solution, are not encouraged---it is like
arguing balls and strikes. In particular this holds
for homeworks (since each assignment carries so little weight
towards the final grade).
Honor System
Kansas State University has an
Honor System based on personal
integrity, which is presumed to be sufficient assurance in academic
matters that one's work is performed honestly and without unauthorized
assistance. Undergraduate and graduate students, by registration,
acknowledge the jurisdiction of the Honor System. The policies and
procedures of the Honor System apply to all full and part-time
students enrolled in undergraduate and graduate courses on-campus,
off-campus, and via distance learning.
A component vital to the Honor System is the inclusion of the Honor
Pledge which applies to all assignments, examinations, or other course
work undertaken by students. The Honor Pledge is implied, whether or
not it is stated: "On my honor, as a student, I have neither given nor
received unauthorized aid on this academic work. "A grade of XF can
result from a breach of academic honesty. The F indicates failure in
the course; the X indicates the reason is an Honor Pledge violation.
You are very welcome to discuss the course material, as well as
specific questions, with your fellow students. However, all submitted
answers must be your own work: you are not allowed to show your
answers to anyone else, or look at the answers of any other student;
neither are you allowed to consult previous model solutions that
may be around, or solicit the Internet for solutions to
specific homework problems.
If you are in doubt about what is permissible, please ask me.
Academic Accommodations for Students with Disabilities
If you have any condition, such as a physical or learning disability,
which will make it difficult for you to carry out the work
or which will require academic
accommodations, please notify me in the first two weeks of
the course.
Acknowledgment and Notice of Copyright
The course material, including this syllabus
and the slides used for the lectures,
is adapted from the
one
taught by
Rodney Howell.
During this course students are prohibited from selling notes to, or
being paid for taking notes by, any person or commercial firm without
the express written permission of the professor teaching this course.
Torben Amtoft