cse547, ams547
DISCRETE MATHEMATICS
Spring 2018



GENERAL NEWS:

 POST FINAL OFFICE HOURS
Tuesday, May 22, 1:00 pm  -  4:00 pm

Have a GREAT SUMMER
Thank you for being good students!


FINAL  will be given on  MONDAY, MAY 14, 2:15 pm- 5:00 pm,  JAVITS 102
FINAL  covers problems from all Quizzes, hmks and Tests
FINAL will contain 5 Questions- one from each chapter and one Extra credit question

Q3 SOLUTIONS are POSTED here

Q3 Solutions

Lectures 13, 14 POSTED

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) on May 4

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

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

Class Meets:

Monday,  Friday   1:00 PM - 2:20 PM

Place:

JAVITS 101

Professor:

Anita Wasilewska

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

TA: Lihan Huang

e-mail:   Lihan.Huang@stonybrook.edu
Office Hours:  Wednesday, Friday 10:00am - 11:30am,  and by appointment
Office Location:    2217 Old CS Building

TA: Rahul Verma

e-mail:  rahul.verma@stonybrook.edu
Office Hours: Wednesday, Thursday 1:00pm-2:00pm,  and by appointment
Office Location:   2217 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 Information

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 letter grade in a standard way as described in the course SYLLABUS
None of the grades will be curved
Records of students grades are being kept on BLACKBOARD
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 topics in Discrete Mathematics  -  to be advertised

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

TESTS and QUIZZES SCHEDULE

This is a preliminary schedule
The changes and updates, if any, will be advertised in the NEWS section

Q1:  Monday, February 12

PRACTICE MIDTERMFriday, 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 101
 
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 before the Practice Midterm

Q2: Monday,  April 9

Q3: Friday, April 27

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  will be given during the FINALS WEEK, as scheduled by University
FINAL  covers problems from all Quizzes, hmks and Tests

DOWNLOADS

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 14: REVIEW for FINAL

Some Past Tests and Qizzes

2017 QUIZ 1
2017 PRACTICE MIDTERM
2017 MIDTERM
2017 QUIZ 2
2017 QUIZ 3
2017 QUIZ 4
2017 PROBLEMS  for  Practice Final
2017 SHORT REVIEW FOR FINAL

General Relaxed Radix Representation
Old Review for Final Slides
Writing Mathematical Texts

Older MATERIAL

Chapter 1 Lecture Notes

CHAPTER 2 Homeworks Solutions

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 DEFINITIONS: HOMEWORK 4 PROBLEMS

Descrete Mathenatics Definitions 1
Descrete Mathenatics Definitions 2
Descrete Mathenatics Definitions 3
Descrete Mathenatics Definitions 3

HOMEWORK 4 PROBLEMS
HOMEWORK 4 PROBLEMS SOLUTIONS

PREVIOUS TESTS TO STUDY FOR FINAL


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 9a (Chapter 2, Infinite Sums 1)
Lecture 9a (Chapter 2, Infinite Sums 1 SLIDES)
Lecture 9b (Chapter 2, Infinite Sums 2)
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: Disability Support Services Website

General Course Description:

The course will have two parts: Concrete Mathematics as presented in the textbook and Concrete Mathematics is "a controlled manipulation of (some) mathematical formulas using a collection of techniques for solving problems "(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, 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.