CMSC 222: Discrete Structures for Computing
Fall 2008
TR 15:45-17:30 Jepson G24-A
Lab: TBA
Handouts
Links
Lectures:
| Date |
Title |
| Tue 26 Aug |
Introduction
[ppt]
[pdf]
|
| Thu 28 Aug |
Logic
[ppt]
[pdf]
|
| Tue 2 Sep |
Implication, Bi-implication, Logical Equivalence (class notes only)
|
| Thu 4 Sep |
Simple Digital Circuits, Converse/Inverse/Contrapositive,
Predicates, Universal and Existential Quantification
|
| Tue 9 Sep |
Universal and Existential Quantification, Rules of Inference
|
| Thu 11 Sep |
Proof Techniques: Direct Proof, Proof By Cases
|
| Tue 16 Sep |
Proof Techniques: Proof by Contradiction, Proof By Contraposition
|
| Thu 18 Sep |
RSA: Overview, Modular Exponentiation |
| Tue 23 Sep |
RSA: Modified Euclidean Algorithm, In-Class Example |
| Thu 25 Sep |
Induction
[ppt]
[pdf]
|
| Tue 30 Sep |
More Induction (no summations) |
| Thu 2 Oct |
Strong Induction |
| Tue 7 Oct |
Algorithm Analysis; Induction: Proving WC Analysis of Binary Search |
| Thu 9 Oct |
Exam 1 |
| Thu 16 Oct |
Proving Correctness: Recursive Algorithms |
| Tue 21 Oct |
Proving Correctness: Iterative Algorithms (Handout
[pdf]) |
| Thu 23 Oct |
Testing:
WordAnalyzer.java
WordAnalyzerTester.java
WordAnalyzerTester2.java
WordAnalyzerTester3.java
|
| Tue 28 Oct |
Proving Correctness; Set Theory |
| Thu 30 Oct |
Counting: Product Rule, Sum Rule (Handout [pdf]) |
| Tue 4 Nov |
More Counting: Inclusion/Exclusion, Pigeonhole Principle, Division
Rule (Handout
[pdf]) |
| Thu 6 Nov |
More Counting: Permutations, Combinations |
| Tue 11 Nov |
Generating Permutations, More Counting: Algebra of
Combinations |
Homework Assignments:
| Due Date |
Title |
Assignment |
| Tue 9 Sep |
Propositions, Predicates, Quantifiers |
hw1.pdf |
| Thu 18 Sep |
Quantifiers, Proofs |
hw2.pdf |
| Thu 2 Oct |
Induction |
§ 3.3: 1,3,7,13,19 |
| Tue 28 Oct |
Proofs of Correctness |
§ 3.6: 3,4,7; Example 2 from 21 Oct
handout |
| Thu 17 Nov |
Counting |
| 4.1: 3,11,17,19,25,37,39,41,55 |
| 4.2: 3,5,7,9,11,15 |
| 4.3: 3,11,17,27,31,33,39 |
| 4.4: 15,17,19,21(b),23,27(b) |
|
Quizzes:
Projects:
|
|