CSE 20: Introduction to Discrete Mathematics
UC San Diego Academy 2015
Welcome to CSE 20 Introduction to Discrete Mathematics!
Instructor and mentors
Instructor: Neil Rhodes ( nrhodes@cs.ucsd.edu). Office Hours/Study Session: M, W: 78PM, TH, 89 PM, CSE 4140
Teaching assistant: Josh Marxen (jmarxen@eng.ucsd.edu). Office Hours: M, TH 11noon, CSE 4140
Mentor: Shuyu Mao: Study Session: MTH 79 PM, CSE 4140(other than times Neil will be there).
Course description
Basic discrete mathematical structures: sets, relations, functions, sequences, equivalence relations, partial orders, number systems. Methods of reasoning and proofs: prepositional logic, predicate logic, induction, recursion, pigeonhole principle. Infinite sets and diagonalization. Basic counting techniques; permutation and combinations. Applications will be given to digital logic design, elementary number theory, design of programs, and proofs of program correctness.
Lecture: M/T/TH/F 8:309:50 in CSE 4258.Discussion Section:. M/TH 1010:50 in CSE 4258. Office Hours: Neil: M: 78, TH 89 PM CSE 4140, Josh: M/TH 11noon CSE 4140Study Sessions: SundayThursday: 79 PM, CSE 4140Textbook and other course materials
Discrete Mathematics with Applications, 4th edition, Susanna Epp, Cengage Learning.
All textbooks and course materials will be provided to the students free of charge on the opening day (August 2, 2015).
Discussion BoardA discussion board is available which has announcements, and where you can post questions and answers. Quizzes/Proofs Quizzes will be given at the beginning of each class and will consist of a small subset of homework problems for that day (with, possibly, small changes). Homework is not graded or turned in. Proofs are submitted, corrected, and then rewritten. Study Guide You will work in pairs to create a 2page study guide for one topic in the course. The study guide is due Thursday, September 4, in class. Here's a sample.
GradingGrades will be assigned by first computing a raw score: Final_score = 15%*Highest_15_Quizzes + 15%*Proofs + 10%*Study_Guide + Max(30%*Midterm + 30%*Final, 20%*Midterm + 40%*Final) In other words, I'll drop the bottom 2 quiz scores; the remaining 15 quizzes will account for 15% of your final score. Proofs will count for 15% of your grade. The study guide will count for 10%. The midterm and final together are worth the remaining 60%: the percentages are either 30/30 or 20/40, depending on which gives a better score.
Regrades: You have the right of appeal for grading on all tests; however, an appeal (except for clerical errors) covers the entire test, and may result in an unfavorable judgment on another problem. You have one week from the time the tests are returned to make appeals, including addition errors on your score. Check it over carefully when you get it. Appeals must be made in writing and turned in to the TA.Grades:A final overall percentage score will be calculated based on the weighted average of the scores earned on exams and quizzes. This percentage score will be used to determine a final letter grade as follows:Percentage score  Grade  ≥90%  A  ≥80%<90%  B  ≥65%<80%  C  ≥50%<65%  D  <50%  F  Pluses and minuses will be attached to the letter grades as the instructor deems appropriate.
Academic integrity
Read the Jacobs School of Engineering code of Academic Integrity. For proofs, you may use the book, instructor, TA, or mentors, but may not use any other resources (including the internet). You may discuss approaches for proofs with other students, but should not read other's proofs. Talk, and even use a whiteboard, but don't copy what another student has written.
Disabilities Students requesting accommodations for this course due to a disability must provide a currentAuthorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD) which is located in University Center 202 behind Center Hall. Students are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance so that accommodations may be arranged. Contact the OSD for further information: 858.534.4382 (phone) osd@ucsd.edu(email)http://disabilities.ucsd.edu(website)
Schedule
Academy Social Sunday: August 9th: 36 PM (meet by the bear).
Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
Aug 3
Getting Started (Slides)
Reading: Chapter 1 
Aug 4
Propositional Logic
Quiz 1
Reading: 2.12.3
HW:
 1.1: 2, 6, 11
 1.2, 2, 3, 4, 7, 8, 12


Aug 6
Boolean Circuits
Quiz 2
Reading: 2.4
HW:
 2.1: 3, 6, 8, 11, 12, 16, 25, 37, 50
 2.2: 3, 11, 18, 20, 22, 23, 33, 36, 44, 45
 2.3: 5, 8, 22, 24, 25, 28, 29, 36

