Computer Science 373 / 548 -- Analysis of Algorithms Spring 1996

Instructor: Steven Skiena

Office: 1411 Computer Science Building

Phone: 516-632-9026

Email: skiena@cs.sunysb.edu

Office Hours: 1-2:30PM Tuesday-Thursday, and by appointment.

Course Time: 11:30AM-12:50PM Place: Studio A, ECC Building

Teaching Assistant: Daren Krebsbach

Office: 1307 Computer Science Building

Email: daren@sbcs.sunysb.edu

Office Hours: 3:00-4:30PM Monday-Wednesday, and by appointment.

Textbook: Cormen, Leiserson, Rivest, Introduction to Algorithms, McGraw-Hill, 1990.

• Undergraduate Grading: Grades will be assigned based on the following formula, with cut-offs determined by my opinion of students on the boundary.

  Daily Problems - 5%

  Homework Assignment - 15%

  Midterm 1 - 25%

  Midterm 2 - 25%

  Final - 30%

• Graduate Student Grading: Grades will be assigned based on the following formula, with cut-offs determined by my opinion of students on the boundary.

  Homeworks - 20%

  Midterm 1 - 15%

  Midterm 2 - 15%

  Project - 25%

  Final - 25%

• Homeworks: There will be five homeworks over the course of the semester. The third assignment will be a program. As discussed below, all homeworks (except the third) can be done in pairs. On each homework assignment, only a subset of the problems will be graded.

• Graduate Student Project: This is your opportunity to study some aspect of the design and analysis of algorithms in depth. Suitable projects will be term papers, implementations, or original research. A list of possible topics will be distributed about two weeks into the semester, although you are encouraged to create your own. A brief proposal of what you intend to do must be submitted by mid-March. Each student will give a five minutes oral report on their project during the last week of class.

Rules of the Games:

1. This semester CSE 548 will be part of EngiNet, meaning that all lectures will be videotaped. Any EngiNet students should contact me by email or phone as soon as possible so I am aware of your existence. For local students, these tapes provide an opportunity to review lectures or enable you to attend lectures at an alternate time. A regularly scheduled screening of the previously lecture will be held in room Javits 108, Wednesday-Friday at 11:40-1PM. The tapes are also available for loan or viewing in the AV room in Javits Hall.

2. Combining CSE 373 and CSE 523 has proven very successful each time it has been taught. The grad and undergrad courses will graded on separate curves, and I will expect considerably more from the graduate students, in terms of the project and better performance.

3. I will lecture from slides, which are now more or less available on-line. I will also make copies of my slides available in the CS library after lecture. If there is sufficient demand, we may also make them available through BASIX or a print shop off campus.

4. A WWW page for the course has been set up: http://www.cs.sunysb.edu/~skiena/548/cse548.html All course handouts and notes are available there, along with the latest announcements. Please check it out.

5. The best way to learn the material is by solving problems. You are encouraged to work in pairs, for the best way to understand the subtleties of the homework problems is to argue about the answers. Each of you should look at all the problems independently, and not just divide the list in two parts each time. Don't be a leech and let your partner do all the work. Unless you learn how to solve problems, I promise that you will get burned on the exams and thus for your final grade.

6. The partner system relies upon a certain maturity among the students. If you don't have a partner, tell me and I will hook you up with one. If you are having trouble with your partner and want a divorce, tell me and I will set you up with a new one. I will act as a broker but not as a counselor. I do not want to hear what a louse your old partner is, and you will get a dirty look from me when you demand a divorce regradless of who was at fault.

7. At the start of each class, I will work out one previously identified homework problem, emphasizing the thought process leading to the solution. To get the most benefit from this, you should try to work out the problem before lecture, I will collect your solutions for these daily problems at the beginning of each class.

8. Only one solution to the assignment per pair should be turned in, with the partners alternating who writes up the final solution. The scribe for each assignment will have to label themselves as such. Unless announced otherwise in class, any solution to a part of a homework problem which takes more than one side of a sheet of paper will not be graded. This is to save you the ordeal of trying to impress with volume instead of quality.

9. Because a primary goal of the course is to teach professionalism, any academic dishonesty will be viewed as evidence that this goal has not been achieved, and will be grounded for receiving a grade of F. (See CEAS Procedures and Guideline Governing Academic Dishonesty, 1/81.)

10. If you have any condition, such as a physical or mental disability, which will make it difficult for you to carry out the work as I have outlined it or which requires extra time on examinations, please notify me in the first two weeks of the course so that we may make appropriate arrangements.

11. I understand that everyone gets into a time bind now and then, and that accidents and troubles befall even the most dedicated student. Thus every student will get one free extension on a homework for up to a week without a late penalty. You do not have to ask for this -- just write that you are using your free extension when you turn it in. Don't waste this extension or feel obligated to use it, since you will get a very dirty look if try to get another one even with a good excuse.

12. Homework assignments will be due at the beginning of class. The penalty will be 20% per day.

13. I hope to establish as much personal contact with each of you as is possible in a class this size. Don't be afraid to stop by during office hours to ask questions or say hello. To facilitate interaction, every few weeks there will be 'Pizza with the Prof'. Outside my office will be a sheet for you to sign-up to join 5-10 other students from the class for a pizza lunch (on me). I look forward to getting to know you.