MTH U230 - Discrete Mathematics

Fall 2003

Course Information


Course:	MTH U230, Discrete Mathematics
Time and place:	MWTh at 10:30-11:35 AM, in 100 CA
Textbook:	K. Rosen, Discrete Mathematics and Its Applications, Fifth Edition. WCB/McGraw-Hill, 2003
Instructor:	Professor Andrei Zelevinsky
Office and phone:	431 LA, x5648
Email:	andrei@neu.edu
Office hours:	Mon., Wed. 11:45 - 12:50 PM, or by appointment

Course Description

The course provides the discrete portion of the mathematical background needed by students in electrical and computer engineering. Here is an (approximate) list of topics we are planning to cover (the numbers refer to sections in Rosen's book):

1.1 Logic
1.2 Propositional equivalences
1.6 Sets
1.7 Set operations
1.8 Functions
10.1 Boolean functions
10.2 Representing Boolean functions
10.3 Logic gates
3.2 Sequences and summations
3.3 Mathematical induction
3.4 Recursive definitions and structural induction
4.1 The basics of counting
4.3 Permutations and combinations
4.4 Binomial coefficients
6.1 Recurrence relations
6.2 Solving recurrence relations
6.5 Inclusion-exclusion
6.6 Applications of inclusion-exclusion
8.1 Introduction to graphs
8.2 Graph terminology
8.3 Representing graphs and graph isomorphism
8.4 Connectivity
9.1 Introduction to trees
9.4 Spanning trees

The grading will be based on several half-hour quizzes (40%), the midterm (20%), and the final exam (40%). Homework will be regularly assigned and discussed in class. Although the homework is not counted in grading, the quizzes and tests will consist of similar problems so doing it is very essential.

It is your responsibility to be aware of any changes in the syllabus announced in class. Students are responsible for all information given when they are absent.

If you have a concern about the course or the instructor that cannot be resolved by speaking with the instructor, please contact Professor D. King (vice chair), 447 LA, x5679, donking@neu.edu.

It is University policy that no grade, including an incomplete, can be changed after one year. Exceptions must be authorized by the Academic Standing Committee.

All students without legitimate conflicts will take the final exam at the scheduled time. Do not make travel plans that conflict with the final exam.

Homework:
Sep. 10: read Section 1.1; pp. 15-17, #1 (e,f,g), 3 c,d), 15.
Sep. 11: read Section 1.2; pp. 16-18, #7 (a-f), 21, 23; p. 26, #7, 13.
Sep. 15: read Section 1.6; p. 85, #1, 4, 20, 24 (a), 25.
Sep. 17: read Section 1.7; pp. 94-96, #1-3, 10, 21, 40-43.
Sep. 18: read Section 1.8; pp. 108-109, #1, 7, 10-13, 16, 17, 19 (a-c).
Sep. 22: p. 109, #25-28, 31.
Sep. 24: read Section 10.1; p. 708, #3 (a,b), 7, 10, 11.
Sep. 25: read Section 10.2; p. 712, #1, 3, 12-14.
Sep. 29: read Section 10.3; p. 718, #1, 3, 6, 7, 15.
Oct. 1: review Sections 10.1-10.3; p. 708, #29; p. 712, #4,5; p. 718, #5, 8.
Oct. 2: read (relevant parts) of Section 3.2; pp. 236-237, #3, 7, 13, 15, 16, 19, 20.
Oct. 6: p. 237, #21, 23; read Section 3.3; p. 253, #1, 2. 5-7.
Oct. 8: p. 253, #9, 13, 15, 19.
Oct. 9: pp. 253-254, #11, 25, 31; read Section 3.4 up to Example 6; pp. 270-271, #1d), 3a), 13, 15.
Oct. 15: p. 253, #17; read Section 4.1; p. 310, #1, 7, 8, 11, 12, 16.
Oct. 16: p. 311, #19, 25, 29-31.
Oct. 20: read Section 4.3; pp. 324-325, #2, 3, 5, 6, 13, 17.
Oct. 22: pp. 325-326, #20, 30, 31.
Oct. 23: read Section 4.4; p. 333, #2, 4, 7, 9, 13.
Oct. 27: review the material in Chapters 1 and 10 (including old homeworks and quizzes 1-3).
Oct. 29: review the material in Chapters 3 and 4 (including old homeworks and quizzes 4-5).
Nov. 3: read Section 6.1; pp. 409-410, #1 (a,b), 5 (a-d), 9 (a, c, e, g), 25, 27.
Nov. 5: pp. 410-411, # 29, 40, 41.
Nov. 6: read Section 6.2 (pp. 413-416); p. 423, #3(c,d,e), 4(a,b,d), 7, 8.
Nov. 10: read Section 6.5; p. 456, #1, 3, 5, 7, 11, 13.
Nov. 12: p. 456, #17, 18; read Section 6.6, pp. 457, 460-461 (the number of onto functions); p. 464, #8, 9.
Nov. 13: read Section 6.6; pp. 461-464 (derangements); p. 464, #13, 15, 17.
Nov. 17: read Section 8.1; pp. 544-545, #11, 13, 19.
Nov. 19: read Section 8.2; pp. 554-555, #1, 5, 7, 13, 17.
Nov. 20: pp. 555-556, #19, 23, 24, 25, 27.
Nov. 24: p. 556, #29; read Section 8.3; pp. 564-565, #5, 9, 11, 34-36.
Dec. 1: pp. 565-566, #39, 41, 57, 69; read Section 8.4; p. 575, #1, 5.
Dec. 3: p. 576, #23-26.
Dec. 4: pp. 641-643, #1, 3, 9, 11a), 12a), 17, 19 (read relevant parts of Section 9.1).
Dec. 8: p. 643, #31; pp. 685-686, #5, 7, 9 (read relevant parts of Section 9.4).

Quizzes and tests:
Quiz 1: Sep. 18 (on Logic, Sets, sections 1.1, 1.2, 1.6).
Quiz 2: Sep. 25 (on Set Operations, Functions, sections 1.7, 1.8).
Quiz 3: Oct. 2 (on Boolean Algebra, sections 10.1, 10.2, 10.3).
Quiz 4: Oct. 16 (on Summations, Mathematical Induction, sections 3.2, 3.3).
Quiz 5: Oct. 23 (on Recursive Definitions, Basics of Counting, sections 3.4, 4.1).
Midterm: October 30 (on all the topics covered so far).
Quiz 6: Nov. 13 (on Recurrence Relations, sections 6.1, 6.2).
Quiz 7: Nov. 20 (on Inclusion-Exclusion Principle, sections 6.5, 6.6).
Quiz 8: Dec. 4 (on Graphs, sections 8.1, 8.2, 8.3).

Final Exam: Wednesday December 17 at 8:00 AM in 205 RY
(allowed: calculators, one sheet of notes).

GRADES (Attention: the version posted on December 17 contained mistakes; it is replaced on December 18).

Created: September 2, 2003. Last modified: December 18, 2003.