Syllabus for CIS 575, Introduction to Algorithm Analysis, Spring 2009

Professor: Rod Howell

Email: rhowell@ksu.edu
Office: Nichols 227D
Office Hours: 1:30-3:00 TT or by appointment
Phone: 532-7735

TA: Aaron Chavez

Email: mchav at ksu.edu
Office: Nichols 219-G
Office Hours: 2:30-3:30 MWF

Required Textbook:

Algorithms: A Top-Down Approach, R. Howell, 8th 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#, 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 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: 15%
Exam 1, Feb. 18: 17%
Exam 2, Mar. 11: 17%
Exam 3, Apr. 15: 17%
Final Exam, May 13, 11:50 am: 34%

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, May 13. Please send this feedback to rhowell@ksu.edu.

Homework will be assigned throughout the semester. Homework assignments may be submitted (in hard copy only) 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. Except under extreme circumstances (as judged by me), no make-up exams will be given.

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:

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

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 © 2009, 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.