Math 55: Discrete Mathematics

Fall 2015

Homework

Instructor: David Li-Bland

Email:

Lectures: TuTh, 11-12:30pm, 245 Li Ka Shing

Course Control Number: 54071

Prerequisites: Mathematical maturity appropriate to a sophomore math class. 1A-1B recommended.

Required Text: Discrete Mathematics and its Applications, (7th Edition, custom UC Berkeley paperback edition.) by Kenneth H. Rosen.

Weekly Schedule of Office Hours:
Monday Tuesday Wednesday Thursday Friday
Ken 9-10am Ken 8:30-9:30am Eric 8-10am
Anh 10-11am
Lecture 11-12:30pm Anh 11-12pm Lecture 11-12:30pm
David 12:30-2pm David 12:30-2pm
Justin 2:30-3:30pm Justin 2:30-3:30pm
Anh 3:30-4:30

Office Hours: Times: Location:
David Li-Bland TuTh, 12:30-2pm 1071 Evans Hall
Justin Brereton MW, 2:30-3:30pm 1056 Evans Hall
Eric Hallman F, 8-10am 1058 Evans Hall
Kenneth Hung M, 9-10am; Tu, 8:30-9:30am 787 Evans Hall
Michael Klug TBA 858 Evans Hall
Anh Nguyen M, 10-11am; Tu, 3:30-4:30pml; W, 11-12am 1070 Evans Hall

Textbook

The textbook for this course is Kenneth H. Rosen’s Discrete Mathematics and its Applications, (7th Edition). We will be using the custom UC Berkeley paperback edition, which omits some material found in the standard edition. 

The lectures will correspond to particular sections of the book (indicated in the syllabus below), and since there is a tremendous amount of material in the course, it is imperative that you read ahead. However, please note that in class I may present material in a different order or from a different perspective than that of the book. Thus it is important to attend class and, since you shouldn't expect to understand everything right away, to take good notes. 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; I would strongly encourage you to post questions outside of class to Piazza.


Media and External Links

Some fun discrete math videos, as well as links to external resources (such as past exams), can be found here.


Study tips:

  • It is necessary to learn the statements of the theorems that we will be proving; 
  • It is not necessary to memorize the proofs of theorems. However the more proofs you understand, the better your command of the material will be. When you study a proof, a useful aid to memory and understanding is to try to summarize the key ideas of the proof in a sentence or two. If you can't do this, then you probably don't yet really understand the proof. 
  • If you want to really understand the material, the key is to ask your own questions. Can I find a good example of this? Is that hypothesis in that theorem really necessary? What happens if I drop it? Can I find a different proof using this other strategy? Does that other theorem have a generalization to the noncommutative case? Does this property imply that property, and if not, can I find a counterexample? Why is that condition in that definition there? What if I change it this way? This reminds me of something I saw in linear algebra; is there a direct connection?
  • If you get stuck on any of the above, you are welcome to come to my office hours. I am happy to discuss this stuff with you. Usually, the more thought you have put in beforehand, the more productive the discussion is likely to be.

Homework

There will be weekly homework (posted here). All the homework assigned in a given week will be due in your discussion section the following Wednesday. No late homework will be accepted. 

A random selection of the assigned homework will be graded.

When calculating grades, we will drop your two lowest homework scores and use only your remaining scores, moreover the final homework grades for each discussion section will be curved to normalize the medians relative to each other.

When preparing your homework, please keep the following in mind:

1) You are encouraged to discuss the homework problems with your classmates. The best way to learn is to think hard about a problem on your own until you get really stuck or solve it, then ask someone else how they thought about it. However, when it comes to writing down your solutions, you must do this by yourself, in your own words, without looking at someone else's paper or any other source.

2) All answers should be written in complete sentences which explain the logic of what you are doing, with mathematical symbols and equations interspersed as appropriate. For example, instead of writing "x^2 = 4, x = 2, x = -2", write "since x^2 = 4, it follows that x = 2 or x = -2." If your proof is unreadable it will not receive credit. Results of calculations and answers to true/false questions etc. should always be justified. Proofs should be complete and detailed. The proofs in the book provide good models; but when in doubt, explain more details. You can of course cite theorems that we have already proved in class or from the book.

Some suggestions from Ian Agol for writing mathematics are available here.


Grading Policy: 

%20 Homework, %20 Midterm I, %20 Midterm II, %40 Final

Exams:

  • Midterm Exam 1: Thursday, Sept. 24th, 11-12:30pm in 245 Li Ka Shing.
  • Midterm Exam 2: Tuesday, Nov. 3rd, 11-12:30pm in 245 Li Ka Shing.
  • Final Exam: Wednesday, Dec. 16, 2015 8-11am

No make-up midterms will be given. If you are absent from one of the midterms, you must have a valid reason and present proof. In such a case, your final exam grade will be substituted for the missed midterm grade.

The L&S student calendar lists drop and grade-change deadlines. The deadline to drop is Friday, Sept. 25th.


Class Schedule: 

Date

Themes

Sections

Homework problems





Aug. 27

Intro to the course
Propositions and such

§§1.1-1.3

§1.1: 3ac, 7, 10, 13abc, 18, 24acd
§1.2: 5, 7ab, 8ab, 16, 17, 21, 25
§1.3: 8, 9, 11, 22

Sept. 1

Quantifiers, rules of inference

