CIS 575, Introduction to Algorithm Analysis, Spring 2019

• Personnel:
  • Instructor: Torben Amtoft, tamtoft hat ksu dot edu,
  • Teaching Assistant: Lei (Ray) Luo, leiluoray hat ksu dot edu
  • Teaching Assistant: Sudesh Venkatramolla, sudeshv hat ksu dot edu
• Schedule:

  Event	Place	Monday	Tuesday	Wednesday	Thursday	Friday
  Classes	Durland 1073	2:30-3:20pm		2:30-3:20pm		2:30-3:20pm
  Torben Office Hours	Engineering 2179		3-4pm		2-3pm	11am-noon
  Ray Office Hours	Engineering 1119	3:30-5pm		3:30-5pm
  Sudesh Office Hours	Engineering 1117	noon-2pm	10-11am

• Communication: Use the email address help-575@santoslab.org for all questions about lectures, homework, and appointments. Do not email the TAs or instructor directly, 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), and 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 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 Homepage: http://people.cis.ksu.edu/~tamtoft/CIS575/S19/index.html.
• Up-to-date Log File: http://people.cis.ksu.edu/~tamtoft/CIS575/S19/log.html.
• Reading Material: Introduction to Algorithms, Thomas H Cormen & Charles E Leiserson & Ronald L Rivest & Clifford Stein, 3rd Ed., MIT Press, 2009.
  Suggested further reading (optional): Algorithms: A Top-Down Approach, Rodney Howell, 9th draft (available online).

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

• Algorithm correctness
• Worst-case asymptotic analysis
• Various data structures, such as
  • Graphs and trees
  • Priority queues
  • Union/find structures
• Various design techniques, such as
  • Divide-and-conquer algorithms
  • Greedy algorithms
  • Dynamic programming algorithms
• Certain frequently occurring settings, such as
  • Depth-first search
  • Network flow and matching

Homeworks are due almost every week (on Thursday night) and are to be submitted through Canvas.

Quizzes will be frequently given in class. We will be using the Top Hat www.tophat.com classroom response system in class. You will be able to submit answers to in-class questions using Apple or Android smartphones, tablets, laptops, or through text messages.
You can visit the Top Hat Overview (https://success.tophat.com/s/article/Student-Top-Hat-Overview-and-Getting-Started-Guide) within the Top Hat Success Center which provides a brief overview to get you up and running on the system.

You will receive (a few days before course start) an invitation by email, but otherwise you can register by visiting our course website: https://app.tophat.com/e/909821. Note: our Course Join Code is 909821
Top Hat may require a paid subscription, and a full breakdown of all subscription options available can be found here: www.tophat.com/pricing.
Should you require assistance with Top Hat at any time, please contact their Support Team directly by email (support@tophat.com), the in app support button, or by calling 1-888-663-5491.

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 16: 25%
• In-class quizzes: 10%

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 somewhat more than 80 % (and at least 75% on the final) to earn an A, and a little above 65 % (and at least 60% on the final) to earn a B.
In general, my approach to grading is expressed well by this piece by S.A. Miller.

Lateness: If you have a documented medical or family emergency, or a certified excused absence for official university activities, you should notify the instructor as soon as possible.

• In such a case, you may be granted extensions for homework assignments, and we will open up in-class quizzes so that you can do them over the next days. For exams, we do not offer make-ups, but will disregard that exam (this is roughly equivalent to eventually assigning you a score close to your average for the other two exams).
• If you do not have a valid excuse, you should not expect any points for missed exams or late assignments, with the following exception: if you submit an assignment less than 12 hours after the deadline, we will grade it, but afterwards subtract 20% of your score.

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

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. The Honor and Integrity System website can be reached via the following URL: www.k-state.edu/honor

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.
• You are not allowed to show your answers to, or look at the answers of, any other student --- this of course excludes any student that you have been allowed to team up with, but in such a case each of you must be able to understand and explain all parts of the submitted work.

Students with Disabilities: Students with disabilities 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;

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.

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

Copyright 2019 (Torben Amtoft) as to 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.