Course Outline
Course Information
Exercises
Assignments
Tests
Exams
Course Outline |
|
EXAM:
* NO notes, NO books, NO blank papers are used during the exam. This is a closed-book exam. Only pens, pencils, erasers, calculators are allowed. Don't forget to bring your Id with your picture.
Lectures: Mondays, Wednesdays and Fridays: 1:30-2:30 pm in CLH C
Instructor: Tran, Kim-Quang, e-mail: trank@pascal.math.yorku.ca
Office hours: Mondays, Wednesdays and Fridays: 3:00-4:00 pm, N 514 Ross Building.
Syllabus: Textbook: " Discrete Mathematics and Its Applications" by Kenneth H.
Rosen (Fourth Edition)
Chapters: Chapter 1: sections 1.1, 1.2, 1.3, 1.4, 1.5, 1.6 and 1.7.
Chapter 2: sections 2.1, 2.3, 2.4, 2.5
Chapter 3: sections 3.1, 3.2 and 3.3.
Chapter 4: sections 4.1, 4.2 and 4.3.
Chapter 6: sections 6.1, 6.3, 6.5 and 6.6.
Note: The Mathlab at S525 Ross Building is available for tutorial help. It normally opens from Monday to Friday with a posted schedule on the doors.
Important Dates: There are 6 homework assignments, 4 tests and a final exam which are scheduled as the following:
- The dates for handing in 6 assignments: #1: Sep. 23; #2: Oct. 7; #3: Oct 16; #4: Oct. 30; #5: Nov.
6 and #6: Nov. 20.
- Tests: #1: Sep. 30; #2: Oct. 23; #3: Nov. 13 and #4: Nov.27.
- Final Exam: Dec 12, 8:30-11:30
After the first two weeks, either an assignment is handed in or a test is given every week.
Note: The last day to withdraw from the course without receiving a grade is FRIDAY, NOVEMBER 8, 2002. The last day of classes is Wednesday, December 4, 2002
Grading Scheme:
20% for 6 assignments; 40% for 4 tests; 40% for a final exam.
Update information will be posted on the course web page.
A new and important information:
From September 30 every assignment will be dropped inside a drop box which is labeled as "Math 1190 3.0 A K.Q. TRAN". This drop box is located on the fifth floor (near the elevator) of the Ross building. No assignment will be handed in the classroom.
Exercises listed below are from the book: "Discrete Mathematics and Its Applications" by Kenneth H Rosen (Fourth Edition).
Students are encouraged to do every question in the following collection of exercises:
Section 6.6: # 1, 3, 5, 9, 11, 17, 25, 23, 37, 45.
Section 6.5: # 3, 5, 7, 11, 15, 17, 31.
Section 6.3: # 11, 13, 14, 15, 17.
Section 6.1: # 3, 4, 5, 7, 9, 11, 13, 14, 15, 17, 21, 29, 30, 31, 35.
Section 4.3: # 5, 7, 11, 13, 15, 19, 21, 23, 25, 26, 29, 31, 33, 35, 37, 39, 41.
Section 4.2: # 3, 5, 7, 9, 11, 13, 15, 19, 23, 25,33, 35
Section 4.1: # 3, 5, 7, 8, 9, 11, 13, 15, 19, 21, 23, 25,29,31, 33, 37, 39, 40, 45
Section 3.3: # 1, 3, 5, 6, 10,11.
Section 3.2: # 3, 4, 5, 7, 8, 9, 10, 12, 13, 16, 17, 20, 21, 23, 25, 29, 34, 43, 47, 53.
Section 3.1: # 1, 3, 7, 9, 11, 13, 14, 15, 16, 17, 20, 21, 23, 25, 27, 29, 33, 41, 45, 49.
Section 2.5: # 1, 2, 3, 5, 6, 7, 11, 12, 15.
Section 2.4: # 1, 2, 3, 4, 6, 8, 9, 10 , 11, 12, 13, 15, 16 ,17.
Section 2.3: # 5, 6, 7, 8, 10, 12, 14, 15, 16,17,18,24, 29, 32,33,35,36,37,38,39.
Section 2.1: # 9, 15, 17.
Section 1.1: #1, 3, 5, 7, 9, 21, 23, 25.
Section 1.2: #1, 3, 5, 7, 13, 15, 17, 19.
Section 1.3: # 5, 6, 7, 22, 23, 25, 35, 45.
Section 1.4: #1, 5, 10, 11, 12, 15, 16, 17, 20, 21, 23.
Section 1.5: #3, 4, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 25, 35, 39, 43.
Section 1.6: #1, 2, 3, 5, 7, 8, 9, 10, 11, 15, 16, 17, 22, 23, 25, 28, 29, 30, 31, 37, 49, 51, 55.
Section 1.7: # 3, 5, 9, 13, 15, 17, 21, 27.
(For fun: Questions # 12, 13, 14 are very interesting , solve them for fun!)
Section 2.1: # 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 25, 26.
Hints: Section 1.7: Table 2, page 76, is useful and used to solve some exercises. Study the sums in this table to see what patterns they are. # 10 (a) Formulate the difference (a_n - a_(n-1)). # 10 (e) Table 2 may be useful of solving this question.
Section 2.1: -- # 6: Solve # 5 to get idea. -- # 8: as the same as # 7. -- # 9: to understand the solution of this question, give some certain integers x and a_1, ...., a_n to see how it works. --# 10: as the same as Algorithm 1. -- #12: solve # 11 to get idea. --# 14: combine algorithm 1 and # 12. -- # 16: let {a_1, a_2, . . ., a_n} be a sequence of letters or blanks. It represents a given sentence. The variables: i (1 =< i =< n), word, maxword, length, maxlength may be used. The form " while .. begin ... end" can be used. -- #18 : solve #17 to get idea.
Assignment # 6: The following questions are for Assignment #6:
Section 3.3: #10
Section 4.1: # 26; #34 (every question will be marked).
Suggestion: Question #26: The word "either" should be omitted. The question means that any license plate of three letters followed by three digits or of four letters followed by two digits is acceptable.
Question #34 of 4.1: A partial function f : A ----> B is an assignment (may not be a function) so that every element a in A maps to either a unique element b in B or to "nothing". For example: f : Z -----> R with f (n) = 1/n . This is not a function because f (0) in not defined (0 maps to "nothing"), but it is a partial function. (More details, see page 69 of the text book)
Assignment #5: The following questions are for Assignment #5:
Section 3.1: #10 (b) and (d); #26 ; #30; #42
Section 3.2: #8; # 28
Assignment # 4: The following are questions for assignment # 4:
Section 2.3: # 26
Section 2.4: # 2 (d) and (f); # 8 (c) ; # 12 (b); # 16.
Assignment #3: The following are 6 questions for assignment 3:
Section 1.6: #20
Section 1.7: #10 e, #12, #26.
Section 2.1: #4, #18.
Assignment #2: The following are the questions for Assignment 2:
Section 1.4: # 10, #24 Section 1.5: #10, # 20; Section 1.6: #10 (b) (d), #14(b) (d) and #38
Assignment #1: The following are the questions for Assignment #1:
Section 1.1: #6 (f); #8 (e), (f); #28 (d), (e); #30 (c), (d);
Section 1.2: #10 (c).
* Solution of test 4: (Note: There is another solution for Q. 2)
(1) White version: The number of haxedecimal numbers of seven digits start with the digit 9 (or end with the digit 0-in the pink version) is 16^6. The number of haxedecimal numbers of 7 digits end with EE (or start with FF as in the pink version) is 16^5. The number of haxedecimal numbers of 7 digits start with 9 and end with EE (or start with FF and end with 0 as in Pink) is 16^4. Using the inclusion-exclusion, we get the number of the required haxedecimal numbers: 16^6 + 16^5 - 16^4.
(2) White and pink versions: There are 4 kinds of committees of 5 members of at least one man and at least one woman: one man and 4 women; 2 men and 3 women; 3 men and 2 women; 4 men and 1 woman. Therefore, the number of ways to select a required committee is C(9,1).C(7,4) + C(9,2).C(7,3) + C(9,3).C(7,2) + C(9,4).C(7,1) - in the white version (and C(10,1).C(6,4) + C(10,2).C(6,3) + C(10,3).C(6,2) + C(10,4).C(6,1) - in the pink version).
Another solution: There are C(16,5) ways to select a committee of 5 members if there are no restrictions; there are C(9,5) [or C(10,5), in "Pink"] ways to select a committee of 5 men only; there are C(7,5) [or C(6,5), in "Pink"] ways to select a committee of 5 women only. Therefore, the number of ways to select a required committee is C(16,5) - C(9,5) - C(7,5) [or C(16,5) - C(10,5) - C(6,5), in "Pink"].
(3) in White or (4) in Pink:
(b) ( x - y )^5 = C(5,0) x^5 + C(5,1) x^4 (-y) + C(5,2) x^3 y^2 + C(5,3) x^2 (-y)^3 + C(5,4) x y^4 + C(5,5) (-y)^5 = x^5 - 5 x^4 y + 10 x^3 y^2 - 10 x^2 y^3 + 5 x y^4 - y^5.
(c) The coefficient of the term x^9 in (2-x)^19 is -2^10 C(19,9) = -94595072.
(4) in White and (3) in Pink:
(a) R_1 is not reflexive since (3,3) is not in R_1; but it is symmetric. It is not antisymmetric since (1,2) and (2,1) are in R_1 but 1 =/= 2. The relation is transitive.
(b) Since every integer a is divisible by itself, then the relation is reflexive. Note that 1 is divisible by 2 but 2 is not divisible by 1, hence the relation is not symmetric. Since 2 | (-2) and (-2) | 2 but 2 =/= -2, the relation is not antisymmetric. It is obvious that the relation is transitive.
* Solution of test 3: ( Mention the solutions of question 4 in the pink version and 5 in white one)
* White version:
(1) (FAC) = 15 x 16^2 + 10 x 16 + 12 = 4012
(2) The inverse of 7 modulo 26 is 15 since 15 x 7 - 4 x 26 = 1. Multiplying both sides of the linear congruence 7x = = 4 (mod 26) by 15, we get 15 x 7x = = 15 x 4 (mod 26) or x = = 8 (mod 26). Therefore, the solution set is S = { 8 + 26n | all n are in Z}.
(3) ( See some similar examples in the book)
(4) (The solution was given in the class)
(5) We use a counterexample to disprove the given statement. Indeed, when n = 2 then ( n^2 - 1 ) = 2^2 - 1= 3, which is prime. Thus, the statement " (n^2 - 1 ) is composite for all n >= 2 " is false.
* Pink version:
(1) (CAF) = 12 x 16^2 + 10 x 16 + 15 = 3247
(2) (The first part is the same as in the white version). .......... the solution set is S = { 19 + 26n | all n are in Z}.
(4) Note that the question can be rewrite as " If n >= 3, then ( n^2 - 1 ) is composite". Let p := " n >= 3 " and q := " ( n^2 - 1) is composite", then we show that the implication p ----> q is true. There are some ways to approach the answer. You can use one of the following:
- Direct proof: Suppose that n >= 3 ( this is p ), then in the factorization ( n^2 - 1) = (n +1 ) ( n - 1) we have (n - 1) >= 2 and (n +1 ) >= 2. Therefore, ( n^2 - 1) is composite ( this is q ).
- Indirect proof: We must show that " not q ----> not p " is true , equivalently, show that " if (n^2 -1) is prime, then n < 3". Since ( n^2 -1 ) = (n +1) ( n -1 ) is prime by the hypothesis, then (n - 1) = 1, hence n = 2, that is n < 3.
- Proof by contradiction: Suppose that n >=3 ( this is p ) and ( n^2 - 1 ) is prime ( this is not q ) we shall find a contradiction. Since ( n^2 - 1 ) = ( n + 1 ) ( n - 1 ) is prime by the hypothesis, then ( n - 1 ) = 1, thus n = 2, which contradicts the hypothesis that n >= 3. Therefore, " (n^2 - 1) is composite for all n >= 3" is true.
- Another proof by contradiction: Suppose that n >= 3 and ( n^2 - 1 ) is prime. Since n >= 3 , then ( n -1 ) and ( n + 1 ) are greater than 2, and thus ( n^2 - 1 ) = ( n + 1 ) ( n - 1 ) is composite. This contradicts the assumption that ( n^2 - 1 ) is prime. Therefore, ( n^2 - 1 ) is composite for all n >= 3.
Comment: To solve this question, direct proof is the best way to be used.
NO notes, NO books, NO blank papers are allowed to be used during the exam. This is a closed-book exam!
The exam will be on December 12 from 8:30 to 11:30 at CLH B, C, D.