CIS 775, Analysis of Algorithms, Fall 2007

Professor: Rod Howell

TA: Joseph Lancaster

Required Textbook:



Specifically, students are expected to have the following background:


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


The early part of the course will be based on Chapters 1-5, and 8 of Howell. 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 Chapters 10-17 in Howell.


Homework problems will be assigned throughout the semester. We will spend significant class time discussing some of the problems before they are due. It is therefore important that you attempt to solve problems before the date on which they will be discussed, so that you will be able to participate in the discussion.

Assignments may be submitted to either

Assignments submitted to any other person/location or after the due date will not be accepted.

All exams will be closed-book. The final exam will be comprehensive.

Grades will be assigned according to the following grading scale:

Academic Honesty:

Kansas State University has an Honor & Integrity 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 & Integrity 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 & Integrity System is the 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."

In this class, you may discuss homework problems with others; however, you must write up your own solutions yourself, without using either complete or partial solutions from your classmates, the internet, or other sources. You must do the exams with no assistance from others. If you are in doubt about what is permissible, please ask me.

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.

For more information, visit the Honor & Integrity System home web page at:

K-State Online:

All course materials will be distributed via K-State Online. Grade information may be accessed there, and announcements will be posted there from time to time. Important class messages will be emailed to your KSU email accounts and posted as announcements. You must be enrolled in the course to access K-State Online.


Any student with a disability that needs a classroom accommodation, access to technology or other assistance in this course should contact Disability Support Services (202 Holton Hall) and/or their instructor.

Copyright © 2007, Rod Howell. This syllabus, all lectures for this course, and all lecture materials are copyrighted materials. 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 Rod Howell.

Valid HTML 4.01!
Valid CSS!
Internet Content Rating Association
SafeSurf Rated