**Classes**: MWF, 2:30pm-3:20pm, in Nichols 122.**Instructor**: Torben Amtoft,`tamtoft hat ksu dot edu`, 219C Nichols, 532-7917.

*Office Hours*: Tuesdays 2-4pm, and by appointment.**Teaching Assistant**is Yang Xue,`xueyang hat ksu dot edu`, N16A; office hours are MW 3:30-5:00pm, and by appointment.**Auxiliary Teaching Assistant**is Karthik Tangirala,`karthikt hat ksu dot edu`, N237; office hours are MWF 9:30-10:30am, and by appointment.**Course Homepage**: http://people.cis.ksu.edu/~tamtoft/CIS575/S13/index.html.**Up-to-date Log File**: http://people.cis.ksu.edu/~tamtoft/CIS575/S13/log.html.**Reading Material**:*Algorithms: A Top-Down Approach*, Rodney Howell, 9th draft (available online)*Suggested*further reading (optional):*Introduction to Algorithms*, Thomas H Cormen & Charles E Leiserson & Ronald L Rivest & Clifford Stein, 3rd Ed., MIT Press, 2009

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

- Significant programming experience in some high-level language, for example Java, C#, C, or C++
- Familiarity with standard data structures such as lists, stacks, trees, graphs, etc.
- Understanding of basic concepts of propositional and predicate logic and their use in program verification
- Experience in writing mathematical proofs in natural language
- Understanding of fundamental mathematics such as basic set theory, functions, solution of equations, limits, summations, derivatives and integrals, combinatorics

** Learning Outcomes**:
Students should attain competency in the following:

- Application of mathematical techniques to analyze time and space usage of algorithms and data structures
- Understanding various advanced data structures and their tradeoffs
- Proving theorems about algorithms
- Recognizing and applying algorithmic design techniques

** Topics** (tentative):

- Algorithm correctness
- Worst-case asymptotic analysis
- Correctness and analysis of data structures
- Amortized analysis
- Priority queues
- Disjoint sets structures
- Graphs
- Divide-and-conquer algorithms
- Greedy algorithms
- Dynamic programming algorithms
- Depth-First Search
- Network Flow and Matching

** Homeworks**
are due almost every week,
with submission details to be given.
Assignments that are late will not be graded,
unless in case of documented medical or family emergencies.

** Exams**
will be closed-book though the use of a limited amount of note
sheets may be permitted.

The final will be comprehensive, but with emphasis on the last part of the course.

** Grading**:

- Homework: 25 %
- Exam 1, February 27: 20 %
- Exam 2, April 10: 20 %
- Final Exam, May 15: 30 %
- Class participation: 5 %

Final letter grades are not based on strict percentage cutoffs but are "curved" by taking into account the difficulty of the exercises and exams. As a rule of thumb, however, you should expect that it requires 80 % to earn an A, 60 % to earn a B, 40 % to earn a C, and 20 % to earn a D. In general, my approach to grading is expressed well by this piece by S.A. Miller.

** Grievances**:
If you think the instructor or the TA has made an oversight
when grading your test or your homework, you are of course
very welcome to ask for clarification. But complaints about
judgment calls, like how much credit to give for a partially
correct solution, are not encouraged (it is like
arguing balls and strikes).

** Statement Regarding Academic Honesty**:
Kansas State University has an Honor System based on personal
integrity, which is presumed to be sufficient assurance that, in
academic matters, one's work is performed honestly and without
unauthorized assistance. Undergraduate and graduate students, by
registration, acknowledge the jurisdiction of the Honor 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. The honor system
website can be reached via the following URL: www.k-state.edu/honor
. A component vital to the Honor System is the inclusion of 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." 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.

You are very welcome to discuss the course material, as well as specific questions, with your fellow students. However, all submitted answers must be your own work: you are not allowed to show your answers to anyone else, or look at the answers of any other student; neither are you allowed to consult previous model solutions that may be around, or solicit the Internet for solutions to specific homework problems. If you are in doubt about what is permissible, please ask me.

** Statement Regarding Students with Disabilities**:
Any student with a disability who needs a classroom accommodation,
access to technology, assistance during an emergency evacuation, or
other assistance in this course should contact Disability Support
Services (dss@k-state.edu) and/or the instructor. DSS serves students
with a wide range of disabilities including, but not limited to,
physical disabilities, sensory impairments, learning disabilities,
attention deficit disorder, depression, and anxiety.

** Statement Defining Expectations for Classroom Conduct**:
All student activities in the University, including this course, are
governed by the Student Judicial Conduct Code as outlined in the
Student Governing Association By Laws, Article VI, Section 3, number
2. Students who engage in behavior that disrupts the learning
environment may be asked to leave the class.

** Statement for Copyright Notification**:
Copyright 2013(Torben Amtoft) as to all lecture slides. 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 the professor teaching this course.

** Acknowledgment**:
Much of the course material, including this syllabus,
is adapted from a
previous course
taught by
Rodney Howell.

Torben Amtoft