CIS 575, Introduction to Algorithm Analysis, Spring 2022

Summary

This semester, this course will be offered fully in-person.
Still, detailed lecture notes will be posted on Canvas.

Content

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 programming experience in some high-level language
• 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.

Topics

See the course schedule (separate document).

Expected Outcome

Students should attain competency in the following:

• Analyzing algorithms and data structures, with respect to
  • running times and space usage
  • correctness properties
• Recognizing and applying algorithmic design techniques.

Additional information sources

The uploaded lecture notes will provide all the material needed to successfully complete the course.
Still, you may benefit from some optional readings (the lecture notes contain references to specific sections):

• Introduction to Algorithms by Thomas H Cormen & Charles E Leiserson & Ronald L Rivest & Clifford Stein, 3rd Ed., MIT Press, 2009.
  This renowned book is a useful reference which could be very helpful even in your future career.

• Algorithms: A Top-Down Approach by Rodney Howell, 9th draft.
  This textbook is available at http://people.cis.ksu.edu/~rhowell/algorithms-text/
  and is designed to provide motivation that will help you to learn and appreciate the various topics.

Logistics

• lecture notes on the given topic(s) will have been posted
• quizzes on the given topic(s) will be due one week later.

Personnel

• Instructor: Torben Amtoft
• Teaching Assistants: Mohammad Saeid Mahdavinejad, and Bishwas Mandal

Weekly Schedule

Communication

We make efforts to keep up with email, even though we may not check our inboxes all the time (to decrease disruption of productivity, the instructor usually reads his email only twice or thrice a day). It is our goal that you should expect an email answer no later than on the next business day. So if you send an email on Friday, we will aim to get back to you the next day the university holds classes (which will typically be Monday), and often even earlier.

For questions (or comments) of general interest, we strongly encourage that you post in the Canvas discussion forum so that also other students will benefit from the answers. We even encourage you to answer questions from other students (of course you should not give more hints towards solutions than you would reasonably expect us to give).

Deliverables and Grading

Exams

will be open book and open notes, with the third (final) comprehensive but with emphasis on what was covered in the last part of the course.

If you do not show up for an exam, then

• if you can document a valid excuse (such as illness, or conference travel) we will disregard that exam and it will not count towards your final grade. (But if you have to skip two exams, you must make up for that in some way, or perhaps get an Incomplete for the course.)
• otherwise, you will get a zero, except that you may be allowed to take the exam shortly afterwards (with some points subtracted from your score).

Homework Assignments

are due on Thursday night almost every week, on topics covered the previous week.

• If you submit an assignment late but less than 12 hours after the deadline, we will grade it, but afterwards subtract up to 20% (proportional to the delay) of the score you earned.
• If you have not submitted 12 hours after the deadline, you'll receive a zero for that assignment.

The lowest assignment score will be disregarded. (But if you can document valid excuses for not submitting two assignments, they will both be disregarded.)

Quizzes

are posted after each class (when new material has been introduced) and are due one week later; for each quiz you may submit up to 5 times (the highest score counts).

If you do not attempt to submit a quiz, it will be disregarded, but only up to three times: the fourth non-submitted quiz, and each subsequent, will (at the end of the semester) be converted to a zero.

Weighting

• Homework assignments: 25%
• Quizzes: 18%
• Exam 1: 16%
• Exam 2: 16%
• Exam 3: 25%

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

• to earn an A will require a bit more than 85%
• to earn a B will require somewhat more than 70%
• to earn a C will require around 60%

In general, my approach to grading is expressed well by this piece by S.A. Miller.

Drop Policy

It is your responsibility to drop the course if you are enrolled but decide not to complete the course; there are no "automatic" drops due to nonattendance.

Grievances

If you think the instructor or the TAs have made an error 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).

Various Statements

Academic Honesty

Kansas State University has an Honor and Integrity 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 and Integrity System. The policies and procedures of the Honor and Integrity 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 and Integrity 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 allowed and encouraged to discuss assignments with each other and with us. However, the final write up that you submit should be solely your understanding of the solutions and should be written individually (and not shown to anyone else).
• You are welcome and encouraged to search the Internet for general material that gives alternative presentations of the topics of the course, but you are not allowed to solicit for solutions to specific homework problems (or consult previous model solutions that may be around).

Students with Disabilities

Expectations for Classroom Conduct

Mandatory Statement on Mutual Respect and Inclusion in K-State Teaching and Learning Spaces

Faculty and staff are committed to promoting equity and believe the success of an inclusive learning environment relies on the participation, support, and understanding of all students. Students are encouraged to share their views and lived experiences as they relate to the course or their course experience, while recognizing they are doing so in a learning environment in which all are expected to engage with respect to honor the rights, safety, and dignity of others in keeping with the K-State Principles of Community https://www.k-state.edu/about/values/community/.

If you feel uncomfortable because of comments or behavior encountered in this class, you may bring it to the attention of your instructor, advisors, and/or mentors. If you have questions about how to proceed with a confidential process to resolve concerns, please contact the Student Ombudsperson Office. Violations of the student code of conduct can be reported here https://www.k-state.edu/sga/judicial/student-code-of-conduct.html. If you experience bias or discrimination, it can be reported here https://www.k-state.edu/report/discrimination/.

Mandatory Statement Regarding Wearing of Face Masks

All students are expected to comply with K-State's face mask policy. As of August 2, 2021, everyone must wear face masks over their mouths and noses in all indoor spaces on university property, including while attending in-person classes. This policy is subject to change at the university's discretion. For additional information and the latest on K-State's face covering policy, see https://www.k-state.edu/covid-19/guidance/health/face-covering.html.

Copyright notification