CIS 775, Analysis of Algorithms, Fall 2009

Instructor: Torben Amtoft
Email: tamtoft hat ksu dot edu
Office: 219C Nichols
Office Hours (tentatively): 1-2pm, Mon & Wed, and by appointment
Phone: 532-7917

TA: Manikanta Babu Karanam
Email: karanam hat ksu dot edu
Office: N-19 (cubicle Q)
Office hours: Tue-Thu 3-4pm

Required Textbook: Introduction to Algorithms, Thomas H Cormen & Charles E Leiserson & Ronald L Rivest & Clifford Stein, 2nd Ed., McGraw Hill, 2001

Algorithms: A Top-Down Approach, Rodney Howell, 9th draft
Fundamentals of Algorithmics, Gilles Brassard and Paul Bratley, Prentice Hall, 1996

Prerequisites: Students are expected to have the following background:

Expected Outcome: Students should master the following knowledge and skills: In addition, students should become familiar with NP-completeness and related topics.


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, and 60 % to earn a B. 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 be closed-book. The final is comprehensive, but with emphasis on the last part of the course.

Grievances: If you think 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 for a partially correct solution, are not encouraged (it is like arguing balls and strikes).

Academic Honesty: Kansas State University has an Honor System based on personal integrity, which is presumed to be sufficient assurance that, in academic matters, 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, accessible at, 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.

Classroom Conduct: All student activities in the University, including this course, are governed by the Student Judicial Conduct Code as outlined in the Student Government Association By Laws, Article VI, Section 3, number 2. Students that engage in behavior that disrupts the learning environment may be asked to leave the class.

Academic Accommodations for Students with Disabilities: Any student with a disability who needs an accommodation or other assistance in this course should make an appointment to speak with me as soon as possible.

Acknowledgment and Notice of Copyright: Much of the course material, including many of the slides used for the lectures, is adapted from the course 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