cse547, ams547 Discrete Mathematics (original) (raw)

FINAL includes DISCRETE MATHEMATICS material covered in detail during the last weeks
of classes: LECTURES 15, 16, Discrete Mathematics BASICS, and YES/NO Short Questions as published
in sections below. The CONCRETE MATHEMATICS part of the FINAL covers material
reviewed in LECTURE 17

FINAL consists of 2 PARTS
Part 1 (60pts)
4 CONCRETE MATHEMATICS Problems (Lecture 17) and
1 DISCRETE MATHEMATICS Problem (Lecture 16)
In particular, PROBLEMS will cover
1.Convergence of Infinite Sums (Lecture 10 and Midterm 2)
2.Proof of GENERAL SPECTRUM PARTITION THEOREM (Lecture 11a)
3.Number Theory (Lecture 12)
4. Binomial Coefficients - Polynomial argument (Lecture 13)
5.Finite and Infinite Sets (Lecture16)

FINAL REVIEW Lectures and all MATERIALS from classical DISCRETE MATHEMATICS
needed for FINAL are POSTED

TA: tba

e-mail:
Office Hours:
Office Location: 2126 Old CS Buildin

Course Textbook

CONCRETE MATHEMATICS
A Foundation for Computer Science
Graham, Knuth, Patashnik
Addison- Wesley, Second or Third Edition

Course Description:

The course will cover the Concrete Mathematics as presented in the textbook, including some chosen topics in Number Theory, and
basics of classical Discrete Mathematics, if times permits. Concrete Mathematics is, as defined in the textbooks introduction,
"a controlled manipulation of (some) mathematical formulas using a collection of techniques for solving problems ".

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.

General Course Information

There will be 2 Midterms , and a Finalexamination

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
Midterm 1 - 60pts
Midterm 2 - 60pts
Final - 80 pts FINAL GRADE COMPUTATION
You can earn up to 200 points during the semester. The grade will be determined in the following way: number of earned points divided by 2 = % grade.

The % grade is translated into letter grade in a standard way i.e.

100 - 90 % isA range, 89 - 80 % is B range, 79 - 70 % is C range,69 - 60 % is D range,
and F is below 60%.

See

SYLLABUSfor detailed distribution and explanation of letter grades.

None of the grades will be curved Records of students grades are being kept on

Brightspace Contact TAs for extra information

COURSE CONTENT

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

HOMEWORK PROBLEMS

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

DOWNLOADS

MIDTERM 2 Solutions MIDTERM 1 Solutions Syllabus Syllabus Slides

### LECTURES SLIDES

Lecture 1 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 14: Chapter 5 Part 3 Lecture 15: Discrete Mathematics Basics Lecture 16: REVIEW for FINAL: Discrete Mathematics Lecture 17: REVIEW for FINAL: Concrete Mathematics

### Some Past Tests and Quizzes - to use for PRACTICE

QUIZ 1 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

### Some extra MATERIAL

Chapter 1 Lecture Notes CHAPTER 2 Homeworks Solutions Chapter 2 - Infinite Sums 1 Chapter 2 - Infinite Sums 2

### HOMEWORK PROBLEMS SOLUTIONS: CHAPTER 1

Corrected Solution of Question 19, Chapter 1:

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.

Chapter 1, Problem on pages 11-12 Chapter 1, Problem 2 Chapter 1, Problem 6 Chapter 1, Problem 7 Chapter 1, Problem 8 Chapter 1, Problem 9 Chapter 1, Problems 14, 2 Chapter 1, Problem 16 Old Chapter 1, Problem 16 Generalization Chapter 1, Problems 18, 19 Chapter 1, Problem 20 Chapter 1, Problem 20, solution 2

### HOMEWORK PROBLEMS SOLUTIONS: CHAPTER 2

Chapter 2, Problem 6 Corrected Chapter 2, Problem 11 Chapter 2, Problems 13, 14 Chapter 2, Problem 15 Chapter 2, Problem 19 Chapter 2, Problems 20, 21 Corrected Chapter 2, Problem 23 Chapter 2, Problem 29 full solution Chapter 2, Problem 29 short solution Chapter 2, Problem 29 Chapter 2, Problem 31

### HOMEWORK PROBLEMS SOLUTIONS: CHAPTER 2

Chapter 2, Problems 5,7 Chapter 2, Problem 8 Chapter 2, Problems 9, 10 Chapter 2, Problems 16, 17 Chapter 2, Problems 27,29 Chapter 2, Problem 29 Chapter 2, Problem 29 short solution

### HOMEWORK PROBLEMS SOLUTIONS: CHAPTER 3

Chapter 3, Problem 10, 12 Chapter 3, Problem 11 Chapter 3, Problem 14 Chapter 3, Problem 16 Chapter 3, Problem 17 Chapter 3, Problem 19, 20 Chapter 3, Problem 23 Chapter 3, Problem 28 Chapter 3, Problem 31 Chapter 3, Problem 33, 36 Chapter 3, Problem 35

### HOMEWORK PROBLEMS SOLUTIONS: CHAPTER 4

Chapter 4, Problem 2, 14 Chapter 4, Problem 6 Chapter 4, Problem 14 Chapter 4, Problem 15 Chapter 4, Problem 45

### HOMEWORK PROBLEMS SOLUTIONS: CHAPTER 5

### DISCRETE MATHEMATICS BASICS

Descrete Mathenatics Definitions 1: Sets, Relations, Equivalence Relation Descrete Mathenatics Definitions 2: Posets, Lattices, Boolean Algebras Descrete Mathenatics Definitions 3; Cardinalities of Sets Some Sets Exercises Solutions Descrete Mathematics Short Questions for FINAL YES/NO QUESTIONS

### More PREVIOUS TESTS - to use for PRACTICE

Practice Midterm 1 Midterm 1 Practice Midterm 2 Midterm 2 PRACTICE FINAL

#### OLD LECTURE NOTES (Hand Written)

Lecture 3 Lecture 4 Lecture 5 Lecture 6 Lecture 7 Corrected pg(119-123a) Lecture 7 Lecture 8 Lecture 9 Lecture 10 Lecture 11 Lecture 12 Lecture 13 Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18

### EXTRA SLIDES

Chapter 2 Method 5 Few Practice Midterm 1 Review Problems

SPECTRUM THEOREM PROOF

#### Academic Integrity Statement

Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at Academic Judiciary Website

#### Stony Brook University Syllabus Statement

If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact Disability Support Services at (631) 632-6748 or Disability Support ServicesWebsite They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to the following website: Disabilit Support Services Website