CIS 775, Analysis of Algorithms, Fall 2020


This course (3 credit hours) teaches important concepts involved in the design and analysis of algorithms.


Students are expected to have the following background:


This semester, this course can be successfully completed online, without ever showing up on campus!

Lecture notes and video lectures will be posted on Canvas, as will quizzes, assignments, and exams.


Torben Amtoft, tamtoft hat ksu dot edu

Course Schedule (click on link)

Weekly Schedule

Zoom link
MondayTuesday WednesdayThursdayFriday
Class 8:05-
Hours 1:00-

Meeting agendas

At least 24 hours before regular class time, the instructor will have posted lecture notes and video lectures. Our two weekly meetings will therefore not contain lectures but instead be conducted as follows:
  1. the instructor may talk about recent, or upcoming, assignments
  2. along the way, or afterwards, students may ask questions, about the assignments, about current or recent course material, etc
  3. while answering those questions, the instructor may elaborate on his lectures, in particular work out further examples
  4. when the agenda for the meeting is exhausted, and there are no more questions, the meeting will end (therefore aim to join from 8:05am!)
Zoom meetings will not be recorded, in the hope that you will feel more free to ask questions. But when important points of general interest are raised, the instructor will post a summary on Canvas.

The instructor will host a weekly office hour at the time listed above. Depending on the number of students attending, the waiting room facility may be used. These office hours will not close prematurely; you may enter at any time during the listed interval.

The Zoom meetings require passwords which will be posted on Canvas.


Please email the instructor directly, rather than thru Canvas messaging. Even though the instructor usually (to decrease disruption of productivity) checks his inbox only a few times each day, it is his 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), but very 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 the instructor to give).

Course Material


While it is possible to successfully complete the course by studying only the material posted on Canvas, we recommend some deeper reading (the posted lecture notes will 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 online textbook is designed to provide motivation that will help you to learn and appreciate the various topics.

Expected Outcome

Students should master the following knowledge and skills: In addition, students should become familiar with NP-completeness and related topics.


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 In general, my approach to grading is expressed well by this piece by S.A. Miller.


are due almost every Thursday (before class) and are to be submitted through Canvas.


will be open book/notes, and will be given online (as Canvas quizzes).

The second exam will be comprehensive (but with some emphasis on the latter part of the course).

Both exams will be proctored, using Examity.


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

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

If you are in doubt about what is permissible, please ask me. I very much hope that it will not be necessary to file any honor pledge violation reports during the semester!

Other Administrative Issues

Wearing of Face Coverings

To protect the health and safety of the K-State community, students, faculty, staff and visitors must wear face coverings over their mouths and noses while on K-State campuses in all hallways, public spaces, classrooms and other common areas of campus buildings, and when in offices or other work spaces or outdoor settings when 6-feet social distancing cannot be maintained. In addition, all students, faculty, and staff are required to take the COVID-19 and Face Mask Safety training. Employees who need reasonable accommodations and assistance related to required face coverings may contact the ADA coordinator at, and students needing accommodations may contact the Student Access Center at

In classrooms, faculty have the right to deny a student entry into the room if the student is not wearing a face covering. Students not wearing a face covering will be reminded to do so and offered a clean face covering, if one is available. If the student does not comply, the faculty member will ask the student to leave the space, and if available, join the class remotely. As a last resort, campus police will be called. The faculty members will complete the Code of Conduct form and the Office of Student Life will look further into the issue and take the non-compliance with the request to leave into consideration of further accountability measures.

At no point should the professor or other students put themselves into an unsafe situation while attempting to enforce the face-covering policy. Manhattan campus police: 785-532-6412

Torben Amtoft