\documentstyle{article}

\begin{document}
\section{Introduction}
\subsection{Admin}
\subsection{6.042 Topics}
\section{Basic Proof Notions}
\subsection{Proofs -- What and Why}
\subsection{Propositions}
\subsection{Mathematical proofs}
\subsection{Basic Concepts/Notation}
\subsubsection{Sets}
\item $A \cap B$ means ``the intersection of $A$ and $B$'' (the set of elements
\subsubsection{Boolean Operators} 
\subsubsection{Predicates}
\subsection{Quantifiers}
\subsection{Axioms}
\subsection{Inference Rules for Propositions}
\subsection{Inference Rules for Predicates}
\setcounter{section}{2}
\section{Logical Proof Systems}
\subsection{Example: equality}
\subsection{Completeness/Consistency}
\section{How To Prove Things}
\subsection{Direct Proof}
\subsection{Proof by Contradiction}
\subsection{A Nonconstructive Existence Proof}
\subsection{Proof by Cases}
\subsection{Other Proof Methods}
\subsection{Fallacies}
\setcounter{section}{4}
The reading for Homework 2 is Rosen, sections 3.1-3.3.
\section{What we Expect in your Proofs}
\subsection{Some Actual Proofs...}
\section{Definitions}
\subsection{What Definitions to Make?}
\subsection{Well-Definedness}
\subsection{Peano's Axioms}
\subsection{Using Peano's Axioms}
\section{Real World Proofs By Induction}
\subsection{What They Are}
\subsection{Simple Number Properties}
\subsection{Die Hard}
\setcounter{section}{7}
\section{Some Warmup Inductions}
\subsection{Sums of Sequences}
\subsection{Angles in A Polygon}
\subsection{Courtyard Tiling}
\subsection{Fallacies}
\section{Induction on Recursive Definitions}
\subsection{Less formal Inductions}
\subsection{Addition}
\section{Other Inductions}
\subsection{Picky Axiomatic Remarks}
\section{Strong Induction}
\subsection{Definition}
\subsection{Fibonacci Examples}
\subsection{Fallacies}
\subsection{Number Theory}
\subsection{Ordinary vs. Strong Induction}
\setcounter{section}{7}
\section{Strong Induction}
\subsection{Definition}
\subsection{Nim}
\subsection{Structural Induction on a Recursive Definition}
\subsubsection{Example: Well-formed Formulas}
\subsubsection{Example: Binary Trees}
\section{The Well-Ordering Principle}
\subsection{Definition}
\subsection{Example: lowest terms for rational numbers}
\section{Number Theory}
\subsection{Example: Factorization}
\subsection{The Division Algorithm}
\subsection{Well-Ordering vs. Induction}
\subsection{Tiling}
\setcounter{section}{10}
\section{Natural Numbers and Integers}
\subsection{Divisibility and Primes}
\subsection{GCDs and LCMs}
\subsection{Fundamental Theorem of Arithmetic}
\subsection{Euclid's GCD Algorithm}
In this section, we present an algorithm for GCD (and therefore also LCM) that
\subsubsection{Euclid's Algorithm for GCD}
\subsubsection{Correctness Proof}
\setcounter{section}{6}
\setcounter{subsection}{4}
\subsection{Finding GCD coefficients}
\subsection{RSA cryptosystem}
\subsection{Algorithm Verification}
\section{State Machines}
\subsection{Definitions: State Machine, Executions and Reachability}
{\it This section is a summary of a more complete version of Handout 11.}
\subsection{Invariants}
{\it This section is a summary of a more complete version of Handout 11.}
\subsection{Fast Multiplication}
\setcounter{section}{7}
\subsection{Why do Proofs?}
\section{Distributed Algorithms}
\subsection{Leader Election}
\subsection{Alternating Bit Protocol}
\setcounter{section}{8}
\section{Sets}
\subsection{Definitions}
\subsection{Russell's paradox}
\subsection{Basic set operations}
\item Intersection 
(see textbook, sections 1.4, 1.5). \\
Union and intersection can be extended to apply to more than two sets.  \\
intersection of no sets is universal set. \\
This definition of union and intersection of no sets might seem
Analogously, for intersection. The recursive definition 
denotes the intersection of all the sets in ${\cal S}$. \\
\item set intersection vs. predicate and: 
\subsection{Power set (set of all subsets)} 
\subsection{Set identities}
(Distributivity:  Union distributes over intersection) \\
It follows by definition of intersection that $x$ is in the intersection
It again follows that $x$ is in the intersection. 
Then by definition of intersection, $x \in A^c \cap B^c$.
\subsection{Cartesian products}
\section{Relations}
\subsection{Definitions}
\subsection{Properties of Relations}
\subsection{Representation}
\subsection{Lists}
\subsection{Boolean matrices}
\subsection{Digraphs} 
\subsection{Composition}
\section{Equivalence relations and partitions}
\subsection{Definitions}
\subsection{Integers modulo $m$}
the next subsection.
\subsection{Fast Exponentiation}
\setcounter{section}{11}
\section{Functions}
proved in a later section.
\subsection{Composition}
\subsection{Inverses}
\section{Cardinality}
\section{Pigeonhole principle}
\subsection{Strong Pigeonhole}
\section{Infinite Sets}
\section{Countability}
\section{Uncountability}
\section{Proving Sets are Countable}
\section{Sizes of Infinite Sets}
\section{Partial Orders}
\subsection{Definitions}
\subsubsection{Partial Order Definition}
\subsubsection{Reflexive and Transitive Closures}
\subsubsection{No Cycles}
\subsubsection{Posets and Hasse Diagrams}
\subsubsection{Partial vs. Total Orders}
\subsection{Topological Sorting}
\subsection{Parallel Task Scheduling}
\subsection{Dilworth's Theorem}
\subsubsection{The Basics}
\subsubsection{Increasing and Decreasing Sequences}
\subsubsection{Number of Comparisons for Database Setup and Searching}
\subsection{Logical Time in Distributed Systems}
\section{Graphs}
\subsection{Definitions and Basic Examples}
\subsubsection{Directed Graphs}
\subsubsection{Undirected Graphs}
\subsection{Degrees}
\subsubsection{Undirected}
\subsubsection{Directed}
\subsection{Graph Representation}
\subsubsection{Adjacency Lists}
\subsubsection{Adjacency Matrices}
\subsection{Paths and Connectivity}
\subsubsection{Basic defs and results}
\subsubsection{Connectivity}
\subsubsection{Paths and Adjacency Matrices}
\subsubsection{Reflexive, Transitive Closure(s)}
\subsection{Graph Coloring}
\section{Cheap Connectivity}
\section{Trees}
\subsection{Definitions}
\subsection{Spanning Trees and Forests}
\subsection{Counting Tree Edges.  Induction off Leaves}
\section{Euler Tours}
\section{Hamiltonian Paths}
\subsection{Oriented Trees}
\subsection{Counting on Trees}
\subsection{Applications of Trees}
\subsubsection{Binary Search Trees}
\subsubsection{Compiling}
\subsubsection{Decision Trees}
\subsection{Paths in Trees}
\section{Annuities}
\section{Related sums}
\section{Book Stacking}
\section{Products}
\section{Some Additional Summations}
\subsection{Sums of Squares}
\subsection{Some Infinite Sums}
\section{Asymptotic Notation}
\subsection{Big-Oh Notation}
\subsection{Big-Omega Notation}
\subsection{Big-Theta Notation}
\subsection{Little-oh notation}
\section{Hanoi Towers}
\subsection{Guess}
\subsection{Plug and Chug}
\subsection{Verification}
\subsection{Change of Variables}
\section{Linear Recurrences}
\section{Solving the Recurrence}
\section{Solving General Linear Recurrences}
\subsection{Repeated Roots}
\section{Inhomogeneous Recurrences}
\section{Merge Sort}
\subsection{Integer Breakage}
\section{Divide and Conquer recurrences}
\section{Recurrences in a product form}
\section{Introduction}
\section{Basic Counting Principles}
\subsection{Sum}
\subsection{Inclusion-Exclusion}
\subsection{Product}
\subsection{Case Analysis and its Tree Representation}
\subsection{Division Rule}
\subsection{A Remark on ``Distinct Ways''}
\section{Permutations and Combinations}
\subsection{Permutations}
\subsection{Combinations}
\section{Basic Properties of Binomial Coefficients}
\section{The Binomial Theorem}
\subsection{The Theorem}
\subsection{Identities via Binomial Theorem }
\subsection{General Binomial Theorem}
\section{Principle of Inclusion and Exclusion}
\section{Permutations and Combinations with Unbounded Repetition}
\subsection{Permutations}
\subsection{Combinations}
\section{Perms and Combs with Bounded Repetition}
\subsection{Combinations}
sizes of the pairwise intersections, plus the size of the 3-way
intersection.  \\
Each 2-way intersection has exactly one possibility. \\
There is no 3-way intersection. \\
All the 3-way or more-way intersections are empty. \\
\subsection{Permutations}
\subsection{Distinguishable Balls in Baskets}
\section{Probability}
\section{Let's Make a Deal}
\section{The Sample Space}
\section{The Probability of Winning}
\section{Probability and Set Theory}
and intersections.  But the advantage of a result like 
\section*{Independence}
\section*{Independence of more than two events}
\section{Conditional Probability}
\section{Another Example}
\section{Yet Another Example}
\section*{Example:One-Time Pads}
\section*{Example: Berkeley Admissions}
\section*{Bayes Rule}
\section*{Odds and Bayes Rule}
\section{Probability and Counting}
\subsection{Sum Rules}
\subsection{Case Trees and Conditional Probability}
\section{Independence and the Product Rule}
is a very simple rule to compute the probability of their intersection.
independent of the intersection of any others.
\section{The Birthday Problem}
\section{Random Variables}
\section{Independence of Random Variables}
\section{The Binomial Distribution}
\subsection{Asymptotics}
\subsubsection{The central term}
\subsubsection{The tails}
\subsubsection{Bounding Sums with Geometric Series}
\subsubsection{Limiting Distribution}
\section{Applications}
\subsection{Polling}
that we derived in the previous section. In particular, we have that\\ 
\subsection{Counting Fish}
\subsection{Leader Election}
\section{Summary}
\section{Definition and Simple Examples}
\section{Computing the Mean---a Shortcut}
\section{Linearity of Expectation}
\subsection{The Results}
\subsection{Simple Examples}
\subsection{Combinations of Events}
\section{Extra Problems}
\subsection{Coupon Collecting}
\subsection{Carnival Game}
\subsection{A two-player game}
\subsection{Another two-player game}
\section{Conditional Expectation}
\section{Expectations of Products}
\section{Wald's Theorem}
\subsection{Branching Processes}
We close this section with an application of Wald's Theorem to 
\section{Markov's Theorem}
\section{Variance and Chebyshev's Theorem}
\subsection{The Chebyshev Bound}
\subsection{A Different Variance Formula}
\subsection{Manipulating Variances}
\section{Exponential Bounds for Independent Events}
\section{Mind Reading Game}
\section{Chernoff Bound}
\section{Summary}
\end{document}

