cse547, ams547

DISCTRETE MATHEMATICS

Spring 2009


GENERAL NEWS:

  • FINAL is all inclusive. It will cover HW1, HW2, HW3 (problems with solution published on the Web) PLUS Lecture Notes, Book problems and Materials that we covered in the class.
  • Find the FINAL's Date and Place in the NEW section FINAL EXAM DATE AND PLACE.
    Which is DATE:5/14/2009 TIME:8:00PM-10:30PM PLACE:Light Eng 102
  • SUBMITING POWERPOINTS: Do not send PDFs. Try to send original files latex or ppt documents (for ppt preferably in windows 2003 format, [windows 2007 has option to save it as 2003 format])
    Put your slide in a folder and name the folder like: "Name1 StudentId1 Name2 StudentId2" Then zip (not rar) it and send it to TA.
  • Check the section "SLIDES AND UNSOLVED PROBLEMS ASSIGNMENT" to see if TA has received it or not.
  • PRESENTATION is on the LAST DAY of CLASSES! BUT ONLY THE NEW PROBLEMS! not LECTURES!
  • SUBMIT the presentation to TA before your final.
  • Students who are solving problems for extra credit can solve on PAPER and show Professor before s/he makes slides.
  • There is a new section "SLIDES AND UNSOLVED PROBLEMS ASSIGNMENT" at the bottom of this page. That contains the assignment of the presentations and unsolved problems. Students are requested to check their assignment.
    Professor needs all slides (lecture slide powerpoint or unsolved problem powerpoint) by, or anytime before the FINAL EXAM DATE. NO extensions! She will give final grades within 2 days of the Final.
  • REGARDING UNSOLVED PROBLEMS, BY "UNSOLVED" WE MEANT THOSE WHICH HAS NO SOLUTIONS EITHER IN HOMEWORKS SOLUTIONS OR CLASS LECTURES.
  • Previously students sent their choices about lecture slides or unsolved problems regarding extra points. Students are now asked to email TA their choices for particular lecture slide or particular unsolved problem, ASAP. INCLUDE YOUR NAME AND STUDENT ID IN YOUR MAIL!!!! Once all the requests are received every one will be assigned their task. (Those who sent their requests earlier dont need to send it again, TA has your records)


    • Time:

    6:50pm - 8:10 pm

    Place:

    Light Eng. Lab. 102

    Professor:

    Anita Wasilewska

    1428 CS Building; 632-8458
    e-mail: anita@cs.sunysb.edu
    Office Hours: Tuesday, Thursday, 2:30pm - 3:30 pm, and by appointment

    Teaching Assistant:

    Faisal Ahmed

    e-mail: faiahmedATcsDOTsunysbDOTedu
    Office Hours: Tuesday, Thursday, 1:00pm - 2:00pm
    Office Location: Applied Logic Lab, Computer Science Building.

    Course Texbook

    CONCRETE MATHEMATICS
    A Foundation for Computer Science
    Graham, Knuth, Patashnik
    Addison- Wesley

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

    General Course Information

    There will be TWO MIDTERMS and a FINAL examination. There also will be assigned sets of homework problems students must work out the solutions and some Problems Presentations for Extra Credit.

    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 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. I 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 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.
    EXTRA CREDIT
    Students can earn up to 25 in extra credit points by solving and making a power point presentation of 2 problems not covered in our homeworks, OR by making a power point/ LATEX presentation of a part of my lecture notes.
    Lecture Notes Slides OR Unsolved Problems can be done in groups of 2 students (both students receive an equal grade, but must show that they both participated in the solution and making the presentation). Please contact our course TA to "sign in" for what you want to do. We will distribute the work when we have a full list.

    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 - if time permits

    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, 11, 13, 14.

    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.

    TESTS SCHEDULE

    Practice Midterm 1: Thursday, February 26, in class

    Midterm 1: Thursday, March 2, in class
    Midterm 1 covers problems from homework 1 (all solutions posted on the course web page), plus problems in the Lecture Notes

    Spring Break: April 6 -10

    Midterm 2: Thursday, April 23, in class
    Midterm 2 covers rest of ch2, ch3 and ch4 homework problems PLUS Lectures proofs and examples.

    Extra Credit Presentations: May 5, 8

    FINAL: Finals week May 13 -19, exact time and place t.b.a.
    Final covers problems from homework 3 (all solutions posted on the course web page), and problems from Hmks 1,2.

    DOWNLOADS

    Syllabus
    Writing Mathematical Texts

    HOMEWORK PROBLEMS SOLUTIONS: CHAPTER 1

    Corrected Solution of Question 19, Chapter 1, provided by Priya Sehgal:

    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 FOR Midterm 1


    Chapter 2, Problem 6
    Chapter 2, Problem 11
    Chapter 2, Problems 13, 14
    Chapter 2, Problem 15
    Chapter 2, Problem 19
    Chapter 2, Problems 20, 21
    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 FOR MIDTERM 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, 14
    Chapter 5, Problem 3
    Chapter 5, Problem 4, 6
    Chapter 5, Problem 4
    Chapter 5, Problem 7
    Chapter 5, Problem 15, 43
    Chapter 5, Problem 18, 45
    Chapter 5, Problem 35

    LECTURE NOTES


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

    SLIDES AND UNSOLVED PROBLEMS ASSIGNMENT

    Lecture Slides Assignment
    Problems Assignment Schedule

    USEFUL PROPERTIES

    Useful Properties

    FINAL EXAM DATE AND PLACE

    Date & Place