Syllabus for CIS 575, Introduction to Algorithm Analysis,
Fall 2005
- Email: rhowell@ksu.edu
- Office: Nichols 227D
- Office Hours: 1:00-2:00 MTWF, 2:00-3:00 Th
- 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
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.