# CS40 (Summer 2015) — Foundations of CS — TA's Notes

This page is dedicated to CS40 class taught at the UCSB during Summer, 2015. Vaguely titled "Foundations of CS", this class is mainly about Discrete Mathematics and to a lesser extent about Mathematical Logic. On this page, I will post announcements and useful notes, while the main and official source of class-related information is GauchoSpace. If you have a question not answered here, please email me or, much better, come to my office hours.

### Contact Info:

TA: Victor Amelkin
Email: victor+cs40@cs.ucsb.edu (PGP key)
Office Hours: Friday, 1-3pm (or by appointment), at GSL (Trailer 698)

### Discussion Notes:

• Week I:
• Main notes — notes on the product and sum rules, permutations, combinations, multinomial coefficients.
• Domino and Fibonacci — a note on using the sum product to express the number of tilings of a cell array with 2-dominoes as Fibonacci numbers.
• Combinations with repetitions — a note on combinations with repetitions and useful ways to look at problems of integer constraint satisfaction and partitioning integers.
• Week III:
• Main notes — notes on propositional logic, logical equivalence, rules of inference, proofs. A possible overlap with Week II.
• A note on quantifiers — a proof involving quantifiers.
• A note on counting propositions — a note on a problem with counting propositions of a special form; the problem appeared in one of the older midterms with the same instructor.
• Functional completeness — proving functional completeness / incompleteness of a system of logical connectives / boolean functions.
• Week IV:
• Sets, relations — these are my old notes on set theory and relations. This week's discussion is led by John, and he will likely use different notes. Thus, think of my notes for Week IV as an extra material (I can refer to them during the office hours).
• Week V:
• Relations, induction, recursion — it is a very raw scan of the collection of notes on relations, induction, and recursion that I have used during Week V's discussion. We have covered about 60% of this material. Recursion has been only briefly mentioned at best.
• Esoteric induction — oftentimes, a single basis case and a simple rule of inference (a combination of "hypothesis" and "induction step") of type (i) ⇒ (i+1) can work just fine for the purpose of mathematical induction. However, like I mentioned in class, it does not always have to be so. When proving the correctness of a proposition / statement P(n) for all legal choices of n, you can use any finite number of basis cases and any finite number of rules of inference as long as this entire system allows to (implicitly) produce correctness proofs for any P(i). Also, make sure that, if you decide to use an esoteric system of inference rules, you clearly describe how these rules along with the basis/bases imply correctness of every P(i). The given example of a "not-so-standard" induction is taken from Concrete Mathematics.

### Extracurricular Resources:

• Combinatorics
• Enumerative Combinatorics (Volume 1) by Richard Stanley — a comprehensive book on combinatorics. A preprint of the first volume is freely available from the author's web-site.
• generatingfunctionology by Herbert Wilf — there is not always enough time to cover generating functions in CS40, yet, this topic is of utmost importance for the combinatorial side of computer science. Thus, feel free to study this subject on your own. The book "generatingfunctionology" by Herbert Wilf is an excellent resource. Its second edition is freely available from the author's web-site.
• Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick — an advanced book on the applications of generating functions and symbolic methods in combinatorics. The book is freely available online.
• Concrete Mathematics by Graham, Knuth, and Patashnik — an excellent mix of discrete mathematics and number theory. Important preliminaries for studying algorithms. UCSB did not have it at the library, but it is available through the inter-library loan.
• Mathematical Logic:
• A tutorial on Karnaugh maps by Jack Crenshaw — a tutorial on using Karnaugh maps for minimization of compound propositions / Boolean formulas.
• Boolean SAT by Lee et al. — slides on the Boolean SAT(isfiability) problem — one of the fundamental problems in Computer Science. A theoretically efficient solution is unlikely to exist, and researchers compete in designing heuristics to solve SAT problems as fast as possible.
• Functional completeness — my old notes on functional completeness (and incompleteness) of a system of logical operators. Post's completeness criterion. Incompleteness of system {∧, ∨} (and any other system, which is indeed such). Sheffer stroke and Peirce's arrow.