Welcome to the Course Page of

AS/SC/AK/MATH 2320 3.0 D

Discrete Mathematical Structures

Fall 2006


School of Analytic Studies and Information Technology
Atkinson Faculty of Liberal and Professional Studies
York University
4700 Keele Street
Toronto, Ontario  M3J 1P3

Course Organization:

Course Information
Course Schedule
Exams  Information
Links & Other Resources


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.
December 07: Please note that I will not have access to my e-mail during the week of December 10.
December 02: Please note that Test #2 papers will be returned in the class on Monday,
December 04.
November 19: We will write Test #2 during the regular class-time on Monday, November 27.
On the test you will be responsible for all the material covered in class from
Sections 4.3, 4.4, 5.1 - 5.5 and 7.1 - 7.2 of the text-book. Please note that
from Section 7.2 you will be responsible only for the material up to Solving
Linear Homogeneous Recurrence Relations with Constant Coefficients (inclusive).
November 15: Please note that the Final Examination will take place on Tuesday,
December 19 from 19:00 to 22:00 in TEL 0001.
As it was announced in the last class, you may get bonus marks if you
submit written solution to the following question related to Question 2(b)
of  Test #1 by the beginning of the class on Monday, November 20:
For what value of m does the Two-Level Search Algorithm have the
"best" worst-case time complexity?
November 05: Please note that Test #1 papers will be returned in the class on Monday,
November 06.  I am making available  solutions  to the test questions.
October 24: We will write Test #1 during the regular class-time on Monday, October 30.
On the test you will be responsible for all the material covered in class from
Sections 3.1, 3.2, 3.3, 3.4, 3.7 and 4.3 of the text-book. Please note that
from Section 4.3 you will be responsible only for the material up to
Lame's Theorem (inclusive).
October 04: Please note that office hour for Friday, October 13 has been cancelled.
September 11:  Welcome back!
Please read Appendices A-2 and A-3 on the back of the text-book.

To view and/or print PDF files you can download the free Acrobat Reader

Course Information

Course: Session: Fall 2006
  Section: D
  Lectures: M 19:00-21:50, ACW 004
Instructor: Name: Dr. Iulduz Raguimov
  Office: S512 Ross Building
  Phone: 416-736-5250 Ext.66092
  Mailbox: N520 Ross Building
  Office Hours: T 12:00-1:00pm, WF 1:00-2:00pm
  E-mail: raguimov@mathstat.yorku.ca
  Tutorials: M 18:00-18:50, ACW 004
TA: Name: Huilan Li
  E-mail: lihuilan@mathstat.yorku.ca
Grading: Two Class-Tests:  25% each = 50%
  Final Examination: 50%

Course Description: The course covers the algebraic and combinatorial structures that are needed in Computer Science and other disciplines. Consultation with the Departments of Computer Science and of Mathematics, and with the ITEC Program, has led to the following list of topics for emphasis: Big oh notation, complexity of formulae and algorithms, modular arithmetic, recursive definitions, general inductions, counting principles, recurrence relations and methods for solving them, trees and simple graph theory. The emphasis will include examples arising from algorithms and the ability to carry out analysis, problem solving, proofs and calculations which will be required in upper level courses. The course does not require previous knowledge of computer science. A student of mathematics should enjoy this introduction to a variety of mathematical topics, many of which are not covered elsewhere. We will emphasize analysis, problem solving, and proofs. 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, Sixth Edition
by Kenneth H. Rosen
McGraw-Hill, 2006. ISBN 0-07-288088-2
Optional Aids: Student Solution Guide for Discrete Mathematics and Its Applications, Sixth Edition
  by Kenneth H. Rosen
  McGraw-Hill, 2006. ISBN 0-07-310779-4
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.
Course Credit Exclusion: AK/MATH 2442 3.0
Important Dates: September 11: Classes commence
September 21: Last date to enrol in the course without my permission
October 06: Last date to enrol in the course with my permission
November 10: Last date to withdraw from the course without receiving a final grade
December 04: Last day of classes
December 06-20: Examination period.

Course Schedule

(subject to any changes announced in class)




September 11 Introduction, 3.1 Classes begin Monday, September 11.
September 18 3.2-3.3  
September 25 3.4, 3.7  
October 02 No classes. Yom Kippur.
October 09 No classes. Thanksgiving.
October 16 3.7, 4.3  
October 23 4.4, 5.1  
October 30 5.2, Test #1 Test #1 will take place on Monday, October 30.
November 06 5.3-5.5  
November 13 5.5, 7.1  
November 20 7.1-7.2  
November 27 7.2, 7.4, Test #2 Test #2 will take place on Monday, November 27.
November 29 7.4, 9.1-9.3 Make-up classes for October 02 classes.
December 04 9.4-9.5, 10.1-10.2, Review The classes end on Monday, December 04.
December 06-20 Final Examination Tuesday, December 19 from 19:00 to 22:00 in TEL 0001.

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


