cse547, ams547

DISCRETE MATHEMATICS

Spring 2017



GENERAL NEWS:

  FINAL scheduled for MAY 11,  8:30- 11:00pm, in our classroom

Q3 Monday, April 24 in class
It covers Lecture 12 and relevant part of Chapter 4 and relevant  Hmk Problems
Proofs of Euclid Algorithm and Main Factorization Theorem

Q2 Monday, April 10
Q2 covers Casino Problem  with detailed explanations

  TESTS schedule and structure CHANGES

  • There will be extra credit QUIZ  on Wednesday, March 8
    The 
    QUIZ will cover material from Lectures 7 and 8- definitions, proofs, examples

    Practice Midterm - will be a TAKE HOME test- not in class test.
    I will post the Practice Midterm on Thursday, March 9
    No change for MIDTERM!
    MIDTERM: Monday, March 20, in class

    Class Meets:

    Monday, Wednesday, 5:30 PM - 6:50 PM

    Place:

    Old CS, room 2120

    Professor:

    Anita Wasilewska

    New Computer Science Department, room 208;
    phone: 632-8458
    e-mail: anita@cs.stonybrook.edu
    Office Hours:   Monday, Wednesday 12:30 pm - 2: 00pm, and by appointment

    TA: Hieu Le

    e-mail: hle@cs.stonybrook.edu
    Office Hours: Wednesday, 9:30 -11:30 am
    Office Location: ROOM 2217, Old Computer Science Blg
    TA webpage for the class: www3.cs.stonybrook.edu/~cse547

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

    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

      CONCRETE MATHEMATICS
     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)

      DISCRETE MATHEMATICS
     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 13

    PRACTICE MIDTERM: TAKE HOME test

    Use it as your own PRACTICE- write carefully all solutions. ONLY One Problem will be corrected

    Spring Break: March 13 - 19

    MIDTERM: Monday, March 20, in class
    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 10

    Q3: Monday, April 24

    LAST DAY OF CLASSES - May 3

    FINAL will be given during the Finals week, May 9 - 17, exact time and place t.b.a

    Final covers problems from all Quizzes, hmks and Tests

    DOWNLOADS


    Syllabus
    Syllabus Slides

    PRACTICE MIDTERM

    General Relaxed Radix Representation

    Old Review for Final Slides
    Writing Mathematical Texts

    Part ONE: LECTURES SLIDES

    Lecture 1
    Lecture 2
    Lecture 3
    Lecture 4
    Lecture 4a: Solution to 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
    Last Year Material from Ch2 and Ch3, Ch4 needed for Midterm 2 and FINAL

    Part TWO LECTURES SLIDES

    To be published soon

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

    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.