CS 371: Design and Analysis of Algorithms
Spring, 2014

Instructor: Jessen Havill

Office: Olin 225A

Phone: 587–6582

E-mail: havill@denison.edu

Web site: http://personal.denison.edu/~havill

Office Hours: Please see the schedule on my office door.

Description

An algorithm is informally defined to be any well-defined sequence of computational steps that transforms an input into some output. In this course, we will study in-depth the design, analysis, and implementation of efficient algorithms to solve a variety of fundamental problems. We will also discuss the limits of tractable computation and techniques that can be used to deal with intractability.

The study of algorithms is fundamental to computer science. Indeed, “the design, analysis, and implementation of algorithms” is a good definition for the discipline!

Required Text

Algorithm Design by Jon Kleinberg and Éva Tardos, Pearson, 2006.

Web Resources

The course web site at http://personal.denison.edu/~havill/371/course-schedule.html will contain reading assignments, homework assignments, answer keys, sample programs, and other useful resources. Refer to this page daily for updated information.

We also have a class page set up on Piazza for Q&A and discussion.  When you have a question, please post it to Piazza so that everyone can benefit from the answer.

Attendance and Other Responsibilities

In order to do well in this class (in any class, really), it is important to take on an active role in the learning process. Learning must be an active process in which the instructor is but an important resource.

Your attendance is expected at each class meeting. It is in your own best interest to attend class, as your grade will almost certainly suffer indirectly if you choose not to attend. In addition, I reserve the right to consider attendance in instances of borderline grade assignments. Of course, excused absences (sickness, family emergencies, varsity athletic participation) will not be held against you. Scheduled absences must be communicated to me well in advance.

You are responsible for the content of reading assignments, lectures and handouts, as well as announcements and schedule changes made in class whether or not you are present. If you must miss a class, be sure to check with me or another student to get what you missed. Exams will be given in class on the day scheduled and may not be made up.

It is very important that you keep up with the assigned reading, and that you practice “active reading;” take notes, work out problems, and identify questions you would like to ask in class. Read your book on a daily basis. Be especially sure to read assigned material before coming to class so you will be ready to ask questions. All reading assignments are listed on the class web page. The material in the course is, by necessity, cumulative. Be warned that if you fall behind, you will not be able to catch up easily.

Homework Policies

There will be a number of homework assignments given during the semester which will be due in class on the date specified. No late homework assignments will be accepted, unless arrangements have been made with me well in advance. Since it will most likely not be obvious how long an assignment might take, you are well advised to start early. Like other classes at Denison, it is expected that you devote at least 2–3 hours to these assignments for each hour of class time.

All submitted work must be typeset using LATEX.

Research Project

Each student will perform a research project during the semester culminating in a paper and a presentation to the class. We will discuss this project in more detail during the first week of class.

Academic Integrity

Proposed and developed by Denison students, passed unanimously by DCGA and Denison’s faculty, the Code of Academic Integrity requires that instructors notify the Associate Provost of cases of academic dishonesty, and it requires that cases be heard by the Academic Integrity Board. Further, the code makes students responsible for promoting a culture of integrity on campus and acting in instances in which integrity is violated. Academic honesty, the cornerstone of teaching and learning, lays the foundation for lifelong integrity. Academic dishonesty is intellectual theft. It includes, but is not limited to, providing or receiving assistance in a manner not authorized by the instructor in the creation of work to be submitted for evaluation. This standard applies to all work ranging from daily homework assignments to major exams. Students must clearly cite any sources consulted – not only for quoted phrases but also for ideas and information that are not common knowledge. Neither ignorance nor carelessness is an acceptable defense in cases of plagiarism. It is the student’s responsibility to follow the appropriate format for citations. Students should ask their instructors for assistance in determining what sorts of materials and assistance are appropriate for assignments and for guidance in citing such materials clearly.

You can find further information about Denison’s Code of Academic Integrity on Denison’s web site at http://denison.edu/academics/curriculum/integrity .

In this class, you may discuss problems with other students in the class, but written (and typed) work must be your own. In other words, you may talk about problems with your peers, but when it comes time to write your solutions, you (and your partner) are on your own. You may have general conversations about problem strategies, but you must leave these conversations without having written anything down. Keep in mind that it is quite easy for me to tell when students have been working too closely. You may not get help from students outside the class, except for departmental tutors. If you have questions, come see me and I will be happy to help. You are also quite welcome to send me email or call if you would like to discuss an assignment.

Students found responsible for breaches of academic integrity may earn a failing grade for the course.

Grade Determination

The following relative weights will be used to determine your final grade:

Homework Assignments 30%

Project 20%

2 Mid Term Exams 30%

Final Exam 20%

General Course Topics
  1. Algorithm analysis and asymptotic notation
  2. Greedy algorithms
  3. Divide and conquer algorithms
  4. Dynamic programming algorithms
  5. Network flow algorithms
  6. NP-complete problems
  7. Approximation and online algorithms
  8. Randomized algorithms
Accommodations

Any student who feels he or she may need an accommodation based on the impact of a disability should contact me privately as soon as possible to discuss his or her specific needs. I rely on the Office of Academic Support to verify the need for reasonable accommodations based on documentation on file in their office.

Course Evaluations

At the end of the semester, you will be asked to evaluate this course and the instructor. These evaluations are an important tool for helping Denison faculty achieve and maintain excellence in the classroom; it will also help you reflect on your learning, participation, and effort in the course. A key purpose of course evaluations, then, is to constantly improve the level of teaching and learning at Denison by instructors and students. Your ratings and comments will also be included as one element of an instructor's overall teaching portfolio. Together with peer observations and other means of assessing teaching effectiveness, this portfolio will be considered by the instructor's colleagues and college administrators in making recommendations for contract renewal, tenure, promotion, and salary decisions.

Have a great semester! If you need anything, please let me know.

© Jessen Havill 2020