1428 CS Building; 632-8458
e-mail: anita@cs.sunysb.edu
Office Hours: Tuesday, Thursday, 3:00pm - 4:00 pm, and by appointment
e-mail: junyang@cs.stonybrook.edu
Office Hours: 1:00PM - 2:00PM on Monday and Wednesday and by appointment
Office Location: Room 2110, CS department.
CONCRETE MATHEMATICS
A Foundation for Computer Science
Graham, Knuth, Patashnik
Addison- Wesley
There will be TWO MIDTERMS 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 will be three, or four Homework sets. NONE will
be collected or graded. Solutions (very short) of all 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 some of such detailed solutions in
class and post ALL of them on our web page for you to study and learn how
to write them.
Your GRADES on the tests will depend on the form, attention to details, and
carefulness of your written solutions.
The course will follow the book very closely and in
particular we will cover some , or all of
the following chapters and
subjects.
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)
Part Two: Classical Discrete Mathematics - Lecture Notes and Problems (HMK4) posted.
HOMEWORK PROBLEMS
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 1, 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.
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 2, 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 3, Chapter 4: Problems on pages 144 - 149.
Write and present a detailed solution to problems 2, 6, 14, 15, 45.
HOMEWORK 3, 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 4, Discrete Mathematics Lecture - problems posted
TESTS SCHEDULE
Practice Midterm 1: Tuesday, March 6, in class
Midterm 1: Tuesday, March 13, in class
Spring Break: April 2 - April 8
Midterm 1 covers problems from homeworks 1 and 2 (chapter 1 and 2 )
plus content and problems in the Lecture Notes.
All solutions are posted on the course web page.
Midterm 2: Tuesday, April 24, in class.
Midterm 2 covers ch3 and ch4 homework problems PLUS Lectures proofs and examples.
LAST DAY OF CLASSES- MAY 5
FINAL: Finals week May 8-15, exact time and place t.b.a.
Final covers problems from homework 3, 4
and some problems from Hmks 1, 2.
DOWNLOADS
Syllabus
Writing Mathematical Texts
STUDENTS INPUT
Chapter 1 Lecture Notes
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
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 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