Welcome to the Course Page of

AS/SC/AK/MATH 2320 3.0 M

Discrete Mathematical Structures

Winter 2005

 

Department of Mathematics and Statistics
York University
4700 Keele Street
Toronto, Ontario  M3J 1P3

Course Organization:

Announcements
Course Information
Course Schedule
Homework
Exams  Information
Links & Other Resources

Announcements

This area will contain announcements and solutions to exams. Announcements made in class will be posted here in reverse chronological order and will not be repeated in class. Please take a minute to read the announcements carefully, as they often get updated. You may need to Reload/Refresh this page.
 
May 12: Deferred Final Examination will take place on Tuesday, May 17 from
  10:00 to 13:00 in N501 Ross.
May 07: Please click  here  to see  your final exam mark and unofficial letter grade
  for the course. Also, please note that your official grade will be sent to you
  by the Registrar's Office upon the approval by the Senate.
                HAVE A NICE SUMMER!
April 26: Please note that I will be holding an office hour on Wednesday, April 27
  from 2:00 to 3:00pm. Also, please note that the Final Examination
  will take place in CLH K from 19:00 to 22:00. Do not forget to take
  with you your sessional card and valid photo ID.
April 11: Please note that there will be a two hour tutorial session on Friday, April 15
  from 11:00 to 1:00pm in N501 Ross.
April 09: I am making available the  grades  for the quizzes and term tests.
  Please let me know by Friday, April 15th if there is any discrepancy.
April 07: Please note that the next week I will have office hours on Monday, April 11  
  from 1:00 to 2:30pm.
April 05: Please note that the next office hour this week I will have on Thursday, 
  April 07 from 3:00 to 4:00pm.
April 03: Please note that Test #2 papers will be returned and we will go over the
  solutions to the test questions during the class on Monday, April 04.
  I am making available  solutions  to the test questions in PDF format.
March 30: Please note that the office hours on Friday, April 01 will be held from
  12:00 to 1:00pm.
March 28: Please note that I will bring the course evaluation forms to the class on
  Wednesday, March 30. It is the time for you to be the judge. Please come
  and fill out the evaluation forms.
  Also, please note that during the Examination Period the MathLab will be open
  from 11:00am to 3:00pm on the following days: April 05, April 06, April 07,
  April 08, April 11, April 13, April 15, April 21 and April 25.
March 23: Please note that there will be an additional tutorial on Thursday, March 24
  at 12:30pm in N501 Ross.
March 19: Please note that we will write Test #2 during the regular class time on
  Monday, March 28. On the test you are responsible for the material from
  Sections 3.2 - 3.5 and 4.1 - 4.5 of the text covered in class.
March 17: Quiz #2 papers will be returned at the end of the class on Friday, March 18.
  I am making available  solutions  to the quiz questions in PDF format.
March 08: Please note that Quiz #2 will take place during the regular class time on Friday
  March 11. On the quiz you are responsible for the material from Sections 3.2,
  3.3, 3.4 and 3.5 of the text.
February 28: If you are interested in bonus marks in the course, you have to answer the following
  question, which relates to Question 3b of  Term Test #1:
  For what value of m does Two Level Search Algorithm have the "best" worst-case
  time complexity?
February 26: Test #1 papers will be returned at the end of the class on Monday, February 28.
  I am making available  solutions  to the test questions in PDF format.
February 08: Please note that we will write Test #1 during the regular class time on
  Friday, February 11th. On the test you are responsible for the material from
  Sections 1.8, 2.1, 2.2, 2.3, 2.4, 2.5 and 2.6 of the text covered in class.
  Click  to view a  Sample Test  with solutions in PDF format.
January 31: Quiz #1 papers will be returned at the end of the class today.
January 24: I am making available  solutions  to Quiz #1 in PDF format.
January 15: Please note that Quiz #1 will take place during the regular class time on
Wednesday, January 19th. On the quiz you are responsible for the material from
  Sections 1.8, 2.1 and 2.2 of the text.  I am making available  Sample Quiz #1
  with solutions in PDF format.
  Tutorials for the course led by TA, Rafael Molina-Rincon will begin on Monday,
  January 17th. Click  Course Information  for the locations and schedule.
January 12: Please note that the office hours will be MWF from 3:00 to 4:00pm.
  Also, note that the first day of the MathLab is Wednesday, January 12th.
  Hours of Operation: 10:30am - 3:30pm (Monday-Friday).
 January 03:  Happy New Year!
To view and/or print PDF files you can download the free Acrobat Reader

Course Information

Course: Session: 2005 Winter
  Section: M
  Lectures: MWF 1:30 - 2:20pm, CB 121
Instructor: Name: Dr. Iulduz Raguimov
  Office: S512 Ross Building
  Phone: 416-736-5250 Ext.66092
  Mailbox: N520 Ross Building
  Office Hours: MWF 3:00-4:00pm, also by appointment
  E-mail: raguimov@mathstat.yorku.ca
  Tutorials: M 2:30-3:20pm, N501 Ross
TA: Name: Rafael Molina-Rincon
  Office: N511 Ross Building
  Phone: 416-736-5250 Ext.40617
  E-mail: gmolina@mathstat.yorku.ca
