CIS 775, Analysis of Algorithms, Fall 2007

Professor: Rod Howell

Email: rhowell@ksu.edu
Office: 227D Nichols
Office Hours: 1:00-2:00 MWF
Phone 532-7735

TA: Joseph Lancaster

Email: jospeh at ksu.edu
Office: Nichols 19
Office Hours: 2:30-3:30 TT

Required Textbook:

Algorithms: A Top-Down Approach, R. Howell, 5th draft (in preparation)

References:

Fundamentals of Algorithmics, G. Brassard and P. Bratley, Prentice Hall, 1996.
Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2nd Ed., McGraw Hill, 2001

Prerequisite:

CIS 575 Introduction to Algorithm Analysis

Specifically, students are expected to have the following background:

Significant experience programming in some high-level programming language
Familiarity with standard data structures: lists, stacks, queues, trees, search trees, priority queues, hash tables, graphs (see Chapters 4-9 of Howell)
Understanding of asymptotic notation and its use in analyzing algorithms
Understanding of basic concepts of set theory and propositional and predicate logic
Ability to write rigorous proofs, similar to any of the proofs in Chapters 1-4 of Howell
Understanding of algebra (functions, solution of equations, limits, summations), calculus (derivatives and integrals), and combinatorics

Goals:

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

Grading:

Homework: 15%
Exam 1, Sept. 26: 15%
Exam 2, Oct. 19: 15%
Exam 3, Nov. 16: 15%
Final Exam, Dec. 14, 4:10 pm: 30%
Participation: 10%

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

Rod Howell; or
the homework tray in the CIS office, Nichols 234 (be sure to include your name, my name, and the course number).

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:

80%-100%: A
60%-79%: B
40%-59%: C
20%-39%: D
0%-19%: F

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: http://www.ksu.edu/honor.

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.

Disabilities:

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.