Summer 2003

Tuesday 6:00-8:20pm

Room 102, Warren Weaver Hall

**Instructor
**

David Tanzer

tanzer@cs.nyu.edu

Room 401, Warren Weaver Hall

Office hours: Tuesday 8:20 to 9:30 pm

Phone: (212) 998-3018

**Teaching Assistant**

Elif Tosun

tosun@cs.nyu.edu

Room 1210, 719 Broadway (at the 12th floor, dial 83339 to reach her)

Office hours: Tuesday 5:00 - 6:00, Thursday 1:00 - 2:00

Phone: (212) 998-3339

**Announcement**

Midterm is Tues. July 1, in class. Closed book.

**Textbook**

Discrete Mathematics with Applications, 2nd editionby Susanna S. Epp, Brooks/Cole Publishing Company, 1995

**Tentative schedule**

Lecture Date Lecture Topic Reading 1 May 20 Logic of Compound Statements Chapter 1 2 May 27 Logic of Quantified Statements Chapter 2 3 June 3 Elementary Number Theory and Methods of Proof Chapter 3 4 June 10 Sequences and Mathematical Induction Chapter 4 5 June 17 Set Theory Chapter 5 6 June 24 Counting Chapter 6 7 July 1 Functions Chapter 7 8 July 8 Recursion Chapter 8 9 July 15 O-notation and Efficiency of Algorithms Chapter 9 10 July 22 Relations Chapter 10 11 July 29 Graphs and Trees Chapter 11 12

Aug 5

Final exam

Very Important: Because this course is preparation for Fundamental Algorithms, students who have taken Fundamental Algorithms and obtained a grade B or better CANNOT be registered for the Discrete Mathematics class.

## Class Notes

I will be using notes written by Professor Bukharovich. They are well-connected with the textbook. I am presently making some small modifications and adaptations. I will notify the class when the next batch is ready.

Lecture 1: Logic of Compound Statements

Lecture 2: Logic of Quantified Statements

Lecture 3: Elementary Number Theory

Lecture 4: Sequences and Mathematical Induction

Lecture 5: Set Theory

Lecture 6: Counting and Probability

Lecture 7: Functions

Lecture 8: Recursion

Lecture 9: Graphs and Trees

## Course Responsibilities

There will be weekly homework assignments. The purpose of them is to get you to live and breathe the mathematics that we will be covering. It will be most helpful to regard them as a fun challenge.You may work with up to ONE partner, in which case you should hand in one copy with both of your names signed to it. Hidden collaborations will be regarded as cheating. We will be discussing the homework problems in class on the day that they are due. Therefore, you must hand them in either at the beginning of class, or email them BEFORE class to the TA. In the absence of a documented medical or family emergency, late homeworks will not be accepted.

There will be one midterm and a final. No programming assignments will be given. Your lowest homework score will be dropped from the grade computation. The course grade will be computed as follows: 30% homework, 25% midterm, 40% final, 5% contribution to group discussions.

This last 5% will be based upon my assessment of the extent of your constructive participation in group discussions, both in class and on the course mailing list. This is a judgement call that I alone will make; it is not a function of the number of bytes posted to the list, etc. The more that you can focus on the content of the class, the more you will get out of it and the better you will do. So, on to the numbers.

## Course Mailing List

You must subscribe to the course mailing list, because this is how we will be sending you timely adminstrative information about the course, and because I am hoping to foster group discussions of our math topics and problems. To subscribe, go to http://www.cs.nyu.edu/mailman/listinfo/g22_2340_001_su03. After you are subscribed, to post to the list -- which is by all means encouraged -- send email to G22_2340_001_su03@cs.nyu.edu.Here are the archives of all the postings to the class mailing list.

Any math-based discussion is pertinent to the list (with the one exception that you should NOT use the list to discuss or solve current homework problems). Good things to post are questions about parts of the material that you are grappling with, e.g., about the meanings of the definitions, or about how the theorems are proven or used. I would especially like for us to put together a collection of problems along with discussions, approaches and solutions to them. Here are some sources of problems that are already at hand: the exercises in the lecture notes, and the exercises in the text (the ones which are not assigned for homework). Once a problem has been "opened up," then let's try to solve it out loud. DO NOT WORRY ABOUT SAYING WRONG THINGS about the problems we are considering. Errors are stepping-stones along the path to the truth of the matter; a "half-baked", partial or mistaken solution contributed by A may well stimulate B to express a valid solution. Also, even if a problem has been solved one way, feel free to contribute solutions that take different approaches. I am hoping to extract highlights from the list and post them to a "course book" section of the web page.

## Group Discussion

Problems related to Chapters 1,2: problems_logic.txtHere are the guidelines for the discussion. You are each assigned one of the problems. Your only responsibility is to think about it, for up to a few days, and then to start the discussion thread which will hopefully lead to its solution. If you solve it, of course, that's also good. If not, then indicate whatever any partial results you may have, approaches that you believe are worthwhile, difficulties that you encountered, etc. I will eventually assemble the solutions into a companion file to the problems file.

To start a thread for your problem, the subject of your email should just be "Problem N". PLEASE do not start a thread for a problem that has been assigned to somebody else. Once a thread has been started, then all are invited to participate. The subject line in this case should just be "Re: Problem N". Also, anyone feel free to start a thread on any of the problems that are not assigned to individuals, or any of the problems which were originally sent to the list, but which I didn't include in the file.

Note: I left out many problems which were fine, in order to obtain a good balance of types of problems, so don't be concerned about whether your submission made its way to the file.

## Homework

Assignment Due Date Solution 1. Homework 1 Tue., May 27 Solution 1 1. Homework 2 Tue., June 3 Solution 2 1. Homework 3 Tue., June 17 Solution 3 1. Homework 4 Tue., June 24 Solution 4 1. Homework 5 Tue., July 15 Solution 5 1. Homework 6 Tue., July 22 Solution 6 1. Homework 7 Tue., July 29 Solution 7 Midterm solutions.

Thanks to Elif for the solutions.