Time: Wednesday 11:30-12:50, Friday 1:10-2:30
Recitation: Tuesday 11:30-12:50
Place: Campbell Hall, room A4
Semester: Fall 2004
Michael's office hours: Hill 409, by
appointment.
Sam's office hours: Hill 418, by
appointment.
| Date | Sections | Topics | Problems |
| 9/1 | 1.6, 1.7 | sets, subsets | 1.6: 4, 6, 8, 10, 12, 14, 16, 18, 22, 24.c 1.7: 2, 4, 10, 20, 22 (justify your answer), 24, 38, 40, 48 (see definition in 47), 50 (see definition after 48, assume the university will buy all the equipment and departments will borrow what they need temporarily) |
| 9/3 | 1.8 | functions mapping set to set, domain, co-domain, range, one-to-one, onto, inverse, composition | |
| 9/8 | 1.1 | propositions, and, or, not, xor, truth tables, implication, contrapositive, converse, inverse | |
| 9/10 | 1.2 | translating logic expressions, equivalences, tautology, contradiction, contingency, DeMorgan, distributive, associative | 1.1: 10, 12, 16, 22, 24(d,e), 28(c,f), 30 1.8: 2(b,c) (justify your answer), 6, 12, 14(a,b,if not, give counterexample), 16, 18, 22 (give values for all elements of S), 24 (name the range), 28, 30, 34 (optional), 66.b |
| 9/15 | 10.1, 10.2 | complementation, Boolean expressions (recursive definition), literal, minterm, DNF, CNF | |
| 9/17 | 10.3 | combinatorial circuit, and gate, or gate, inverter, half adder, full adder | 1.1: 34(b, c; see pg. 14 for bitwise definition), 44, 48
(consistent means "their conjunction is not a
contradiction"), 52 (optional), 54 (optional) 1.2: 4(a), 6, 10 (detailed proofs, see pg. 25 for example), 12, 30 (optional), 40 10.1: 2, 4(b,d), 6(b,d, optional), 26 (optional), 32 (detailed proof, optional), 34 (detailed proof, optional) |
| 9/22 | 1.3 | predicate, propositional function, universal quantification, existential quantification, predicate calculus, connection to conjunction and disjunction | |
| 9/24 | 1.4, 1.5 (start) | nested quantifiers, negating nested quantifiers, proof, axioms, rules of inference, fallacy, lemma, corollary, conjecture, valid arguments, modus ponens | 1.3: 2(a,b), 10, 12, 22 1.7: 6(a,d,e,g, use quantifiers), 12(a,d, use quantifiers) 10.2: 4(c,d, sum of products means DNF), 6, 8 (answer should be in CNF), 12(c,d), 18 (downarrow is "nor"), 20(a,c, justify your answer) 10.3: 2 (give formula), 4 (give formula), 6(c,d), 10, 12 (build the circuit, using the full and half subtractors as components), 16, 18 |
| 9/29 | 1.5 (rest) | universal/existential instantiation/generalization, direct proof, indirect proof, proof by contradiction, proof by cases, non-constructive existence proof, strategy-stealing argument | |
| 10/1 | MIDTERM | ||
| 10/6 | 3.1, 3.2 (remotely) | 1.3: 26, 30, 34, 38, 40, 42 (supply the inference rules),
46 (give counterexample), 50 (see notation in problem
48), 56, 58 1.4: 8, 10, 12(j,k,l), 16(d,e), 22, 30, 38 (say "true" if no counterexample exists), 42, 48 |
|
| 10/8 | 3.3 | induction, basis, inductive hypothesis | 1.5: 12 (name the inference rule of fallacy for each), 14 (evaluate the validity of the reasoning, not the validity of the statements), 16, 18, 20, 28, 36, 38, 42, 48, 50, 52, 54, 56, 60 (supply the inference rule), 64 (optional), 74 |
| 10/13 | 3.4 | strong induction | |
| 10/15 | 3.4 (more) | induction, recursion | 3.1: 2, 4, 6 (hint: from class), 8 (hint: from class),
12 (compare quadratic mean, a, and b), 20, 22, 26, 28, 32
(optional) 3.2: 6(d,e,h), 10(a,e), 20, 30, 38 (optional), 42 (optional) 3.3: 4, 6 (cute one!), 8, 12, 14 |
| 10/20 | 3.5 | recursion, iteration, repeated squaring | |
| 10/22 | 7.1, 7.3 | relations, reflexive, symmetric, antisymmetric, transitive, directed graph, matrices (Eric Allender covering) | |
| 10/27 | 7.4 | closure, path, connectivity relation | |
| 10/29 | 7.5, 7.6 | 3.3: 16, 18, 24, 28, 30, 36, 42 (ask if you need the
definition of matrix multiplication), 44, 48, 50, 52, 54,
58 (Hn = 1/1 + 1/2 + ... + 1/n) 3.4: 6, 8, 12 (fn is the nth Fibonacci number), 14 (hint: use a proof by induction and carefully apply the definition of fn), 18, 22, 26 (optional), 28, 30, 36 (use the definition from the solution to problem 35), 42, 44, 46, 48 (see the definition immediately above), 50, 54 |
|
| 11/3 | MIDTERM | ||
| 11/5 | 11.1 | natural language, vocabulary, sentence, empty string, language, phrase-structure grammar, directly derivable, derivable, derivation | 7.1: 4, 8, 20 (see definition before problem 16), 22, 24
(see definition above the problem), 30, 34(a,d, see
definition before problem 32), 36, 48 (optional), 56 7.3: 8, 14(c,d,e), 20, 24 (list the ordered pairs), 32 7.4: 2, 10, 14 (optional), 18, 22, 24 7.5: 2, 6 (Hint: Think about the range of f.), 10, 24, 28 |
| 11/10 | 11.1, 11.3 | parse tree, finite state automaton | |
| 11/12 | 11.2 | finite state transducer | (Due a week from Tuesday) 7.5: 30, 34 (recall [x,y] includes the endpoints and (x,y) doesn't), 40, 42 7.6: 4, 6, 8 (bar means "divisibility"), 10, 16, 22, 26, 28, 30 (can draw a diagram), 38, 48 (optional), 56 11.1: 2, 6 (give a proof by induction) |
| 11/17 | 11.3, 11.4 | regular sets, regular languages, NFAs, DFAs | |
| 11/19 | 11.4 | Kleene's theorem, pumping | 11.1: 8 (show everything generated has this form and
everything of this form can be generated), 12, 16, 18, 24 11.3: 2, 8 (use definition of set equality), 12 (give a regular expression for your answer), 22, 24, 26 |
| 11/24 | NO CLASS | ||
| 11/26 | NO CLASS | ||
| 12/1 | 11.5, 2.2 | halting problem, Big O | |
| 12/3 | 2.2, A.1 | big-O, big-Omega, big-Theta, logs, exponentials | 2.2: 2, 6, 8, 12, 14(d,e,f), 18, 22, 26, 36 11.1: 20 11.3: 2, 8.b, 10, 18 |
| 12/8 | wrap up | ||
| 12/10 | juggling, site-swap notation | ||
| 12/20 | FINAL |