Homework Problems 

Appendix A-3:   Exercises: 1, 2, 3
Chapter 3: Section 3.1 Exercises: 9, 13, 15, 17, 18, 19, 23, 24, 25, 29, 31, 32, 35, 39, 53
  Section 3.2 Exercises: 1, 2, 9, 12, 17, 18, 21, 24, 25, 28, 32, 51, 53, 60, 63
  Section 3.3 Exercises: 5, 7, 8, 9, 11(a), (b), 17, 19, 27, 28(a), (b)
  Section 3.4 Exercises: 5, 6, 9, 14, 17, 18, 19, 20, 21, 22, 23a
  Section 3.7 Exercises: 2(e), (f), (g), 3, 5, 10-13, 18, 19, 23-29, 36-39, 46, 47
Chapter 4: Section 4.3 Exercises: 1, 2, 17, 22-24, 34, 35, 39, 40
  Section 4.4 Exercises: 4, 6, 7, 10, 11, 16, 17, 20, 21, 22, 23
Chapter 5: Section 5.1 Exercises: 1, 2, 4, 11, 12, 13, 19, 20, 22, 26, 31, 33, 37, 39, 44, 49, 51, 53
  Section 5.2 Exercises: 6, 7, 8, 9, 12, 13, 22, 25, 32, 35, 37, 40
  Section 5.3 Exercises: 11, 13, 15, 17, 25, 33, 34, 35
  Section 5.4 Exercises: 4, 9, 17, 19, 22, 24, 29
  Section 5.5 Exercises: 3, 5, 8, 11, 15, 17, 25, 26, 29, 31, 40, 44, 45
Chapter 7: Section 7.1 Exercises: 5, 7, 9(a), (b), (c), 11, 13, 19, 23, 24, 25, 27, 32, 35, 36, 40
  Section 7.2 Exercises: 1, 3, 7, 8, 13, 17, 23
  Section 7.4 Exercises: 1, 2, 7, 13, 16, 19, 22, 23, 33, 34, 35
Chapter 9: Section 9.1 Exercises: 1, 2, 10, 13, 18, 24, 25, 29
  Section 9.2 Exercises: 1-5, 20-23, 25, 26, 29, 35, 36, 42, 44, 47, 53, 59, 61
  Section 9.3 Exercises: 1, 5, 9, 13, 15-17, 22, 25, 34, 35, 37, 39, 41, 43, 46, 54, 55, 58(a), 65
  Section 9.4 Exercises: 1, 3, 5, 14, 17, 22, 25, 46, 49, 53
  Section 9.5 Exercises: 1, 3, 5, 7, 9, 13, 15, 18, 21, 26, 27, 37, 44
Chapter 10: Section 10.1 Exercises: 2, 5, 7, 9, 11, 15, 16, 17, 19, 21, 27, 28, 30, 34, 37, 45
  Section 10.2 Exercises: 1, 3, 5, 7-9, 11, 13, 15-18.

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 you complete as many problems as possible. Do not memorize them. Rather, learn how to solve problems like them. Use the Solutions Manual only after you have tried the problem. There is nothing like a bit of computation to strengthen understanding in mathematics! Successful students must keep up with 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-book before every class. Next to the classes, working out the answers to the problems 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-book. It is quite practical to work on your own or together in small groups. 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 Class-Tests (75 minutes each written tests held in the lecture period): 25% for Test #1 and 20% for Test #2 (Dates for the tests: Monday, October 30 and Monday, November 27, 2006).
Final Examination
(3-hour exam scheduled by the Registar's Office): 55% of the overall grade, will take place Tuesday, December 19 from 19:00 to 22:00 in TEL 0001.
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 tests in advance of their scheduled dates. No make-ups will be done for the class-tests. Missed tests will be counted as zero, except under extreme circumstances in which case the corresponding percentage of the overall grade will be "forwarded" to the final exam. If you miss a class-test  for medical reasons you must turn in  within one week following the test a copy of the medical report form provided  here after getting it filled in by your doctor. No other type of medical note will be accepted.  However, missing 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 School of Analytic Studies & Information Technology (Mathematics Department, Room 2005, TEL Building, Tel: 416-736-2100, Ext. 33203; Fax: 416-736-5188) in advance that the exam will be missed,
2) the student submits a copy of the medical report form provided  here after getting it filled in by his/her doctor 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
December 15 is NOT a legitimate excuse for absence from a final exam on December 19.

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

Academic Honesty

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


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

2- 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 December 07, 2006