DISCRETE MATHEMATICS

Fall 2023

FINAL December 19, 11:15
pm - 1:44 pm JAVITS 111

NEW MATERIALS on classical DISCRETE
MATHEMATICS POSTED

MIDTERM 2 SOLUTIONS POSTED

New Computer Science Department, room 208;

phone: 632-8458

e-mail: anita@cs.stonybrook.edu

Office Hours: **tba**

Office Hours:

Office Location: 2126 OLd CS Building

Office Hours:

Office Location: 2126 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

basics of classical Discrete Mathematics, if times permits.

Concrete Mathematics is, as defined in the textbooks introduction,

We will cover some or all material from book chapters 1- 5.

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, and thinking about their correctness.

There will be a TWO Midterms and a FINAL examination

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

**None will be collected or graded**. You may be tested
only on Homework problems dealing with material
covered in class.

Some solutions (very short) of homework problems are 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 a lot of such detailed solutions in ** class.**

Moreover, all of the Homeworks SOLUTIONS you may need to know for
**tests **are POSTED on
the page below.

You have to study them and to learn how to write
proper, detailed solution to problems on your**
tests**.

TESTS GRADES will depend on
the form, attention to details, and carefulness of your **solutions writing**.

GRADING COMPONENTS

FINAL GRADE COMPUTATION

You can earn up to

The

100 - 90 % is

and

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
classical topics in Discrete Mathematics
- to be advertised

None of the Homeworks will be collected.

ALL of the Homeworks SOLUTIONS **you
need
are posted below
**

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

MIDTERM 1 Solutions

Syllabus

Syllabus Slides

Lecture 2

Lecture 3

Lecture 4

Lecture 4a: Chapter 1, Problem 20

Lecture 5

Lecture 6

Lecture 7

Lecture 8

Lecture 8a

Lecture 9a

Lecture 9b

Lecture 10

Lecture 11

Lecture 11a

Lecture 12

Lecture 13: Chapter 5 Part 1

Lecture 13a: Chapter 5 Part 2

Lecture 13b: Chapter 5 Part 3

Lecture 14: REVIEW 1 for FINAL - Concrete Mathematics

Lecture 15: Discrete Mathematics Basics 1

Lecture 16: Discrete Mathematics Basics 2

Lecture 17: REVIEW 2 for FINAL - Discrete Mathematics

PRACTICE MIDTERM

MIDTERM

QUIZ 2

QUIZ 3

QUIZ 4

PROBLEMS for Practice Final

SHORT REVIEW FOR FINAL

General Relaxed Radix Representation

Old Review for Final Slides

Writing Mathematical Texts

CHAPTER 2 Homeworks Solutions

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.