CIS 775, Analysis of Algorithms, Fall 2022
This syllabus is subject to (hopefully only minor) modifications
This course (3 credit hours)
teaches important concepts
involved in the design and analysis of algorithms.
This semester, this course will be offered fully in-person,
and also as a distance course.
Detailed course material will be posted on Canvas,
accessible also for on-campus students
(who will need to be on campus only for exams but certainly are much
encouraged to show up in class).
Students are expected to have the following background:
significant experience with programming in some
high-level programming language
familiarity with standard data structures such as lists, trees, graphs, etc.
understanding of fundamental mathematics such as:
basic set theory, propositional and predicate logic, functions, solution of equations, limits, summations,
derivatives and integrals, combinatorics
ability to write rigorous proofs.
See the course schedule (separate document).
Students should attain competency in the following:
In addition, students should get to appreciate and be familiar with
mathematical analysis of algorithms:
their running times and
space usage, and their
recognizing and applying algorithmic design techniques.
mathematical rigor in solving theoretical problems
the significance and ramifications of some problems being known
to be (NP)-hard.
- 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
Introduction to Algorithms
by Thomas H Cormen & Charles E Leiserson &
Ronald L Rivest & Clifford Stein,
4th Ed., MIT Press, 2022.
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 (for now) available at
and is designed to provide motivation that will
help you to learn and appreciate the various topics.
For each class,
lecture notes on the given topic(s) will have been posted
quizzes on the given topic(s) will be due one week later.
The instructor makes efforts to keep up with email (please do not
use Canvas messaging) even though he may not check his inbox all the time (to decrease disruption of productivity, he usually reads his email only twice or thrice a day). But you may expect an email answer no later than on the next business day, 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 the instructor to give).
Deliverables and Grading
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.
On-campus students must take the exams on campus
Distance students must take the exams proctored by the Examity system
(details to be provided).
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 aim to reschedule; if that is not possible,
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 almost every week,
on topics covered the previous week.
The lowest assignment score will be disregarded.
(But if you can document valid excuses for not submitting
two assignments, they will both
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.
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 two times: the third non-submitted quiz,
and each subsequent, will (at the end of the semester)
be converted to a zero.
Extra credit will be given if you actively contribute to
the learning climate
by constructive and interesting comments and questions
(as subjectively judged by me).
Homework assignments: 25%
Exam 1: 16%
Exam 2: 16%
Final Exam: 25%
are not based on strict percentage cutoffs but are
"curved" by taking into account the difficulty of the exercises and
As a rule of thumb, however, you should expect
In general, my approach to grading is expressed well by
piece by S.A. Miller.
to earn an A will require a bit more than 85%
to earn a B will require around 70%
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.
If you think the instructor has 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).
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.
If you are in doubt about what is permissible, please ask me.
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).
At K-State it is important that every student has access to course content and the means to demonstrate course mastery. Students with disabilities may benefit from services including accommodations provided by the Student Access Center. Disabilities can include physical, learning, executive functions, and mental health. You may register at the Student Access Center (k-state.edu/accesscenter) or to learn more contact:
Manhattan/Olathe/Global Campus - Student Access Center
Students already registered with the Student Access Center please request your Letters of Accommodation early in the semester to provide adequate time to arrange your approved academic accommodations. Once SAC approves your Letter of Accommodation it will be e-mailed to you, and your instructor(s) for this course. Please follow up with your instructor to discuss how best to implement the approved accommodations.
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 V, Section 3, number 2. Students who engage in behavior that disrupts the learning environment may be asked to leave the class.
Mandatory Statement on Mutual Respect and Inclusion in K-State Teaching and Learning Spaces
At K-State, faculty and staff are committed to creating and maintaining an inclusive and supportive learning environment for students from diverse backgrounds and perspectives. K-State courses, labs, and other virtual and physical learning spaces promote equitable opportunity to learn, participate, contribute, and succeed, regardless of age, race, color, ethnicity, nationality, genetic information, ancestry, disability, socioeconomic status, military or veteran status, immigration status, Indigenous identity, gender identity, gender expression, sexuality, religion, culture, as well as other social identities.
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
Kansas State University strongly encourages, but does not require, that everyone wear masks while indoors on university property, including while attending in-person classes. 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.
Mandatory Statement Regarding Discrimination, Harassment, and Sexual Harassment
Kansas State University is committed to maintaining academic, housing, and work environments that are free of discrimination, harassment, and sexual harassment. Instructors support the University's commitment by creating a safe learning environment during this course, free of conduct that would interfere with your academic opportunities. Instructors also have a duty to report any behavior they become aware of that potentially violates the University's policy prohibiting discrimination, harassment, and sexual harassment (PPM 3010).
If a student is subjected to discrimination, harassment, or sexual harassment, they are encouraged to make a non-confidential report to the University's Office for Institutional Equity (OIE) using the online reporting form. Incident disclosure is not required to receive resources at K-State. Reports that include domestic and dating violence, sexual assault, or stalking, should be considered for reporting by the complainant to the Kansas State University Police Department or the Riley County Police Department. Reports made to law enforcement are separate from reports made to OIE. A complainant can choose to report to one or both entities. Confidential support and advocacy can be found with the K-State Center for Advocacy, Response, and Education (CARE). Confidential mental health services can be found with Lafene Counseling and Psychological Services (CAPS). Academic support can be found with the Office of Student Life (OSL). OSL is a non-confidential resource. A comprehensive list of resources is available here. If you have questions about non-confidential and confidential resources, please contact OIE at email@example.com or (785) 532-6220.
Copyright 2022 (Torben Amtoft) as to this syllabus and all lectures. 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. In addition, students in this class are not authorized to provide class notes or other class-related materials to any other person or entity, other than sharing them directly with another student taking the class for purposes of studying, without prior written permission from the professor teaching this course.