Grading: Two Quizzes:  7.5% each = 15%
  Two Class Tests:  20% each = 40%
  Final Examination: 45%

Course Description: The course covers the algebraic and combinatorial structures that are needed in Computer Science and other disciplines. We begin with a review of functions, then discuss growth of functions, algorithms and complexity. Other topics include elementary number theory, combinatorics, recursive definitions and recurrence relations, graph and tree structures. This course emphasizes analysis, problem solving and proofs. For a more detailed list of topics with references to the textbook, please see Course Schedule.

Text-book: Discrete Mathematics and Its Applications, Fifth Edition
by Kenneth H. Rosen
McGraw-Hill, 2003. ISBN 0-07-242434-6
Optional Aids: Student Solution Guide for Discrete Mathematics and Its Applications, Fifth Edition
  by Kenneth H. Rosen
  McGraw-Hill, 2003. ISBN 0-07-247477-7
Course Prerequisite: AS/SC/AK/MATH 1090 3.0, or AS/SC/AK/MATH 1190 3.0, or AK/MATH 2441 3.0,
or any 2000-level MATH course without the second digit 5. Student who have not taken 
  AS/SC/AK/MATH 2090 3.0 or AS/SC/AK/MATH 1190 are advised to review set theory,
  functions, relations and induction proofs.
Degree-credit AK/MATH 2442 3.0
Exclusions:  
   
Important Dates: January 3: Classes commence
January 14: Last date to enrol in the course without my permission
January 28: Last date to enrol in the course with my permission
February 14-18: Reading Week (No classes)
March 4: Last date to withdraw from the course without receiving a final grade
March 25: Good Friday (University is closed)
April 4: Last day of classes
April 6-29: Examination period.

Course Schedule

(subject to any changes announced in class)

Week

Sections of the text

Comments
January 3-7 Introduction, 1.8, 2.1 Lectures begin Monday, January 03
January 10-14 2.2, 2.3  
January 17-21 2.4, 2.5, Quiz #1 Quiz #1 will take place on Wednesday, January 19
January 24-28 2.5, 2.6  
Jan 31-Feb 4 2.6, 3.2  
February 07-11  3.2, 3.3, Test #1 Test #1 will take place on Friday, February 11
February  14-18   Reading Week No classes
February  21-25   3.3, 3.4  
Feb 28-March 4 3.5, 4.1  
March 7-11  4.2, 4.3, Quiz #2 Quiz #2 will take place on Friday, March 11
March 14-18  4.4, 4.5  
March 21-25 6.1, 6.2 No classes will be on Friday, March 25
March 28-Apr 01 6.4, Test #2 Test #2 will take place on Monday, March 28.
April 4 Review The classes end on Monday, April 4
April 6-29 Final Examination  Wednesday, April 27th from 19:00 to 22:00 in CLH K.

Note: The course will not cover all the sections of each chapter from the text-book.


Homework  

Homework Problems 

Chapter 1: Section 1.8 Exercises: 4, 7, 9-13, 16, 25, 26, 27, 32, 33, 36, 39, 59, 63, 65
Chapter 2: Section 2.1 Exercises: 9, 13, 15, 17, 18, 19, 23, 24, 25, 29, 31, 35, 39, 53
  Section 2.2 Exercises: 1, 2, 9, 12, 17, 18, 21, 24, 25, 28, 32, 51, 53, 60
  Section 2.3 Exercises: 5, 7, 8, 9, 11(a), (b), 17, 19, 27, 28(a), (b)
  Section 2.4 Exercises: 5, 6, 9, 11, 13, 14, 23, 25, 29, 34, 37, 38, 39, 40, 42, 43, 44, 45, 55
  Section 2.5 Exercises: 19, 21, 22, 23, 24, 26, 27
  Section 2.6 Exercises: 1, 3, 5, 6, 10, 11, 12, 19, 25, 27, 29, 37, 38, 59
Chapter 3: Section 3.2 Exercises: 3, 14, 17, 20, 21, 27, 31, 32, 35, 37, 39, 41, 42, 45
  Section 3.3 Exercises: 2, 5, 13, 15, 18, 21, 22, 25, 45, 50, 51, 52, 53, 54, 63
  Section 3.4 Exercises: 1, 2, 34, 35, 39, 40
  Section 3.5 Exercises: 4, 6, 7, 16, 17, 20, 21, 22, 23.
Chapter 4: Section 4.1 Exercises: 1, 3, 10, 11, 12, 18, 21, 26, 31, 33, 37, 39, 44, 49, 51, 53
  Section 4.2 Exercises: 6, 7, 8, 9, 12, 13, 22, 25, 32, 35, 37, 40
  Section 4.3 Exercises: 9, 13, 15, 17, 25, 33, 34, 35
  Section 4.4 Exercises: 4, 9, 17, 19, 22, 24, 29
  Section 4.5 Exercises:  3, 5, 9, 11, 15, 17, 25, 26, 29, 31, 40, 44, 45
