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