CIS 575, Introduction to Algorithm Analysis, Spring 2021
Summary
This course (3 credit hours) teaches important concepts
involved in the design and analysis of algorithms.
This semester, this course is fully online!
Lecture notes and video lectures will be posted on Canvas, as will quizzes,
homework assignments, and exams.
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
-
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.
-
Textbooks
-
While it is possible to successfully complete the course
by studying only the material posted on Canvas,
we recommend some deeper reading
(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 online textbook is designed to provide motivation that will
help you to learn and appreciate the various topics.
Logistics
For each week (cf the
course schedule),
-
lecture notes on the given topic(s) have been posted
(by Friday in the previous week), together with short video lectures
-
quizzes on the given topic(s) will be due Tuesday night
in the following week
-
a homework assignment may be due on Thursday night,
on topics covered the previous week
(it will have been posted by Wednesday
in that week, together with a short lecture explaining it)
-
the instructor, and the TAs, will each have multiple Zoom office hours
(requiring passwords which will be posted on Canvas)
at various days and times.
Depending on the number of students
attending, the waiting room facility may be used.
Personnel
-
Instructor:
Torben Amtoft,
tamtoft hat ksu dot edu
-
Teaching Assistant:
Bishwas Mandal, bishmdl76 hat ksu dot edu
-
Teaching Assistant:
Soudabeh Taghian Dinani, soudabehtaghian hat ksu dot edu
Weekly Schedule
Communication
Use the email address
help-575@santoslab.org for all questions about lectures, homeworks, etc. Do not email the TAs or instructor directly
(unless there is a very good reason),
and do not use Canvas messaging to contact us.
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 the instructor to give).
Grading
-
Exams
-
will be given as Canvas quizzes:
- there will be some flexibility on when in the
week to take a given exam
(likely Tuesday and/or Wednesday)
- but once you start the exam you must finish within a certain time
-
the third (final) will be comprehensive,
but with emphasis on the last part of the course
-
details about proctoring will be provided later.
-
Weighting
-
-
Homework assignments: 25%
-
Quizzes: 15%
-
Exam 1: 15%
-
Exam 2: 15%
-
Exam 3: 30%
-
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 close to 60%
In general, my approach to grading is expressed well by
this
piece by S.A. Miller.
- Lateness
-
Late deliverables will not be graded,
with one exception: if you submit a homework assignment 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.
-
Missing Deliverables
-
Given the highly unusual circumstances during also this semester,
we will not ask for
documentation for medical conditions, family emergencies,
official university activities, etc.
If you do not submit a deliverable, we will disregard it, that is, it
will not influence the final grade (which will be determined by the
scores on the deliverables that you do submit).
However, if you miss a number of deliverables that together count more
than 8% of the total grade, please contact the instructor. Depending on the
situation, he may in such cases assign a score of zero for some or all
of the missing deliverables,
or (if the bulk of course work has been completed in passing fashion)
assign you an Incomplete (I) for the course.
-
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.
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:
-
You are not allowed to consult previous model solutions that
may be around, or solicit the Internet for solutions to
specific homework problems
(but you are very welcome
to search for general material that gives alternative presentations
of the topics of the course!)
-
You are not allowed to show your
answers to, or look at the answers of, any other student.
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!
who need classroom accommodations, access to technology, or information about emergency building/campus evacuation processes should contact the Student Access Center and/or their instructor. Services are available to students with a wide range of disabilities including, but not limited to, physical disabilities, medical conditions, learning disabilities, attention deficit disorder, depression, and anxiety. If you are a student enrolled in campus/online courses through the Manhattan or Olathe campuses, contact the
Student Access Center
at accesscenter@k-state.edu, 785-532-6441.
Copyright 2021 (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.
Torben Amtoft