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: 7-8PM, TH, 8-9 PM, CSE 4140

Teaching assistant: Josh Marxen (jmarxen@eng.ucsd.edu). Office Hours: M, TH 11-noon, CSE 4140

Mentor: Shuyu Mao: Study Session: M-TH 7-9 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:30-9:50 in CSE 4258.

Discussion Section:. M/TH 10-10:50 in CSE 4258. 

Office Hours: Neil: M: 7-8, TH 8-9 PM CSE 4140, Josh: M/TH 11-noon CSE 4140

Study Sessions: Sunday-Thursday: 7-9 PM, CSE 4140

Textbook 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 Board

A 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 2-page study guide for one topic in the course. The study guide is due Thursday, September 4, in class.  Here's a sample.

Grading

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

Scores can be seen at GradeSource.

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 scoreGrade
≥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: 3-6 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.1-2.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:
  • 2.4: 3, 4, 21, 25, 31
     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.1-4.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, 11-14, 19, 23 ,24, 32
    		     Aug 13
    Direct Methods of Proof
    Quiz 6
    Reading: 4.4-4.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.6-4.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.2-5.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.1-6.2
    Proofs: #4 due, rewritten #2 due
    HW:
    • 5.5: 2, 7, 9, 11
     Aug 25
    Set Theory
    Quiz 12
    Reading: 6.3-6.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.1-7.3
    Proofs: #5 due, rewritten #3 due
    HW:
    • 6.3: 2, 8, 24, 40 46
    • 6.4: 20-26
     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.1-8.3
    Proofs: Rewritten #4 due
    HW:
    • 7.4: 1, 4, 9, 17, 32, 38
     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, 34-36
    • 8.3: 2, 12, 42, 45
    		 
      Sep 3
    Permutations/Combinations/Pigeonhole Principle
    Quiz 17
    Reading: 9.3 (Permutations only), 9.4-9.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 closed-book, closed-calculator, closed-note, other than one single-sided handwritten 8.5"x11" page of notes.

    Here's an old midterm (along with its solution). 

    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.