~rbharpaz

Office 5316N

Telephone 718-9515527

Meeting times Thursday 6:20-9:00 pm, room 234NE

Office hours Before and after class, or by setting up an appointment in advance

Textbooks Required

Discrete Mathematics and its Applications, fifth edition,

by Kenneth H. Rosen, McGraw-Hill

Recommended Texts

Schaum's Outline of Discrete Mathematics, by Seymor Lipschutz

Attendance

Although class attendance is not mandatory, you are responsible for whatever is done in class. While our textbooks cover most basic concepts, class is your only source for the specifics that will allow you to learn the material, and pass the class. Make sure you get the notes and homework if you miss a class. To encourage you to prepare and come to class, I will be taking class participating into account towards your final grade.

Homework

In order to succeed in any mathematics class you must practice. I will be giving homework from our text book every time we finish a section. I will not be collecting and grading your homework, but rather go over selected questions at the beginning of every class. Without doing the homework you are less likely to succeed in this class.

Grading Policy

Your grade will be determined by your performance on two midterm exams, a final exam, and class participation.

These will contribute to your grad as follows:

Midterm #1 30%

Midterm #2 30%

Final exam 35 %

Class participation 5%

Course Description

What is discrete mathematics?

Different people will give different answers to this question, however it is widely accepted that discrete mathematics is mathematics that deals with discrete objects and structures as apposed to continuous mathematics (i.e. calculus) that deals with continuous objects. Discrete objects are objects which are separated from (not connected to/distinct from) each other, e.g. integers, rational numbers, cars, houses, people etc. are all discrete objects. On the other hand real numbers which include irrational as well as rational numbers are not discrete. This is because between any two different real numbers there is another real number different from either of them. So they are packed without any gaps and can not be separated from their immediate neighbors. In that sense they are not discrete. Thus, discrete mathematics can be considered the mathematics of everything that is not calculus. Many real-world problems are inherently discrete, for example how many routes exist from point A to point B in a computer network? How much execution time is required to sort a list of integers in increasing order? What is the probability of winning a lottery? What is the shortest path from point A to point B in a computer network? etc. The rise in popularity of discrete mathematics courses coincides with the rise of the computers, which is why it is often referred to as the mathematics of computers. The study of discrete mathematics focuses on discrete structures and mathematical tools which are used to represent, analyze, and manipulate discrete objects. These include sets, functions, relations, matrices, graphs, discrete probability, logic, recurrence relations, mathematical induction, Boolean algebra, linear programming, and number theory.

Aims

The aim of this course is to introduce you to some of the basic ideas and tools of discrete mathematics. The course is designed to: enable you to obtain general knowledge about the area of discrete mathematics, and more in-depth knowledge of selected topics, and to understand mathematical reasoning and methods to read, comprehend and construct mathematical arguments.

Course Outline

The following is a tentative schedule of lectures. We might deviate from it depending on the circumstances.

Week Topic Book Chapters

1 Logic/Propositional Calculus 1.1, 1.2

2 Proof Techniques Part 1 1.5

3 Introduction to Set Theory 1.6,1.7

4 Relations 7.1, 7.3

5 Relations 7.4, 7.5

6 Functions 1.8

7 Counting 4.1, 4.3

8 Counting 4.4,4.5

9 Discrete Probability 5.1, 5.2, 5.3

10 Graphs 8.1, 8.2

11 Graphs and Trees 8.3, 9.1

12 Proof Techniques Part 2 3.3, 4.2

13 Recursion 3.4

14 Recurrence Relations 6.1, 6.2

15 Algorithms 2.1, 2.4, 2.5

Some of the following topics might also be covered if time permits.

More on Graphs, Introduction to Linear Algebra, Complexity of Algorithms,

Number Theory, Boolean Algebra, Formal Languages.