Instructor:

Prerequisites: CS 210 Data Structures and Math 250 Discrete Mathematics.

Textbooks:

Course Overview:

This course is about the design, analysis and use of algorithms. We will study a number of common algorithm design techniques. We will apply each technique to several problems so that we can see how to use the technique in a variety of settings and come to understand how to apply it in new situations. We will also solve some problems using several of the design techniques so that we can compare the different techniques and have a basis for selecting one over another.

We will also look at formal and informal ways to analyze the complexity of algorithms. We will study both the time complexity of an algorithm and the space complexity. These analyses allow us to compare different algorithms for solving a problem. We will also analyze the problems themselves. This will tell us whether the algorithms we have to solve the problem are the best possible, or whether better algorithms might exist.

Finally, the algorithms that we use as examples are interesting and useful in their own right. The algorithms not only illustrate methods of design and analysis, but also solve common problems that arise in a variety of applications.

Tentative Course Schedule:
Weeks 1 - 2: The Basics
Introduction to Algorithms, Asymptotic Notation, Divide-and-Conquer Algorithms, The Master Method, Quicksort
Weeks 3 - 5: Graph Algorithms and Data Structures
Graph Search and Its Applications, Dikstra's Shortest Path, Heaps, Search Trees, Hash Tables
Weeks 6 - 8 Greedy Algorithms and Dynamic Programming
Greedy Algorithms, Huffman Codes, Minimum Spanning Trees, Dynamic Programming, Shortest Paths
Weeks 9 - 10: Intractibility

Grades:

Grades will be based on:
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.

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.

The class MS Team will be used for occasional class meetings, announcements, document sharing, and some Q and A. Students are expected to have notifications turned on for the General, Announcements, and Q and A Channels.

Reading assignments, and related exercises will be assigned for each class. You are expected to do the reading 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.