Chapter 6: Section 6.1 Exercises: 5, 7, 9(a), (b), (c), 11, 13, 19, 23, 24, 25, 27, 32, 35, 36, 40
  Section 6.2 Exercises: 1, 3, 7, 8, 13, 17, 23
  Section 6.4 Exercises: 1, 2, 7, 13, 16, 19, 22, 23, 33, 34, 35

The homework problems are posted but solutions will not be collected for grading. While these will not directly affect your grade, it is extremely important that students complete as many problems as possible. Since mathematics is a subject where mastery of previous material is essential in order to understand and deal with current topics, successful students must keep up with the homework and seek help for points they do not understand as soon as possible. Do not fall behind! It is recommended to read the relevant sections of the text before every class. Next to the classes, working out the answers to the problems (the back of the textbook contains the answers to all the odd numbered exercises) is the most important preparation for the tests and exam that will contain for the most part but not exclusively, questions very similar to those from the text. Each student should do at least three hours of independent study for every lecture hour. The amount you learn in this course and the grade you receive will be proportional to the amount of time you spend working on problems.


Exams Information

Lecture/Exam Rules:

Please turn off all cell phones and pagers before entering the lecture hall. For quizzes, tests and exam cell phones, digital dictionaries, palms, pagers or other electronic devices are not allowed. All such devices as well as all books, papers, knapsacks, and briefcases must be left at the front of the lecture hall. Anyone caught with electronic devices will be charged with Academic Dishonesty (see the next page). The only items you may have at your seat are pens, pencils, student ID, a non-graphing, non-programmable calculator, purses and coats.
You are responsible for all material covered in lectures.
Note: Photo identification and signing-in are required at all
quizzes, tests and exam.

Final Grade:

The composition of the final grade is as follows:
Two Quizzes (20 minutes each written Quizzes held in the lecture period), 7.5% each (Dates for the Quizzes: Wednesday, January 19 and Friday March 11, 2005).
Two Class Tests (50 minutes each written tests held in the lecture period), 20% each (Dates for the tests: Friday, February 11 and Monday, March 28, 2005).
Final Examination
(3-hour exam), 45% of the overall grade, will take place on Wednesday, April 27, 2005.
All exam marks you receive should be interpreted as raw scores and not "percentages". The statistics of scores will be announced for all exams. Students have seven days from the date of the return of an exam paper to appeal their marks. Cut-off for converting midterm scores into letter grades will be announced prior to the drop date.

Make-up Policy:

No permission will be given to a student to write quizzes or tests  in advance of their scheduled dates. No make-ups will be done for the quizzes or tests.  Missed tests will be counted as zero, except under extreme circumstances. If you miss a class test or quiz and provide a medical certificate showing a physical incapability of writing it, the corresponding percentage of the final grade will be "forwarded" to the final exam. However, missing class tests is extremely dangerous and not recommended. As experience has shown, students who miss class tests because of some 'mysterious illnesses' will usually average 30% on the final exam. A student who misses the Final Examination will be allowed to write a make up exam only if both of the following conditions are met:
   
1) the student notifies me (raguimov@mathstat.yorku.ca) or the Department of   Mathematics and Statistics (Undergraduate Office, N502/503 Ross Building, 416-736-2100 Ext. 55902 or 33969) in advance that the exam will be missed,
   
2) the student provides a medical certificate showing a physical incapability of writing the exam within one week following the exam.
Students who miss the Final Examination and do not meet both conditions will receive a grade of F.
It is student's responsibility to fill out and submit the Deferred Standing Agreement Form.
Note: Do not make vacation/job plan until the final exam date is known: having a plane ticket for Hawaii or Las Vegas on
April 15 is NOT a legitimate excuse for absence from a final exam on April 20.


Religious Observance:

 York University is committed to respecting the religious beliefs and practices of all members of the community and making accommodations for observances of special significance to adherents. If any of the dates specified in the course schedule for in-class tests pose such a conflict, students should contact me (raguimov@mathstat.yorku.ca) by the end of the second week of classes. Please note that if the final exam date poses a conflict, students must complete the Examination Accommodation Form, which can be obtained from the Registrarís Office

Academic Honesty

Conduct that violates the ethical or legal standards of the university community or of oneís programme or specialization may result in serious consequences. Refer to the Senate Policy on  Academic Honesty

Communication 

Individual questions can be discussed by e-mail, or in person after class, or during office hours. Please send all e-mail notes as plain text within the body of the message. Do not send attachments nor HTML-formatted mail. Also, if the name of your account is an alias, I will not know who the mail is from unless you sign it; it also risks being accidentally discarded as junk mail. The course web page will be up-dated regularly to include important announcements made in class, such as the material to be covered on the tests. E-mail notes requesting such information contained on the web page will be answered the last.


Links and Other Resources

1-   McGraw-Hill Online Learning Centre

2-  York Undergraduate Math Program

3-  Study Groups

4- The Great Internet Mersenne Prime Search  www.mersenne.org


Questions and comments regarding this Web page please send to raguimov@mathstat.yorku.ca

© 2005, All Rights Reserved, York University & Iouldouz S. Raguimov

Last modified May 12, 2005