Mathematics 55

Spring, 2019
TuTh 12:30-2PM, 2050 VLSB

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)

"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

Katrina Biele 739 Th 3:30-5:30

Benjamin Castle 737 Tu, Th 10-11

Rahul Dalal 747 F 11-1

Christopher Miller 1049 M 10-12

Max Wimberley 1047 Th 10-11, F 1-2

Dylan Yott 1065 M 10-11, Tu 11:30-12:30

Dongxiao Yu 1085 Tu 10-12, Fri 2-3

Textbook

photo of Ken Rosen and Ken Ribet, January, 2018

Discrete Mathematics and its Applications, eighth edition by Kenneth H. Rosen.

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. 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

First midterm exam, Thursday, February 21, 2019, in class (median 20.0, maximum 34.0, mean 19.94, standard deviation 7.64, questions, questions and answers)
Last midterm exam, Thursday, April 4, 2019, in class (median 17.0, maximum 34.0, mean 17.07, standard deviation 7.43, questions, questions and answers)
Final examination, Thursday, May 16, 2019, 3PM (questions, questions and answers)

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.

Quizzes

There will be six quizzes during the semester. These are 20-minute short examinations that are given during the discussion sections.

Schedule of quizzes

Date Relevant Chapter

February 4 1

February 13 2

March 4 5

March 18 6

April 17 8

May 1 10

In calculating your quiz grade, we will add together your five highest scores. In other words, your lowest quiz grade will be dropped.

For practice

Spring, 1996 midterm and final exams (solutions to final).
Fall, 1997 midterm and final exams (solutions to final).
Spring 2013 questions and (skeletal) answers to: first midterm exam, second midterm exam, final exam.
Spring 2015 questions and (skeletal) answers to: first midterm exam, second midterm exam, final exam.
Six-year old quiz questions:
- Questions given in 2013 discussion sections through February 15, 2013.
- Questions given in discussion sections between mid-February and April 3, 2013.
- Questions given in 2013 discussion sections after April 3, 2013.
Sample exams are available on the Fall, 2011 and Spring, 2014 Math 55 web pages by Lauren Williams.
Check for old Math 55 web pages on Richard Borcherds' archive of math course web pages.

Class schedule

Date

Themes

Sections

Homework problems

Jan. 22

Intro to the course

Propositions and such

§§ 1.1-1.3

§1.1: 1abde, 2abcd, 4cd, 6bd, 10, 14bdf

§1.2: 2, 5, 8cd, 14, 19, 20

§1.3: 8ad, 9b, 10c, 11bdf, 13(bdf)

Jan. 24

Quantifiers, rules of inference

§§ 1.4-1.6

§1.4: 5, 6, 8, 14, 21, 34

§1.5: 2, 3abc, 4def, 10, 11

§1.6: 2, 3abc, 4de, 5, 8, 14

Jan. 29

Proofs

§§ 1.6-1.8

§1.7: 5, 7, 8, 9, 11, 15, 16, 18, 19, 21

§1.8: 1, 2, 5, 8, 10, 11, 12, 14

Jan. 31

Sets, functions and more

§§ 2.1-2.3

§2.1: 6, 11, 12, 13, 22, 24, 25, 33

§2.2: 2, 4, 16e, 38, 41, 42, 52

§2.3: 3, 4, 8gh, 10, 14, 23, 32, 36, 37

Feb. 5

Sequences, cardinality

§§ 2.4-2.5

§2.4: 5fg, 6bdf, 10bd, 12d, 16ab, 18, 22

§2.5: 1cdf, 2def, 3bd, 4cd, 6, 7, 10, 16

Feb. 7

The beginning of number theory!

§§ 4.1-4.2

§4.1: 9, 10, 12, 16c, 18ace, 21, 22, 44

§4.2: 2c, 4b, 7d, 8, 28, 32, 38

Feb. 12

More number theory

§ 4.3

§4.3: 4f, 6, 9, 10, 12, 18, 25ef, 30, 32ef, 39hi

Feb. 14

Consequences of Bézout's theorem

§ 4.4

§4.4: 6bc, 8, 12b, 16, 21, 22, 32, 34, 38

Feb. 19

Crypto and some review

§ 4.6

§4.6: 12, 24, 26, 28, 31

Feb. 21

First Midterm Exam

Feb. 26

Induction

§§ 5.1-5.2

