cs504 Course Introduction

cs504, S98/99 Course Introduction

This course is about the mathematical analysis of algorithms; this material is part of the theoretical foundations of computer science. We will examine analytical tools and use them to discuss the efficiency of some of the most widely used algorithms in computer science, including searching and sorting. Examples will be drawn from across much of computer science.

Expected Background

This course expectes you understand the following material, which can be acquired by taking the WPI course cs507.

introductory data structures (at the undergraduate level),
diiscrete structures and mathematical maturity.

Course Meetings

This course meets in two sections. Students may attend either or both sections. The course instructors are coordinating closely and the lectures are substantially similar.

WPI Waltham Campus, Monday 18:00-21:00, Room 501

WPI Worcester Campus, Wednesday 17:30-20:30, Room KH320

Text

There is one required text

R Sedgewick and P Flajolet, An Introduction to the Analysis of Algorithms (1996, Addison-Wesley), ISBN 0-201-40009-X. Note that a list of errata is available.

There are two recommended texts.

M Hofri, Analysis of Algorithms, (1995, Oxford University Press), ISBN 0-19-509954-0. Note that a list of eratta is available.

DL Graham, DE Knuth, and O Patashnik, Concrete Mathematics, A Foundation for Computer Science, 2nd Edition (1995, Addison-Wesley), ISBN 0-2-1-55802-5. Note that a list of eratta is available.

Teaching Stuff. How to Communicate with Us or with the Entire Class

See the Teaching Staff web page.

Grading Policy and Practices

Homework - 40%

The homework will consist of written assignments and programs. Assignments and programs are due at the beginning of class on the due date (Note that the due date at the Worcester Campus is two days later than at the Waltham Campus). You may submit homework at either of the class sessions (but not both!). Late homeworks will not be accepted for any reason. Twelve homeworks will be assigned. Each homework is worth 4% of the total course grade and the lowest two of the homeworks will be dropped - only the ten highest grades will count. You may work with other students and obtain assistance from any source except that you must describe any collaboration in your homework paper and you must author anything you submit by yourself. We think it is useful to collaborate but it is essential that you write and submit unique work.

Exams - 60%

There are two open-book, open-notes exams. You may take an exam either in Waltham or in Worcester, but not in both. Each exam counts for 30% of the grade and no makeup exams will be given for any reason.

Cooperation

You are encouraged to work with other students. In fact, it is our experience that students who form study groups to discuss the material generally perform better; However, your homeworks and exams are your responsibility alone. It is acceptable, even preferable, to discuss the homework in a group, but you must write up your solutions yourself without consulting others. Turning in someone else's work or modifications of someone else's work, whether it was obtained with or without permission, is unacceptable. Cooperating in any form during Exams is not allowed. Please read the WPI Academic Honesty Policy since we will follow that policy exactly as published. If you have any questions about this policy, please discuss them with the Instructors.