Vassar College, Spring 2009

Syllabus / Course Wiki

Our course syllabus is a wiki. It is subject to update throughout the semester.

Cormen, Leiserson, Rivest, and Stein Introduction to Algorithms, 2e, MIT Press, 2001.
Available in the bookstore.

Algorithmics is also known as the analysis of algorithms. This analysis transcends the specific limitations of any particular programming language or computing platform. To describe a problem algorithmically is to define the set of possible input and output instances and to provide each step of the problem solution in sufficient detail for that step to be converted into a form that is understood by a computer. The analysis of algorithms involves the estimation and comparison of the time and space requirements of different algorithmic solutions for a particular problem. Generally speaking, the efficiency is described as a function of the size of the input.

Obviously, an efficient algorithm that produces incorrect output is not useful. Therefore, our job as algorithm analysts also requires us to prove that each particular algorithm will produce the correct output for every possible input instance.

Comparing the relative efficiency of algorithms and proving algorithm correctness are fundamental skills that must be mastered by every computer scientist. Practically speaking, efficiency and correctness are serious concerns of every person that will potentially use an algorithm. Algorithms that consume large quantities of data or that model large, complex systems are an integral part of most modern-day scientific disciplines, as well as many non-science-oriented fields. An algorithm that can be shown to solve a problem (i.e., process the input to produce the correct output) faster or using less memory is more efficient than one that solves the same problem slower or using more memory.

By the end of the semester you should:

• be familiar with fundamental algorithms and algorithmic techniques for many given problem domains,
• be able to decide which algorithm among a set of possible choices is the most efficient solution,
• be able to prove correctness and to analyze the running time of a given algorithm, and
• be able to design efficient algorithms for new problems.

• Introduction and Mathematical Fundamentals - Chapters 1, 2, 3, and 4
• Sorting - Chapters 6, 7, and 8
• Selection - Chapter 9
• Hashing - Chapter 11
• Basic Graph Algorithms - Chapters 22, 23, and 24
• Data Structure for Disjoint Sets - Chapter 21
• Dynamic Programming and Greedy Algorithms - Chapters 15, 16
• Geometric Algorithms - Chapter 33
• NP-Completeness - Chapters 34, 35

Lecture slides will be distributed prior to their presentation in class as an aid to note-taking and will be posted at a link on this web site.

• First Exam (Take-home, February 26)
• Second Exam (Take-home, April 16)
• Third Exam (Take-home, May 5)
• Assignments
• Class participation

The assignments will have cumulative weight that is equal to one exam (each exam will account for roughly 20% of the grade). Assignments are designed to emphasize only recently-covered material and, once assigned, will generally be due at the start of the next class period. Exams and will either be given in class or take-home and will be open-book and open-note format. The dates given above for the exams may be subject to change.

Note: You must have both a passing cumulative score on the assignments and a passing cumulative score overall in order to pass this course.

I encourage you to discuss ideas for assignment solutions with your classmates and to form study groups. However, be aware that you must include names of collaborators and outside sources as part of your assignment submission. Assignments are designed to prepare you for exam questions and significant discrepancies between your performance on assignments and exams will be taken into consideration in your final grade.

Any collaboration of which I am not informed will be considered as a violation of academic integrity.

Any student(s) suspected of going beyond the limits of academic integrity will be referred to the Dean of Students and the Academic Panel.

All assignments are due at the start of class on the date specified.

Late assignments will not be accepted UNLESS I am informed before-hand about the reason for the late submission or if you can produce a valid excuse.

If you do not get permission from me to submit an assignment after the deadline and you lack an official excuse, you will receive a score of 0 for the assignment.

Valid excuses must come through Baldwin Health Services or from the Dean of Studies office or be approved in advance by the instructor.