CSE 311 Spring 2012

Lecture Topics

Lecture Topics

Date | Description |
---|---|

March 26 |
Propositions; ¬, ∧, ∨, → 1.1-1.3 (7th), 1.1-1.2 (6th) |

March 28 | Truth tables, ↔, logical equivalence |

March 30 | Logical equivalences, disjunctive normal form |

April 2 |
Complexity of proving tautologies; predicates, quantifiers 1.4-1.5 (7th), 1.3-1.4 (6th) |

April 4 | Nested quantifiers, logical equivalences |

April 6 |
Sets: ∈, ⊆, =, power set; first proofs 2.1-2.2 |

April 9 | Cartesian product, ∪, ∩, − |

April 11 |
Functions: injective, surjective 2.3 |

April 13 | bijective, inverse, composition |

April 16 |
Divisibility, primes, Fundamental Theorem, Division Theorem 4.1&4.3 (7th), 3.4-3.5 (6th) |

April 18 | Modular arithmetic |

April 20 |
Modular exponentiation; GCD, Euclid's algorithm End of 4.2 (7th), 3.6 (6th) |

April 23 | Properties of gcd; proof by contradiction |

April 25 |
RSA cryptosystem Slides |

April 27 | Digital signatures, coin-flipping; induction |

April 30 |
Induction, correctness of Euclid's algorithm 5.1 (7th), 4.1 (6th) |

May 2 |
Strong induction 5.2 (7th), 4.2 (6th) |

May 4 |
Recursive definitions 5.3 (7th), 4.3 (6th) |

May 7 | Midterm exam |

May 9 |
Relations 9.1 (7th), 8.1 (6th) |

May 11 |
Equivalence relations 9.5 (7th), 8.5 (6th) |

May 14 |
Graphs, Boolean functions 10.1, 10.4, 12.1 (7th), 9.1, 9.4, 11.1 (6th) |

May 16 |
Normal forms, circuits, ripple-carry adder 12.2-12.3 (7th), 11.2-11.3 (6th) |

May 18 |
Finite-state machines 13.2 (7th), 12.2 (6th) |

May 21 |
Finite-state automata 13.3 (7th), 12.3 (6th) |

May 23 |
Regular expressions 13.4 (7th), 12.4 (6th) |

May 25 | Kleene's Theorem |

May 30 |
Halting problem 3.1 |

June 1 |
Turing machines, undecidability 13.5 (7th), 12.5 (6th) |