CS 215 Syllabus

Instructor


Prerequisites

Successful completion of CS 210: Data Structures and Math 250: Discrete Mathematics is required.

Textbooks

Course Overview

This course is about the design, analysis, and use of algorithms. We will study a number of common algorithm design techniques. Each technique will be applied to several problems so that we can see how it works in a variety of settings and learn to apply it in new situations. We will also solve some problems using multiple techniques, so we can compare approaches and understand when one is more effective than another.

We will also look at formal and informal ways to analyze the complexity of algorithms, including both time and space complexity. These analyses allow us to compare different algorithms for solving the same problem. We will also analyze the problems themselves to determine whether the algorithms we have are optimal or if better ones might exist.

Finally, the algorithms we study are interesting and useful in their own right. They not only illustrate design and analysis methods, but also solve common problems that arise across a wide range of applications.

Tentative Course Schedule

Week-by-week overview of course topics
Weeks Topics
1 – 2 Introduction to Algorithms, Asymptotic Notation, Divide-and-Conquer Algorithms, The Master Method, Quicksort
3 – 5 Graph Search and Its Applications, Dijkstra's Shortest Path, Heaps, Search Trees, Hash Tables
6 – 8 Greedy Algorithms, Huffman Codes, Minimum Spanning Trees, Dynamic Programming, Shortest Paths
9 – 10 Intractability

Grades

Grades will be based on the following components:

Grade breakdown by component
Component Weight
Homework, In-class Activities, Programming Assignments 50%
Presentation 15%
Reflective Responses, Quizzes, Tests 35%

Attendance and Participation

Regular attendance and participation is expected of all students and will affect your grade. Active participation in this class means coming to class on time, completing assigned reading and exercises, listening to others, contributing ideas of your own, and asking questions as they come up. There are direct correlations between keeping up, how much you learn and can apply later, and your grade.

Assignments, Collaboration, and the Honor System

This course operates in accordance with the principles of the Kalamazoo College Honor System. Unauthorized collaboration and receiving help from others outside the bounds permitted by the instructor are also violations of the College honor code. You are responsible for working within the permitted bounds, and acknowledging any help from others or contributions from other sources. Failure to do so will result in consequences that may include failure of an assignment, failure of the course, or referral to the Dean of Students.

Assignments, class notes, class videos, and other material will be made available on the course web site (http://www.cs.kzoo.edu/cs215/). Students are responsible for checking this resource and refreshing their browser frequently.

Reading assignments, and related exercises will be assigned for each class. You are expected to do the reading and watch any videos before class. You are encouraged to work on the discussion exercises in groups; just be sure that each group member understands each answer well enough to present it to the class. You should make an effort to solve each exercise but don't expect to 'get' all of the answers. It is helpful to the whole class to see the process to find a solution as well as the solution itself. Class time will often be spent working in small groups on discussion questions and homework problems.

Homework assignments will be assigned throughout the quarter. Homework assignments are due by the end of the day on the due date. If you get stuck on a homework problem or just want to see if you are heading in the right direction, the TAs and I are quite willing to help you. You may also discuss the requirements, concepts, and overall strategies related to homework problems with your classmates. It is important that you write up your homework solutions individually, acknowledging any ideas from others that you have used. Organizing and writing up the solutions on your own ensures that you really understand the solution. Submitting a copied solution as your own work is plagiarism, and will be dealt with accordingly. You are strongly encouraged, but not required, to type up your homework assignments. Any handwritten assignment that cannot be clearly read is subject to a loss of points.

At least one Programming project and several smaller programming assignments will be assigned during the quarter. Projects and programming assignments may be done in pairs. I reserve the right to adjust grades based on team participation. You may discuss ideas and strategies for projects with others in the class but you may not share code or code fragments with anyone outside of your team. Sharing code constitutes academic dishonesty and will be dealt with as such. You should list anyone with whom you collaborated or from whom you received help in a With Assistance From: clause in your program documentation. If you work with a partner on a project, you should indicate both authors in the program documentation and turn in only one copy of the program for the team (not one for each team member).

Two documents, the CS Program Style Guide and Documentation Standards, describe the programming style and documentation standards for this course. Following these standards is an important step towards writing well-structured and reusable programs. You may use two templates that have been created to help you meet the documentation standards: the class template and main class template.

All students will give at least one Presentation with a partner and will be expected to give reflective feedback on others' presentations.

The course will also involve at least two Reflective Responses. These will be opportunities to describe key ideas that have been covered in class and to reflect on what you've learned so far. These will tentatively take place at the end of 5th week and at the end of 9th week, as well as at the end of any programming project. There may be occasional quizzes throughout the quarter to check understanding of concepts. Obviously your answers to quizzes should be entirely your own work and not the result of collaboration with others.  If the use of outside sources (such as the textbook) is permitted, be careful to cite ideas and material from those sources, whether derived, summarized, quoted or paraphrased. If collaboration is allowed on a quiz, that will be specified clearly before the quiz is taken.

Late submission policy: Assignment due dates have two important functions: to help you plan your time and keep you on track to successfully complete the course, and to make grading more manageable. Late assignments will accrue late penalties or might not be accepted at all. To encourage timeliness, assignments that are one day late will lose 2%; two - three days late will incur a 4% loss. After three days, the loss will jump significantly to 10% or more. In unusual circumstances an extension may be granted, but only if you speak to your instructor in advance.

Title IX Support and Responsibilities

Accommodations

At Kalamazoo College we are committed to making education accessible to all students. Students needing academic accommodations for a disability must first contact Disability Services to verify the disability and to establish eligibility for accommodations. Students may call the Student Development Office (269) 337-7209 or visit Disability Services to begin the process. After accommodations have been approved, it is the student’s responsibility to work with professors to make specific arrangements. Please be aware that no accommodations will be provided without documentation from the Disability Services Office. For more information please visit Disability Services.