Aug 7
Number Systems/
Computer Arithmetic
Quiz 3
Reading: 2.5
HW:

Aug 10
Predicate Logic
Quiz 4
Reading: Chapter 3 (except Prolog in 3.3) HW:
 2.5: 9, 12, 16, 18, 22, 24, 28, 34, 40, 43, 45, 47b

Aug 11
Number Theory/
Direct Methods of Proof
Quiz 5
Reading: 4.14.3 HW:
 3.1: 2, 3, 12, 13, 16, 17, 30
 3.2: 2, 10, 15, 17, 23, 44
 3.3: 4, 11, 35, 36, 43, 45, 50, 57
 3.4: 4, 6, 1114, 19, 23 ,24, 32


Aug 13
Direct Methods of Proof
Quiz 6
Reading: 4.44.5 Proofs: #1 due HW:
 4.1: 5, 6, 16, 18, 28, 36, 41, 42, 46
 4.2: 7, 8, 18, 36, 38, 39
 4.3:5, 15, 23, 37, 42, 45

Aug 14
Indirect Methods of Proof
Quiz 7
Reading: 4.64.8 HW:
 4.4: 10, 19, 21, 27, 35, 50
 4.5: 4, 5, 9, 21, 22, 24, 28, 30

Aug 17
Sequences
Quiz 8
Reading: 5.1 Proofs: #2 due HW:
 4.6: 4, 9, 24, 31
 4.7: 8, 10, 11, 12, 19, 28, 33
 4.8: 7, 12, 19, 27

Aug 18
Induction
Quiz 9
Reading: 5.25.4 HW:
 5.1: 4, 15, 26, 39, 41, 52, 54, 61, 67, 72, 83


Aug 20
Induction
Quiz 10
Reading: 5.5 Proofs: #3 due, rewritten #1 due HW:
 5.2: 4, 5, 7, 27, 33
 5.3: 2, 17, 28, 30, 31, 35, 37,
 5.4: 7, 11, 19, 20, 25, 26

Aug 21
Midterm (covers through Sequences)

Aug 24
Set Theory
Quiz 11
Reading: 6.16.2 Proofs: #4 due, rewritten #2 due HW:

Aug 25
Set Theory
Quiz 12
Reading: 6.36.4 (except Boolean Algebras section of 6.4) HW:
 6.1: 1, 7, 13, 14, 18, 26, 29, 33
 6.2: 1, 2, 8, 20, 22, 26, 37


Aug 27
Functions
Quiz 13
Reading: 7.17.3 Proofs: #5 due, rewritten #3 due HW:
 6.3: 2, 8, 24, 40 46
 6.4: 2026

Aug 28
Cardinality
Quiz 14
Reading: 7.4 HW:
 7.1: 2, 7, 16, 17, 27, 30, 34, 42, 44, 50
 7.2: 2, 5, 17, 18, 22, 39, 43
 7.3: 2, 17, 20

Aug 31
Relations
Quiz 15
Reading: 8.18.3 Proofs: Rewritten #4 due HW:

Sep 1
Partial Order Relations
Quiz 16
Reading: 8.5 Study guide due. HW:
 8.1: 5, 8, 20
 8.2: 2, 3, 14, 17, 3436
 8.3: 2, 12, 42, 45
 
Sep 3
Permutations/Combinations/Pigeonhole Principle
Quiz 17
Reading: 9.3 (Permutations only), 9.49.5 Proofs: Rewritten #5 due HW:
 8.5: 1, 6, 7, 11, 17, 28, 30, 32, 48, 50

Sep 4
Final exam: 8:30 a.m 11:30 a.m. HW:
 9.3: 2, 8, 21, 24, 38
 9.4: 2, 19, 27, 28, 33
 9.5: 7, 16, 25

Exams
Exams will be closedbook, closedcalculator, closednote, other than one singlesided handwritten 8.5"x11" page of notes.
Here's an old final (along with its solution). Ignore problem 12; we didn't cover RSA.
My recommendation for using the practice final: study, including looking at midterms, quizzes and homework problems. Then, take the practice final as a practice: give yourself 3 hours and do it. Only then look at the solution.
