CIS 775, Analysis of Algorithms, Fall 2006

Professor: Rod Howell

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

Required Textbook:

Algorithms: A Top-Down Approach, R. Howell, 4th 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
Concrete Mathematics, R. Graham, D. Knuth, and O. Patashnik, 2nd Ed., Addison Wesley, 1994

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.

The material will be presented both in lecture format and by class discussion. In addition, a number of suggested exercises will be posted. Though these exercises will not be collected for grading, it is unlikely that you will be able to achieve adequate mastery of the material without working on them. Model solutions for all of the suggested exercises will be posted, and some of the exercises will be discussed in class.

Grading:

Exam 1, Sept. 29: 20%
Exam 2, Oct. 25: 20%
Exam 3, Nov. 20: 20%
Final Exam, Dec. 12, 4:10 pm: 40%

In addition, up to 10% extra credit may be awarded for feedback on the required text. In order to be considered for extra credit, feedback must be submitted by noon, Dec. 12.

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

Grades will be assigned according to the following grading scale:

85%-100%: A
70%-85%: B
55%-69%: C
40%-54%: D
0%-39%: F

Academic Honesty:

On all exams, you will be expected to do your own work. According to the Honor System, on all assignments, examinations, or other course work undertaken by students, the following 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." For more information, please visit the Honor System 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.

Other

College of Engineering Policies

Copyright © 2006, 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.