cse547
DISCRETE MATHEMATICS
Fall 2023
GENERAL NEWS:
FINAL December 19, 11:15
pm - 1:44 pm JAVITS 111
NEW MATERIALS on classical DISCRETE
MATHEMATICS POSTED
MIDTERM 2 SOLUTIONS POSTED
Class Meets:
Tuesday, Thursday 2:30 pm
- 3:50 pm
Place:
JAVITS 111
Professor:
Anita Wasilewska
New Computer Science Department, room 208;
phone: 632-8458
e-mail: anita@cs.stonybrook.edu
Office Hours: tba
TA: tba
e-mail:
Office Hours:
Office Location: 2126 OLd CS Building
TA: tba
e-mail:
Office Hours:
Office Location: 2126 Old CS Building
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 textbook very closely
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
General 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 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
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 % is A range,
89 - 80 % is B
range, 79 - 70 % is C range, 69
- 60 % is D range,
and F is below 60%.
See SYLLABUS for
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 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
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
Chapter 5, Problem 2 Solution
Chapter 5, Problem 3 Solution
Chapter 5, Problem 4 Solution
Chapter 5, Problems 4, 6 Solution
Chapter 5, Problem 7 Solution
Chapter 5, Problem 8 Solution
Chapter 5, Problem 8 Solution 2
Chapter 5, Problem 14 Solution
Chapter 5, Problem 15 Solution
Chapter 5, Problem 16, Chapter 4
Problem 15 Solution
Chapter 5, Problems 15, 43 Solution
Chapter 5, Problem 17 Solution
Chapter 5, Problem 18 Solution
Chapter 5, Problems 18, 45 Solution
Chapter 5, Problem 35 Solution
Chapter 5, Problem 74 Solution
DISCRETE MATHEMATICS
Descrete Mathenatics
Definitions 1 : Sets, Relations, Functions, Equievalence
Relation
Descrete Mathenatics Definitions 2:
Posets, Lattices, Boolean Algebras
Descrete Mathenatics Definitions
3; Cardinalities of Sets
Some Exercises in Sets Solutions
Descrete
Math HOMEWORK
HOMEWORK PROBLEMS SOLUTIONS
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