DISCRETE MATHEMATICS

Spring 2018

**ATTENTION!!**

Midterm ROOM CHANGED:

**MIDTERM**: March 23,
Friday - in **JAVITS
102**

**IMPORTANT CHANGE **in Syllabus:

According to University RULES we MUST HAVE **FINAL** examination
during the **FINALS WEEK**

I will give you PRACTICE FINAL (extra credit) om May 4 in class:

**PRACTICE FINAL**
**FRIDAY, ****May 4 in JAVITS 102
**

This is in class, extra credit test designed for your PRACTICE. ONLY one problem will be corrected

FINAL covers problems from all Quizzes, hmks and Tests

PRACTICE MIDTERM: March 9, Friday - in class

TAs office hours POSTED

ALL GRADES are listed on BLACKBOARD

Contact TAs if you need more information or need to talk about grading

I will list names who is correcting which test when you take them

Correcting: Both TAs

New Computer Science Department, room 208;

phone: 632-8458

e-mail: anita@cs.stonybrook.edu

Office Hours: **Wednesday
7:00 pm - 8: 00pm, Friday 3:30pm - 4:30pm, and
by appointment**

Office Hours:

Office Location: 2217 Old CS Building

Office Hours:

Office Location: 2217 Old CS Building

**CONCRETE MATHEMATICS **

** A Foundation for Computer Science **

** Graham, Knuth, Patashnik **

** Addison- Wesley, Second or Third Edition**

We will cover all or parts of Chapters 1-5 of the **Concrete Mathematics **book

**If time allows**** **we
will cover some chosen topics in classical **Discrete Mathematics**

In this case I will provide Lecture Notes and sets of Problems and you can use any Discrete Mathematics book as an extra reading

There will be a Practice Midterm, three One Question Quizzes, a Midterm and a FINAL examination

There also will be assigned sets of
homework problems students must work out and learn for
the tests

The complete solutions to all problems are posted on the course
webpage

The book also contains majority of solutions but they are are not
complete

All tests are **CLOSED NOTES** and **CLOSED
BOOK**

If a student is found using notes or a book during a test, he/she
will receive **AUTOMATICALLY 0pts**
for a given test.

There are 6 sets of Homework problem

Not all of them might be covered.
**None will be collected or graded**.

You will be tested Homework problems dealing with material covered in class.

Some solutions (very short) of homework problems are also in the
text book.

Students are responsible for working out and writing **detailed
solutions** explaining all steps and methods used, as it is
done in our Lecture Notes. We will
cover some of such detailed solutions in class

ALL of them are POSTED on our web page for you to study and learn
how to write them.

GRADES for Quizzes and Tests will depend on the form, attention to details, and carefulness of your written solutions.

GRADING COMPONENTS

3 Quizzes - 25pts each

Practice Midterm - 25pts

Midterm - 100pts

Final - 100pts

FINAL GRADE COMPUTATION You can earn up to 300 points + x extra points = 300 +x points during the semester.

The grade will be determined in the following way: number of earned points divided by 3 = % grade.

The % grade is translated into a

The course will follow the book very closely and in particular we will cover some, or all of the following chapters and subjects

Chapter 1: Recurrent Problems

Chapter 2: Sums

Chapter 3: Integer functions

Chapter 4: Number Theory

Chapter 5: Binomial Coefficients pp 153- 204

Chapter 6: Special numbers pp 243- 264 (reading)

**If time allows **will cover some chosen topics
in Discrete Mathematics
- to be advertised

HOMEWORK 1, Chapter 1: Problems on pages 17 -20.

Write carefully a detailed solution to problems 2, 6, 7, 8, 9, 11,
12, 14, 15, 16, 19, 18, 20,

write details of pp 12-13 discussion of cyclic properties of J(n)
and the false guess that J(n) = n/2,

write details of pp 15-16 binary solutions to generalized
recurrence.

HOMEWORK 2, Chapter 2 part one: Problems on pages 62-63.

Write and present a detailed solution to problems 5 ,6, 7, 8, 9,
10, 11, 13, 14, 15, 16,

HOMEWORK 2, Chapter 2 part two: Problems on pages 63-66.

Write and present a detailed solution to problems 16, 18, 19, 20,
21, 23, 24, 25, 26, 27, 29, 30, 31.

HOMEWORK 3, Chapter 3: Problems on pages 96- 101.

Write and present a detailed solution to problems 10, 11, 12, 14,
16, 17, 19, 20, 23, 28, 31, 33, 35, 36.

HOMEWORK 4, Chapter 4: Problems on pages 144 - 149.

Write and present a detailed solution to problems 2, 6, 14, 15,
45.

HOMEWORK 5, Chapter 5: Problems on pages 230 - 235.

Write and present a detailed solution to problems 2, 4, 6, 7, 8,
15, 16, 17, 18, 35, 43, 45.

HOMEWORK 6, Discrete Mathematics- some problems posted- more to come

This is a** ****preliminary schedule**

The changes and updates, if any, will be advertised in the NEWS section

**Q1: Monday,
February 12**

**PRACTICE ****MIDTERM****:
Friday, March 9**

This is in class test designed for your PRACTICE. ONLY one problem will be corrected

**Spring Break: March
12 - 18**

**MIDTERM: FRIDAY,
March 23 in JAVITS 202
**

Midterm covers problems from Homework sets 1 and 2 (chapters 1 and 2 ) plus content and problems in the Lecture Slides that were covered in class

**Q2:** **Monday, **
**April 9**

**Q3: Monday,**
**April 23**

**PRACTICE FINAL**
**FRIDAY, ****May 4 in JAVITS 202
**

This is in class, extra credit test designed for your PRACTICE. ONLY one problem will be corrected

FINAL covers problems from all Quizzes, hmks and Tests

Is it possible to obtain Zn regions with n bent lines when the angle at each zig is 30 degrees?

Answer: Here we will need 12 such bent lines, when the first overlap occurs. This is because a complete circle is of 360 degrees and each zig is 30 degrees. So, till n=11 we will get Zn regions. On the 12th bent line, it will overlap with one of the previous lines in order to give Zn regions.

Original textbook was an extension of "Mathematical Preliminaries" of Knuth book of ART OF COMPUTER PROGRAMMING. Concrete Mathematics is supposed (and hopefully will) to help you in the art of writing programs, or thinking about them.

The second part of the course will cover some chosen topics in Number Theory and classical Discrete Mathematics, if times permits.