CIS 775, Analysis of Algorithms, Fall 2004
- Email: harmon at cis.ksu.edu
- Office: 16A Nichols, Cubicle B
- Office Hours: 10:00-11:00 Tu, 11:00-12:00 W
Required Textbook:
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:
- To develop skills in the design of efficient algorithms
- To develop skills in the mathematical analysis of algorithms
- To develop mathematical creativity
- To develop mathematical rigor in solving theoretical problems
- To develop skills in the written communication of rigorous
problem solutions
Topics:
The early part of the course will be based on Chapters 1-5, Section
6.4, and Chapter 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 the following Chapters 10-17 in
Howell.
Grading:
- Homework: 40%
- Final Paper, Due Dec. 17, 3:50 pm: 50%
- Participation: 10%
Homework will be assigned throughout the semeseter. We will spend
significant class time discussing some of the problems before they are
due. It is therefore important that you attempt to solve the problems
before the date on which they will be discussed, so that you will be
able to participate in the discussion. The participation grade will
be based on your participation in these discussions, as well as
any feedback you might give me on the required textbook.
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.
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 homework, projects, and 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.
Any attempt to represent as your work any
work done by any other person, (student or non-student) will be
considered to be cheating. Penalties for cheating range from a 0 on
the assignment to dismissal from the university. For more
information, see my Guidelines on the
Use of External Sources.
K-State Online
All assignments and other course materials will be distributed via K-State
Online. Grade information may be accessed there, and a
Message of the Day may be available at times. Important class
messages will be emailed to your KSU email accounts and posted as
the Message of the Day. You must be enrolled in the course to
access K-State Online.
Other
Copyright © 2004, 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.