Mathematics 55

Spring, 2013
TuTh 3:40-5PM, 100 Lewis

Professor Kenneth A. Ribet

email:

Telephone: 510 642 0648

Fax: (510) 642-8204

Office hours (885 Evans Hall)

photo of Ribet at Calpalooza,
taken on August 23, 2012 as part of the Cal photobooth project

Graduate student instructors

Course outline

"Logic, mathematical induction, sets, relations, and functions. Introduction to graphs, elementary number theory, combinatorics, algebraic structures, and discrete probability theory."

Textbook

Discrete Mathematics and its Applications, seventh edition by Kenneth H. Rosen. You can buy a Cal custom edition of this book for $105 (new) or $78.75 (used) from the campus bookstore.

For better or for worse, Rosen's book is the 800lb gorilla in the discrete mathematics textbook market. It is used at hundreds, and perhaps thousands, of colleges and universities. You might want to consult the McGraw-Hill home page for the book for student resources and other material.

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

Chapter 1: all sections
Chapter 2: sections 1-5
Chapter 4: sections 1-4 and section 6
Chapter 5: sections 1-3
Chapter 6: sections 1-5
Chapter 7: all sections
Chapter 8: sections 1-2 and sections 4-6
Chpater 9: sections 1, 3, 4 and 5
Chapter 10: sections 1-5
Chapter 11: section 1 and Cayley's formula

Because there is a tremendous amount of material in the course, it is imperative to read ahead in the book before each lecture.

Schedule

Date

Themes

Sections

Homework problems

Jan. 22

Intro to the course

Propositions and such

§§ 1.1-1.3

§1.1: 6, 10, 18, 22

§1.2: 6, 10, 16, 20, 32

§1.3: 10, 12, 18

Jan. 24

Quantifiers, rules of inference

§§ 1.4-1.6

§1.4: 10, 14, 28, 32

§1.5: 12, 14, 20, 24

§1.6: 8, 10, 14, 20

Jan. 29

Proofs

§§ 1.6-1.8

§1.7: 12, 16, 22, 30

§1.8: 8, 10, 14, 22

Jan. 31

Sets, functions and more

§§ 2.1-2.3

§2.1: 10, 18, 22

§2.2: 14, 24, 30, 40, 52

§2.3: 4, 12, 20, 34

Feb. 5

Sequences, cardinality

§§ 2.4-2.5

§2.4: 14, 20, 26, 28

§2.5: 4, 10, 22, 24, 30

Feb. 7

The beginning of number theory!

§§ 4.1-4.3

§4.1: 16, 30, 36, 40

§4.2: 6ac, 8, 22ac, 28

§4.3: 6, 18, 30, 36

Feb. 12

More number theory

§ 4.3

Feb. 14

Consequences of Bézout's theorem

§ 4.4

§4.4: 14, 16, 18, 34

Feb. 19

Crpyto and some review

§ 4.6

§4.6: 2c, 4c, 12, 26

Feb. 21

First Midterm Exam

Feb. 26

Induction

§§ 5.1-5.2

§5.1: 10, 14, 30, 50, 52

§5.2: 4, 12, 30

Feb. 28

Recursive definitions

§ 5.3

§5.3: 12, 18, 14, 26, 30

Mar. 5

Counting and the pigeonhole principle

§§ 6.1-6.2

§6.1: 16, 26, 30, 44

§6.2: 4, 10, 16

Mar. 7

Permutations, combinations, binomials

§§ 6.3-6.4

§6.3: 12, 24, 26, 28

§6.4: 10, 14, 16, 20, 24

Mar. 12

More permutations and combinations

§ 6.5

§6.5: 16, 22, 26, 34, 38

Mar. 14

Probability begins!

§§ 7.1-7.2

§7.1: 14, 28, 32

§7.2: 8, 16, 18, 28

Mar. 19

Bayes

§§ 7.2-7.3

§7.3: 4, 10, 12

Mar. 21

Expected value and variance

§ 7.4

§7.4: 10, 14, 18, 28

Apr. 2

Expected values and Review

Apr. 4

Second Midterm Exam

Apr. 9

Recurrence relations

§§ 8.1-8.2

§8.1: 8, 10, 12, 14, 20

§8.2: 4ace, 8, 17

Apr. 11

Generating functions, inclusion-exclusion

§§ 8.4-8.6

§8.4: 4dgh, 8cg, 12cd, 14, 18

§8.5: 8, 14, 20

§8.6: 2, 4, 8, 16

Apr. 16

Relations

§ 9.1, § 9.3

§9.1: 10, 24, 38, 40

§9.3: 8, 10, 16

Apr. 18

Examinations

First midterm exam, Thursday, February 21, 2013, in class (questions and skeletal solutions, mean 17.6, standard deviation 7.0).
Last midterm exam, Thursday, April 4, 2013, in class (questions and skeletal solutions, mean 19.9, standard deviation 7.6).
Final examination, Friday, May 17, 2013, 7-10PM (sorry!), exam group 20 (questions and skeletal solutions, mean 33.74, standard deviation 13.08).

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

Spring, 1996 midterm and final exams (solutions to final);
Fall, 1997 midterm and final exams (solutions to final);
Various sample midterm and final exams are available on the Fall, 2011 Math 55 web page;
Check for old Math 55 web pages on Richard Borcherds' archive of math course web pages.
The old poker hand sheet that I showed you in lecture one day.
The list of quiz questions that were given in discussion sections through February 15, 2013.
The list of quiz questions that were given in discussion sections from mid-February to April 3, 2013.
The list of quiz questions that were given in discussion sections after April 3, 2013.

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 20%, final exam 46%.

According to the College academic calendar, the last day to add or drop this course is Friday, February 22, i.e., the day after the first midterm. The last day to change your grading option is Friday, April 5, 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 find the composite grade distribution for this course from schedulebuilder. (I checked and think that the grade distribution has been as follows: 30% A, 34% B, 24% C, 12% D/F.) While visiting this site, you can check out my ninjacourses ratings.

Homework

Homework will be due in section on Wednesdays:

January 30: sections 1.1-1.5
February 6: sections 1.6-1.8 and 2.1-2.3
February 13: sections 2.4-2.5 and 4.1-4.2
February 20: sections 4.3-4.4
February 27: section 4.6
March 6: sections 5.1-5.3
March 13: sections 6.1-6.4
March 20: sections 6.5, 7.1 and 7.2
April 3: sections 7.3 and 7.4
April 10: section 8.1
April 17: sections 8.2, 8.4, 8.5
April 24: sections 8.6, 9.1, 9.3 and 9.4
May 1: sections 9.5 and 10.1-10.3
May 8 (RRR period): sections 10.4, 10.7, 10.5

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.

Last Updated: GMT