6.042J/18.062J Staff Notes
Week of Tues., Feb. 8 through Monday, Feb. 14.

----------------------------------------------------------------------

Reading: CLR Chapter 5 (photocopy handout); M&R Sections 0.1-3, 3.1-3.

----------------------------------------------------------------------

Lecture 3 -- Tuesday, Feb. 8

10    Sets
	Mention basis: 8 axioms + 2 axiom schemata (Zermelo-Skolem-Fraenkel)
	Defining sets
	Common sets
	Set equality
	Subsets
	Theorem: $A\subseteq B$ and $B\subseteq A$ iff $A=B$

15    Set operations
	Intersection, Union, Difference, Complement
	Laws, duality (p. 78 of CLR)
	Correspondence between predicates and sets
	Show DeMorgan's law with truth table method

15    Relations and graphs
	Ordered pairs as sets
	Cartesian products
	Def of relation
	Representation of relation as a digraph
	Definition of a digraph
	Representation of relation/digraph as an adjacency matrix

10    Properties of relations
	Reflexive: def and example
	Symmetric: def and example
	Transitive: def and example

20    Equivalence relations
	Equivalence classes
	Partitions
	Theorem: Equiv. relation is same as partition


----------------------------------------------------------------------

Lecture 4 -- Thursday, Feb. 10

30    Composition of relations
	Definition
	Square of a relation/graph	
	Paths in relations/graphs, reachability
	Acyclic relations, dags
	Thm: Every dag has a sink

15    Reflexive and transitive closure

15    Def of undirected graph
	Degree of a vertex
	Handshaking lemma
	$\card{E}\leq \card{V}^2$

30    Free trees
	Cycles in undirected graphs
	Defs of (free) trees/forests
	Equiv. defs of free trees (CLR, Ch. 5)


----------------------------------------------------------------------

Recitation 2 -- Friday, Feb. 11 -- Eulerian graphs 

(Follow Grimaldi, pp. 424-430)

 5    Bridges of Koenigsberg (undirected graph)

20    Theorem: Connected and all vertices have even degree => Euler cycle
	  Proof 

10    Corollaries
	Connected and 0 or 2 vertices have odd degree => Euler path
	Digraph connected and out-deg = in-degree => Euler cycle

10    Application: de Bruijn sequences 
	
----------------------------------------------------------------------