Syllabus for CIS 575, Introduction to Algorithm Analysis, Fall 2005

Professor: Rod Howell

Email: rhowell@ksu.edu
Office: Nichols 227D
Office Hours: 1:00-2:00 MTWF, 2:00-3:00 Th

TA: Scott Harmon

Email: harmon at ksu.edu
Office: Nichols 16A-2
Office Hours: By appointment
Note: Scott's duties will consist solely of grading homework assignments. This contact information is provided for those who need to ask him questions regarding his grading. If you need help with the class, please see Dr. Howell.

Required Textbook:

Algorithms: A Top-Down Approach, R. Howell, 3rd draft

Prerequisites:

CIS 300 Data and Program Structures
CIS 301 Logical Foundations of Programming
MATH 510 Discrete Mathematics

Specifically, students are expected to have the following background:

Significant experience programming in some high-level programming language, preferably Java, C, or C++
Familiarity with standard data structures: lists, stacks, queues, trees, search trees, hash tables, graphs
Understanding of basic concepts of propositional and predicate logic and its use in program verification
Experience in writing mathematical proofs in natural language
Understanding of algebra (functions, solution of equations, limits, summations), calculus (derivatives and integrals), combinatorics, probability, and recurrence relations

Goals:

Students should master the following knowledge and skills:

Analysis of time- and space-complexity of algorithms
Various sorting algorithms and their tradeoffs
Various advanced data structures and their tradeoffs
Proving theorems about algorithms

In addition, students should become familiar with the following algorithm design techniques:

Divide-and-conquer
Greedy strategies
Dynamic programming

Topics:

Algorithm correctness
Worst-case asymptotic analysis
Correctness and analysis of data structures
Amortized analysis
Data structures for storage and retrieval
Randomized algorithms and expected-case analysis
Priority queues
Disjoint sets structures
Graphs
Divide-and-conquer algorithms
Greedy algorithms
Dynamic programming algorithms

Grading:

Homework: 20%
Exam 1, Sept. 30: 20%
Exam 2, Nov. 9: 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 prior to the final exam.

Homework will be assigned throughout the semester. Homework 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.

The exams will be closed-book, though the use of a sheet of notes may be permitted. The final exam will be comprehensive.

Grades will be assigned according to the following grading scale:

90%-100%: A
80%-89%: B
70%-79%: C
60%-69%: D
0%-59%: F

Academic Honesty:

On all homework, projects, and exams, you will be expected to do your own work. According to the Undergraduate Honor System, on all assignments, examinations, or other course work undertaken by undergraduate 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. Also 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 announcements will be posted 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 © 2005, 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.