• Propositional and predicate logic, set theory, functions and relations, counting, mathematical induction and recursion.

Lecture topics, homeworks and announcements:

• November 20 (Friday): Homework 8 is posted. Due December 4 (Friday).
• Lecture 16, Thursday, November 19: Applications and the proof of the inclusion-exclusion formula, derangements, balls-in-boxes.
• November 18 (Wednesday): Midterm statistics: Average grade = 31/65, Lowest grade = 15/65, Highest grade =50/65.
• Lecture 15, Tuesday, November 17: More on binomial coefficients, models for binomial coefficients, multinomial coefficients, the binomial theorem, Pascal's triangle, algebraic versus combinatorial proofs, balls-in-boxes, lattice paths, identities, inclusion-exclusion.
• November 13 (Friday): Homework 7 is posted. Due November 20 (Friday). Solutions to homework 7
• Lecture 14, Thursday, November 12: The pigeonhole principle, counting, rule of sum and rule of product, permutations, combinations, factorials, subsets, binomial coefficients.
• November 11 (Wednesday): Solutions to the Midterm Exam.
• THE MIDTERM EXAM IS ON TUESDAY, NOVEMBER 10. PLEASE BRING A BLUE-BOOK AND YOUR ID.
• November 7 (Saturday): Homework 6 is posted. Due November 16 (Monday). Solutions to homework 6
• November 5 (Thursday): For the upcoming midterm: Eyrun's list of common mistakes, Lijie's list of clarifications.
• Lecture 13, Thursday, November 5: Fibonacci numbers, recursive definitions, extended binary trees, structural induction, review.
• November 3 (Tuesday): Sample problems from previous exams.
• Lecture 12, Tuesday, November 3: Well-ordering principle, strong induction, examples, polygons, Pick's theorem.
• October 30 (Friday): Homework 5 is posted. Due November 6 (Friday). Solutions to homework 5
• Lecture 11, Thursday, October 29: The principle of mathematical induction, strong induction, structural induction, examples and pitfalls.
• Lecture 10, Tuesday, October 27: Base-b representations, binary, octal, decimal, hexadecimal systems, conversion between representations, "casting out 9's", Fermat's little theorem, Euler's function.
• October 23 (Friday): Homework 4 is posted. Due October 30 (Friday). Solutions to homework 4
• Lecture 9, Thursday, October 22: Euclid's algorithm for GCD computations, extended Euclid algorithm, solving linear modular equations, systems of equations, the Chinese remainder theorem, arithmetic using the Chinese remainder theorem.
• Lecture 8, Tuesday, October 20: Integers, divisibility, quotient and remainder, modular arithmetic, linear congruential generators, Caesar cypher, prime numbers, prime factorization, the infinitude of primes, GCD and LCM calculations.
• October 16 (Friday): Homework 3 is posted. Due October 23 (Friday). Solutions to homework 3
• Lecture 7, Thursday, October 15: Properties of countable sets, Cantor's diagonal argument, the uncountability of the Real numbers, the existence of non-computable functions.
• Lecture 6, Tuesday, October 13: Bit-string representation of sets, functions, domain, co-domaini, range, 1-1, onto, inverse images, inverse functions, function composition, characteristic functions, equivalence of sets, countably infinite sets, countable sets, countability of the rationals.
• October 9 (Friday): Homework 2 is posted. Due October 16 (Friday). Solutions to homework 2
• Lecture 5, Thursday, October 8: Types of proofs, proof by cases, geometric proofs, dominos-triominos, sets, membership, equality, Boolean operations, Venn diagrams, Cartesian product, empty set, power set, truth sets of predicates, intersection and union notation, finite and infinite sets, cardinality.
• Lecture 4, Tuesday, October 6: Negating expressions involving quantifiers, rules of inference, arguments, proofs, direct proof, indirect proofs, contraposition, contradiction, existence proofs.
• Lecture 3, Thursday, October 1:Predicates, universal and existential quantifiers, scope.
• October 2 (Friday): Homework 1 is posted. Due October 9 (Friday). Solutions to homework 1
• Lecture 2, Tuesday, September 29: Compound propositions, terminology, precedence of logical operators, conditional, biconditional, equivalences, tautology, contradiction, De Morgan's laws.
• Lecture 1, Thursday, September 24: Introduction & overview, propositional logic, AND, OR, NOT, variables and functions, truth tables.

Quiz and Final exam dates:

• Midterm exam: Tuesday, November 10, 12:30 - 1:45 pm. 
• Final exam: Tuesday, December 8, 12:00 - 3:00 pm.

• Textbook:

  • Kenneth H. Rosen, "Discrete Mathematics and Its Applications",  WCB, McGraw-Hill, 2007 (Sixth Edition).
  • Two copies of the textbook for 2-hour checkout are available in RBS, Davidson Library.

  Prerequisites:

  • Computer Science 10 or 12; and Mathematics 3C.

  Weekly Schedule:

  • Tuesday, Thursday 12:30-1:45 Lecture (PHELP 3505)
  • Wednesday 11:00-11:50 Discussion (Eyrun, PHELP 1508)
  • Friday 12:00-12:50 Discussion (Lijie, PHELP 1401)

  Homework assignment Schedule:

  • HW 1: Out Friday, October 2; Due Friday, October 9
  • HW 2: Out Friday, October 9; Due Friday, October 16
  • HW 3: Out Friday, October 16; Due Friday, October 23
  • HW 4: Out Friday, October 23; Due Friday, October 30
  • HW 5: Out Friday, October 30; Due Friday, November 6
  • HW 6: Out Friday, November 6; Due Monday, November 16
  • HW 7: Out Friday, November 13; Due Friday, November 20
  • HW 8: Out Friday, November 20; Due Friday, December 4

  All homeworks are due in the HW box marked CS40 in 2108 HFH by 4:00 pm.
  NO LATE HOMEWORKS ARE ACCEPTED.

  Office Hours:

  • Omer Egecioglu: Tuesday, Thursday 10:30-11:30 am, HFH 2115.
  • Eyrun A. Eyjolfsdottir: Wednesday 9:00-11:00 am, PHELP 1413.
  • Lijie Ren: Friday 9:00-11:00 am, PHELP 1413.

  Grading/Exams:

  • 40% Homework + 20% Midterm + 40% Final Examination

  Conduct

  You are required to work on the homework assigments on your own. Please check the policies for expected student conduct of the UCSB catalogue. Note that in particular "It is expected that students attending the University of California understand and subscribe to the ideal of academic integrity, and are willing to bear individual responsibility for their work. Any work (written or otherwise) submitted to fulfill an academic requirement must represent a student's original work. Any act of academic dishonesty such as cheating or plagiarism, will subject a person to University disciplinary action. Using or attempting touse materials, information, study aids, or commercial "research" services not authorized bythe instructor of the course constitutes cheating. Representing the words, ideas, or concepts of another person without appropriate attribution is plagiarism. Whenever another person's written work is utilized, whether it be single phrase or longer, quotation marks must be used and sources cited. Paraphrasing another's work, i.e., borrowing the ideas or concepts and putting them into one's "own" words, must also be acknowledged. Although a person's state of mind and intention will be considered in determining the University response to an act of academic dishonesty, this in now way lessens the responsibility of the student."