I am experiencing problems updating this page. As long as this
message is here, trust moodle instead as some of this inforamtion
may be out of date.
Prerequisites: CS 210 Data Structures and Math 250 Discrete Mathematics.
Textbook: Corman, et al: Intoduction to Algorithms, 3rd Edition, MIT Press, Cambridge, Mass.
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.
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, announcements, class notes, 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 frequently.
Reading assignments and related exercises will be assigned for each class. You are expected to come to class having completed the assignment and being prepared to discuss both the ideas from the reading and your solutions to the exercises. You are encouraged to work on these exercises in groups; just be sure that each group member understands each answer well enough to present it to the class. When presenting an answer, you should acknowledge any help that you received. It is necessary to 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 ways to find a solution as well as the solution itself. Due to the nature of the small class we will usually discuss exercises together as a group.
Homework assignments and programming projects will be assigned throughout the quarter. Homework assignments and programming projects are due by 4:00 pm on the due date. You have two "late days". With the use of a late day, assignments must be submitted by 4:00 pm on the day following the original deadline, or 4:00 pm the following Monday if the deadline was on a Friday. Once you have used up your late days, late assignments will be accepted for half credit up to one week after the original due date. Assignments more than one week late will not be accepted. 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.
Programming projects may be done in pairs. I reserve the right to limit the number of times you may work with the same partner.
The course will also involve a mid-term and a final examination. Obviously your answers to exam questions 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.
Grades will be based on:
Examinations 30% Homework Assignments 20% Projects 40% Attendance and Class Participation 10%