Mathematics 55

Spring, 2015
TuTh 2:10-3:30PM, 100 Lewis

Logic, mathematical induction, sets, relations, and functions. Introduction to graphs, elementary number theory, combinatorics, algebraic structures, and discrete probability theory.
Professor Kenneth A. Ribet
email:
Telephone: 510 642 0648
Fax: (510) 642-8204
Office hours (885 Evans Hall)
first
lecture of the semester
"If you want to get to know him, you can, and even if you don't, you will."

Student Instructor Office Hours

Student Instructor Evans Hall Office Office Hours
Daniel Appel 739 MW 9:30-12
Alvin Jin 864 F 2:30-4:30
Watson Ladd 716 Tu 12-2
Chanwoo Oh 1095 Tu 9:55-10:55
Eugenia Rosu 1087 M 2-3, F 11-12

Discussion Sections

Section Time Room (U)GSI
101 8AM 87 Evans Alvin Jin
102 9AM 81 Evans Eugenia Rosu
103 10AM 85 Evans Watson Ladd
104 11AM 87 Evans Watson Ladd
105 12PM 87 Evans Alvin Jin
106 1PM 75 Evans Eugenia Rosu
107 2PM 237 Cory Daniel Appel
108 3PM 237 Cory Daniel Appel
109 8AM 30 Wheeler Chanwoo Oh

Textbook

photo of Ken Rosen and Ken Ribet,
January, 2015 Discrete Mathematics and its Applications, seventh edition by Kenneth H. Rosen. Rosen's book dominates the North American discrete mathematics market. It is used at hundreds, and perhaps thousands, of colleges and universities. You might want to consult the book's McGraw-Hill home page for student resources and other material.

The catalog description corresponds to the following sections of the textbook:

Because there is a tremendous amount of material in the course, it is imperative to read ahead in the book before each lecture. I welcome comments and questions during the lectures and would especially like to hear from you before each lecture as to what aspects of the material you would like me to emphasize.

Examinations

Please do not plan travel on the dates of these exams. If you believe that you have a conflicting obligation because of an intercollegiate sport or other extracurricular activity, please read these guidelines immediately.

For practice

Class schedule

DateThemes SectionsHomework problems
Jan. 20
Intro to the course
Propositions and such
§§ 1.1-1.3
§1.1: 3ac, 4bd, 7, 10, 13abc, 14abc
§1.2: 4, 7ab, 8ab, 16, 18
§1.3: 8, 10ab, 9ab, 16
Jan. 22Quantifiers, rules of inference§§ 1.4-1.6
§1.4: 10, 12ab, 13ab, 16ac, 17ac, 19cd, 20cd
§1.5: 1ab, 2ab, 6, 10, 11abc, 12abc
§1.6: 2, 3ac, 4cd, 6, 8, 10abc
Jan. 27Proofs §§ 1.6-1.8
§1.7: 8, 10, 12, 15, 22
§1.8: 4, 8, 12, 14, 23
Jan. 29 Sets, functions and more §§ 2.1-2.3
§2.1: 7, 8, 10, 18, 20, 22
§2.2: 14, 18, 20, 32
§2.3: 2a, 4, 8gh, 12, 13, 20
Feb. 3 Sequences, cardinality §§ 2.4-2.5
§2.4: 6de, 8, 12bd, 14ace, 26cde, 27, 34bd
§2.5: 2, 4, 6, 8, 10, 16, 18, 22
Feb. 5 The beginning of number theory! §§ 4.1-4.2
§4.1: 15, 16, 24, 30, 37
§4.2: 2c, 4bd, 8, 13, 26
Feb. 10 More number theory § 4.3 §4.3: 4df, 6, 11, 12, 24
Feb. 12 Consequences of B├ęzout's theorem § 4.4 §4.4: 6bcd, 7, 8, 12bc, 17, 18ab
Feb. 17 Crpyto and some review § 4.6 §4.6: 12, 24, 26, 31, 32
Feb. 19 First Midterm Exam
Feb. 24 Induction §§ 5.1-5.2
§5.1: 3, 4, 6, 10, 14, 18, 27, 50
§5.2: 5, 8, 10, 12, 14
Feb. 26 Recursive definitions § 5.3 §5.3: 4cd, 6ace, 10, 12, 13, 14, 15, 17
Mar. 3 Counting and the pigeonhole principle §§ 6.1-6.2
§6.1: 8, 14, 16, 22a-f, 25, 30, 40
§6.2: 4, 10, 23, 31, 36
Mar. 5 Permutations, combinations, binomials §§ 6.3-6.4
§6.3: 12, 16, 18, 21, 23, 24
§6.4: 8, 10, 14, 16, 20, 21
Mar. 10 More permutations and combinations § 6.5 §6.5: 5, 8, 10, 16, 18, 24, 25, 26
Mar. 12 Probability begins! §§ 7.1-7.2
§7.1: 12, 19, 26ab, 28
§7.2: 2, 6, 8, 12, 13; what is the probability that the 13th of a month occurs on a Friday?
Mar. 17 Bayes §§ 7.2-7.3 §7.3: 3, 6, 8, 12, 15
Mar. 19 Expected value and variance § 7.4 §7.4: 6, 10, 12, 19 (plus more to be due on April 8)
Mar. 31 Expected values and Review
Apr. 2 Second Midterm Exam
Apr. 7 Recurrence relations §§ 8.1-8.2
§8.1: 3, 4, 7, 8, 12
§8.2: 3cde, 4fg, 8, 11, 17, 23, 24
Apr. 9 Generating functions, inclusion-exclusion §§ 8.4-8.6
§8.4: 3ace, 4bde, 5ef, 6df, 7d, 8h, 13, 14, 15, 16
§8.5: 6, 8, 15
§8.6: 2, 8, 14, 16, 17
Apr. 14 Relations § 9.1, § 9.3
§9.1: 4, 6e-h, 8-9, 18, 20, 40, 50
§9.3: 2bd, 4c, 16
Apr. 16 More on relations §§ 9.4-9.5
§9.4: 20, 15, 10
§9.5: 2 (all parts), 9, 10, 18, 25, 46
Apr. 21 Less on graphs §§ 10.1-10.2
§10.1: 2 (all parts), 11, 13ab, 18
§10.2: 6, 18, 22, 24, 28, 29, 40
Apr. 23 More on graphs §§ 10.3-10.4
§10.3: 12, 24, 25, 34, 35, 36
§10.4: 4, 5, 11ab, 12ab, 20, 21, 23, 43
Apr. 28 Planar graphs § 10.7 §10.7: 2, 4, 8, 12, 14, 17
Apr. 30 Euler and Hamilton paths and circuits § 10.5 §10.5: 2, 3, 4, 8, 10, 11
May. 5 Review
May. 7 Questions
May. 11 Final Exam, 11:30AM-2:30PM