§5.1: 3, 4, 6, 10, 27, 49

§5.2: 4, 10, 12, 30, 32

Feb. 28

Recursive definitions

§ 5.3

§5.3: 1cd, 2d, 6ace, 8, 10, 12, 13, 17, 18, 19

Mar. 5

Counting and the pigeonhole principle

§§ 6.1-6.2

§6.1: 8, 16, 22, 32, 46, 48, 68

§6.2: 6, 14, 18, 28, 33, 42

Mar. 7

Permutations, combinations, binomials

§§ 6.3-6.4

§6.3: 9, 12, 13, 14, 22, 24, 28, 43

§6.4: 8, 12ace, 14, 19, 24, 25, 26, 28

Mar. 12

More permutations and combinations

§ 6.5

§6.5: 4, 10, 11, 15, 18, 20, 24, 26, 34

Mar. 14

Probability begins!

§§ 7.1-7.2

§7.1: 6, 8, 12, 16, 24, 31, 34

§7.2: 5, 6, 8, 11, 13, 17, 20

Mar. 19

Bayes

§§ 7.2-7.3

§7.3: 3, 6, 8, 12, 16

Mar. 21

Expected value and variance

§ 7.4

§7.4: 6, 8, 10, 12, 15, 16, 25, 29, 36

Apr. 2

Expected values and Review

Apr. 4

Second Midterm Exam

Apr. 9

Recurrence relations

§§ 8.1-8.2

§8.1: 3, 4, 6, 12, 13, 28, 29

§8.2: 3cde, 8, 9, 11, 17, 23

Apr. 11

Generating functions, inclusion-exclusion

§§ 8.4-8.6

§8.4: 4acfg, 6(all), 8abc, 9c, 10c, 17

§8.5: 6, 10, 25, 26

§8.6: 2, 6, 14, 18, 19

Apr. 16

Relations

§ 9.1, § 9.3

§9.1: 3, 4, 6, 8, 12, 19, 26, 36ace, 51

§9.3: 2ac, 4ac, 5, 6, 9, 10, 24

Apr. 18

Homework

Homework will be due in your discussion 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 section 4.1
February 20: sections 4.2-4.4
February 27: sections 4.6 and 5.1
March 6: sections 5.2-5.3
March 13: sections 6.1-6.3
March 20: sections 6.4-6.5, 7.1-7.2
April 3: sections 7.3, 7.4
April 10: these problems from §7.4: 21, 24, 28, 32, 35
April 17: sections 8.1-8.2
April 24: sections 8.4-8.6 and section 9.1
May 1: sections 9.3-9.5 and section 10.1
May 8 (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.

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%.

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.

The grade distribution for this course has historically been as follows: 31% A, 34% B, 24% C, 11% D/F.

Random Links

The first 50 million prime numbers by Don Zagier
The largest prime number known to date was discovered at the end of the fall RRR week.
An article about me in The Math Dong-A, a mathematics magazine in Korea for middle school and high school students
See if you can do the worm problem
My Numberphile video on the Math 55 bagel problem
My Numberphile interview, ``The Bridges to Fermat's Last Theorem''
My Numberphile podcast on Fermat's Last Theorem
Our class's piazza group
Infinity is bigger than you think
Numberphile video on the stable marriage problem
Facebook adoption article by Jon Kleinberg
Bayes' Theorem with Lego
Chances are, a great NY Times article about Bayes's Rule.
The Tversky-Kahneman Taxicab problem
Sage, a free open-source mathematics software system that will compute all sorts of numbers and objects that are relevant to our course
Printed sculpture and Fibonacci numbers
A silly article about Fibonacci numbers and investing
A poker hand sheet from Fall, 1997 that I may project in lecture some day.
The Berkeley Student Learning Center's Math 55 page

Last Updated: GMT

Student Instructor	Evans Hall Office	Office Hours
Katrina Biele	739	Th 3:30-5:30
Benjamin Castle	737	Tu, Th 10-11
Rahul Dalal	747	F 11-1
Christopher Miller	1049	M 10-12
Max Wimberley	1047	Th 10-11, F 1-2
Dylan Yott	1065	M 10-11, Tu 11:30-12:30
Dongxiao Yu	1085	Tu 10-12, Fri 2-3

Date	Relevant Chapter
February 4	1
February 13	2
March 4	5
March 18	6
April 17	8
May 1	10