§§1.4-1.6

§1.4: 10, 13, 17, 18
§1.5: 2, 7ace, 9, 20, 39
§1.6: 2, 4, 6, 8, 10abc, 15

Sept. 3

Proofs

§§1.6-1.8

§1.7: 8, 10, 17, 22
§1.8: 7, 12, 14, 23, 43

Sept. 8

Sets, functions and more

§§2.1-2.3

§2.1: 5, 7, 8, 10, 18, 20, 22
§2.2: 14,15, 18, 20, 60
§2.3: 2a, 5, 12, 13, 21, 42b, 44

Sept. 10

Sequences, cardinality

§§2.4-2.5

§2.4: 14, 20, 26, 28
§2.5: 4, 9, 10, 22, 24, 30

Sept. 15

The beginning of number theory!

§§4.1-4.2

§4.1: 10abc, 15, 16, 25, 32, 37
§4.2: 2c, 4bd, 11, 13, 25

Sept. 17

More number theory

§4.3

§4.3: 4df, 6, 15, 25, 32

Sept. 22

Consequences of Bézout’s theorem

§4.4

§4.4: 6, 7, 8, 16, 33, 50

Sept. 24
First Midterm Exam
Sept. 29

Crpytography

§4.6

§4.6: 11, 12, 24, 26, 31, 32

Oct. 1

Induction

§§5.1-5.2

§5.1: 3, 4, 7, 10, 15, 18, 27, 49
§5.2: 3, 6, 8, 11, 14, 23

Oct. 6

Recursive definitions

§5.3

§5.3: 3cd, 5ace, 9, 12, 13, 14, 15, 30

Oct. 8

Counting and the pigeonhole principle

§§6.1-6.2

§6.1: 8, 16, 23, 26, 30, 41
§6.2: 3, 10, 23, 33

Oct. 13

Permutations, combinations, binomials

§§6.3-6.4

§6.3: 12, 24, 26, 28
§6.4: 8, 10, 14, 16, 20, 22

Oct. 15

More permutations and combinations

§6.5

§6.5: 5, 8, 9, 16, 19, 25, 45

Oct. 20

Probability begins!

§§7.1-7.2

§7.1: 15, 29, 32
§7.2: 7, 16, 19, 28

Oct. 22

Bayes

§§7.2-7.3

§7.3: 4, 7, 9, 12, 15

Oct. 27

Expected value and variance

§7.4

§7.4: 6, 10, 12, 19

Oct. 29

Expected values and Review

Nov. 3
Second Midterm Exam
Nov. 5

Recurrence relations

§§8.1-8.2

§8.1: 8, 10, 12, 14, 20
§8.2: 4, 8, 11, 17, 23, 24

Nov. 10

Generating functions, inclusion-exclusion

§§8.4-8.6

§8.4: 4, 6a-d, 8a-d, 13, 14, 15, 16
§8.5: 5, 9, 17
§8.6: 2, 9, 14, 16, 22

Nov. 12

Relations

§9.1, §9.3

§9.1: 3, 10, 24, 38, 40,
§9.3: 1ab, 3b, 16

Nov. 17

More on relations

§§9.4-9.5

§9.4: 11, 15, 22
§9.5: 2, 9, 10, 18, 25, 45

Nov. 19

Less on graphs

§§10.1-10.2

§10.1: 1, 11, 13a, 20
§10.2: 6, 18, 22, 24, 28, 29, 40

Nov. 24

More on graphs

§§10.3-10.4

§10.3: 11, 24, 25, 34, 37, 42
§10.4: 2, 18, 22, 27, 28, 38

Dec. 1

Planar graphs

§10.7

§10.7: 4, 6, 14, 18, 20

Dec. 3

Euler and Hamilton paths and circuits

§10.5

§10.5: 1, 3, 5, 7, 10, 11

Dec. 8
Review
Dec. 10
Questions
Dec. 16
Final Exam, 8-11Am



Piazza: To handle questions posed outside of class, we will be using Piazza, a free platform for instructors to efficiently manage out-of-class Q&A. On the class dashboard, students can post questions and collaborate Wikipedia-style to edit responses to these questions. Instructors can also answer questions, endorse student answers, and edit or delete any posted content. Instead of emailing me math questions, I encourage you to post them to Piazza.

You will be able to access Piazza via the bCourses webpage for this class.


Approach to work and classroom/Piazza interactions:

Please behave according to the academic honor code:

"As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others."


Incomplete grades: Incomplete “I” grades are almost never given. The only justification is a documented serious medical problem or genuine personal/family emergency. Falling behind in this course or problems with workload in other courses are not acceptable reasons.

Special arrangements: If you are a student with a disability registered by the Disabled Student Services (DSS) on UCB campus and if you require special arrangements during exams, you must provide the DSS document and make arrangements via email or office hours at least 10 days prior to each exam, explaining your circumstances and what special arrangements need to be done. Also, see the lecturer as soon as possible to make arrangements for the homeworks.

If you have scheduling conflicts (e.g. for religious holidays or extracurricular activities), please inform the lecturer by the second week of class in writing, and he will attempt to make arrangements to accommodate you.

If you are forced to miss class, homework deadlines, or examinations due to illness, pregnancy, or parenting, please contact the lecturer as soon as possible to see if arrangements can be made.

© David Li-Bland 2014