Homework

Homework will be due in your discussion section on Wednesdays:
  1. January 28: sections 1.1-1.5
  2. February 4: sections 1.6-1.8 and 2.1-2.3
  3. February 11: sections 2.4-2.5 and section 4.1
  4. February 18: sections 4.2-4.4
  5. February 25: sections 4.6 and 5.1
  6. March 4: sections 5.2-5.3
  7. March 11: sections 6.1-6.3
  8. March 18: sections 6.4-6.5, 7.1-7.2
  9. April 1: sections 7.3, 7.4
  10. April 8: these problems from §7.4: 21, 24, 28, 32, 35
  11. April 15: sections 8.1-8.2
  12. April 22: sections 8.4-8.6 and section 9.1
  13. April 29: sections 9.3-9.5 and section 10.1
  14. May 6 (RRR period): sections 10.2-10.5 and 10.7
Each assignment will be worth 12 points. Your homework grade will be the sum of your twelve highest grades and half of your next-to-lowest grade. Accordingly, the maximum possible homework grade will be 150; we are "dropping" your lowest 1 1/2 grades.

Random Links

Grading

Course grades will be based on a composite numerical score that is intended to weight the course components roughly as follows: midterm exams 17% each, homework and quizzes 20%, final exam 46%.

According to the College academic calendar, the last day to add or drop this course is Friday, February 20, i.e., the day after the first midterm. The last day to change your grading option is Friday, April 3, i.e., the day after the second midterm. Incomplete grades will be assigned only to students for whom a documented medical, personal or family emergency precludes completion of the course. Students receiving such grades are required to have been doing work of passing quality up to the intervention of the emergency.

You can deduce the composite grade distribution for this course from schedulebuilder. (I calculated that the grade distribution has been as follows: 31% A, 34% B, 24% C, 11% D/F, but you might want to check my work.) While visiting this site, you can review my ninjacourses ratings.

"Ribet is the bomb. His lectures are crystal clear and fresh, and I actually looked forward to them because he was extremely animated and perceptive to his student's needs. Catch his Math 55 class in the spring if you can! It'll be great, guaranteed. :)"

You can read the student evaluations for this course now that it's over.

Last Updated: GMT

Valid HTML 4.01!