Computer Science 547 - Discrete Mathematics
Spring 1999

Instructor: Steven Skiena

Office: 1411 Computer Science Building

Phone: 516-632-9026

Email: skiena@cs.sunysb.edu

Office Hours: 10-11:30AM Tuesday-Thursday, and by appointment.

Course Time: 2:20-3:40PM Tuesday-Thursday Place: Studio A ECC

Teaching Assistant: Hui (Huey) Xie

Office: Room 1208 CS Building, 632-7678

Email: xhui@cs.sunysb.edu

Office Hours: Monday-Wednesday 4:45-6:15PM

Textbook: Graham, Knuth, and Patashnik, Concrete Mathematics, a foundation for computer science, second edition, Addison-Wesley, Reading MA, 1994.

Recommended Books: (1) Lecture notes course pack at Solutions. (2) West, Introduction to Graph Theory, Prentice-Hall, 1996.

• The mathematical analysis of algorithms uses a variety of topics from discrete mathematics - combinatorial analysis, number theory, and graph theory. The purpose of this course is to provide fluency with summations, congruences, generating functions, graph theory, and other tools of the trade. The emphasis will be on learning how to attack and solve problems.

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

  Homework Assignments - 15%

  Take home exams - 2 * 20%

  Project - 20%

  Final Exam - 25%

• Homeworks: There will be five homework assignments, each of which is due approximately two weeks later. You may work in pairs on the homework, and turn in only one copy of the assignment per pair. Since complete solutions for many problems are available in the back of the textbook, turning in the correct answers is not necessarily an accomplishment. You will receive most credit if you turn something in for each problem to show that you worked on it.

• Graduate Student Project: This is your opportunity to study some aspect of discrete mathematics in depth. Suitable projects will be term papers, implementations, or preferably original research. A list of possible topics will be distributed about three weeks into the semester, although you are encouraged to create your own. A brief proposal of what you intend to do should be submitted before St. Patrick's Day (March 17). Each student will give a five minute oral presentation on their project during the last week of class.

• Exams: There will be two open book, one week take home exams during the semester. It will be strictly forbidden to discuss the exams with anyone other than the professor or the TA. The final exam will given in class.

Rules of the Game:

1.

The WWW page for the course is http://www.cs.sunysb.edu/$\sim$skiena/547/. All course handouts and notes are available there, along with the latest announcements. Please check it out.

2.

This course is being taught as part of EngiNet, meaning that some students will be taking this course remotely at other sites. If you are a remote student, be sure to contact me ASAP so that we can arrange an appropriate hw/exam delivery mechanism. One benefit is that video tapes of lectures you may have missed might be available, but don't rely too heavily on this technology.

3.

I will lecture from slides, which are available from the campus printshop, Solutions. All the material in this course is presented in the transparencies and/or the book, although sometimes the treatment may not be complete. The recommended book covers graph theory, our topic for the last three weeks of the course, which is not covered by Graham-Knuth-Patashnik.

4.

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.

5.

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.

6.

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.

7.

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.)

8.

If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, I would urge that you contact the staff in the Disabled Student Services office (DSS), Room 133 Humanities, 632-6748/TDD. DSS will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation of disability is confidential.

9.

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.

10.

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

11.

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.